Removing item from ordered list via binary search, and getting seg faults.

[fiji885]

I implemented the code to remove an item from an ordered list (low to high). The code seems to work only if valueToErase is done with something like:

classObject.erase(someValue);

Now, if I do something like this...

int x;
std::cin >> x;
classObject.erase(x);

I get a segmentation fault, and the program crashes. Does it have something to do with getting input from the console?

The code...

while(low <= high)
{
    mid = (low+high) >> 1;
    if(valueToErase == this->list[mid])
    {
        pos = mid;
        found = true;
        break;
    }
    if(valueToErase < this->list[mid])
        high = mid - 1;
    else
        low = mid + 1;
}
// If used std::cin to remove an item, the program doesn't even get to here. It crashes somewhere within the while loop.
if(!found)
{
    return false;
}
else
{
    // Erases value...
}

[jonnin]

print mid and the value at mid for each iteration of that while, then run the search code where the item you seek is the first item, the last item, a random item, and not present at all to see if it is working.

if that works 100%, then we need to see the erase code.

did you initialize found to false?

[fiji885]

found declared and initialized as false. For high, it is high = this->size()-1; and low is set to 0. Also, I forgot to mention above, std::cin only gives me a segmentation fault IF the value isn't on the list.

I did a test run with this list.
{ 263, 604, 633, 959 }

I then tried to remove 10 from the list, which isn't there. For all the iterations in the while loop, I printed the value of mid...

Trying to erase: 10, Mid value is: 2

Trying to erase: 10, Mid value is: 0

Trying to erase: 10, Mid value is: 9223372036854775807

Trying to erase: 10, Mid value is: 4611686018427387903

Segmentation fault (core dumped)

Small update
I've had it all wrong. Input from the user isn't what is causing the problem here. It seems that it's giving me a segmentation fault if I try to remove a value that is lower than whatever the first element on the list is...

[JLBorges]

What happens when mid == 0 and valueToErase < this->list[mid]?
If the type of mid is an unsigned integer type, what would be the value of mid-1 when mid == 0?

[JLBorges]

There are some clear advantages to using signed integer types for arithmetic.
http://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Res-signed

Consider writing many small functions instead of one big one. For example:

#include <iostream>

// return position of value if found in [left,right], return -1 otherwise
int find( const int ordered_list[], int left, int right, int value )
{
    if( right < left ) return -1 ;

    const int mid = left + (right-left)/2 ;
    if( ordered_list[mid] == value ) return mid ;
    else return ordered_list[mid] > value ? find( ordered_list, left, mid-1, value )
                                          : find( ordered_list, mid+1, right, value ) ;
}

// return position of value if found in ordered_list, return -1 otherwise
int find( const int ordered_list[], int size, int value )
{ return find( ordered_list, 0, size-1, value ) ; }

// erase element at position pos
void erase_at( int ordered_list[], int size, int pos )
{
    for( int i = pos+1 ; i < size ; ++i ) ordered_list[i-1] = ordered_list[i] ;
}

// erase first element equal to value, return true.
// return false if no element equal to value was found
bool erase( int ordered_list[], int size, int value )
{
    const int pos = find( ordered_list, size, value ) ;
    if( pos == -1 ) return false ;

    erase_at( ordered_list, size, pos ) ;
    return true ;
}

void print( const int list[], int size )
{
    for( int i = 0 ; i < size ; ++i ) std::cout << list[i] << ' ' ;
    std::cout << '\n' ;
}

int main()
{
    const int N = 20 ;
    int ordered_list[N] ;
    for( int i = 0 ; i < N ; ++i ) ordered_list[i] = i+1 ;
    print( ordered_list, N ) ;

    int curr_size = N ;
    while( curr_size > 0 )
    {
        int value ;
        std::cout << "value? " && std::cin >> value ;
        if( erase( ordered_list, curr_size, value ) ) --curr_size ;
        print( ordered_list, curr_size ) ;
    }
}

[fiji885]

@JLBorges
Fixed it. Thank you. The issue was that I doing arithmetic through unsigned types and causing some overflows. Very informative link.