CODEWITHSUNDEEP
c++c++11while-loopiterator
Gopesh Bharadwaj
Gopesh Bharadwaj

Reputation: 160

Loop condition works well with raw iterator but not with iterator dereferencing

In the snippet below, while(litr < = ritr) works well, but while(*litr < *ritr) can not be met and goes out of range and crashes when try to search element which is not present in vector. I understand, loop will work with raw iterators but Why loop condition can not be met with iterator dereference?

bool binarySearch(std::vector<int> sorted_list, int item)
{
    if(sorted_list.empty())
    {
        return false;
    }
    
    auto litr = sorted_list.begin();
    auto ritr = sorted_list.end()-1;

    while(litr <= ritr)
    {
        int leftindex = std::distance(sorted_list.begin(), litr);
        int rightindex = std::distance(sorted_list.begin(), ritr);

        int mid = (leftindex + ((rightindex-leftindex)/2));

        if(sorted_list.at(mid) == item)
        {
            return true;
        }

        if(item < sorted_list.at(mid))
        {
            ritr = sorted_list.begin() + mid-1;
        }
        else
        {
            litr = sorted_list.begin()+ mid+1;

        }
    }

    return false;
}

Upvotes: 0

Views: 88

Answers (1)

Eric Backus
Eric Backus

Reputation: 1924

I don't understand what you mean by "iterator deduction". I think you mean "dereferencing"?

Anyway, you're asking about while(litr <= ritr) (which works) compared to while(*litr < *ritr) (which fails). There are several differences.

LessThanOrEqual vs. Equal

The working code uses <= rather than just <, and the equals part is necessary for correct operation.

Consider a sequence of just three elements (0, 10, 20), and the search item is 20. Then leftindex = 0, mid = 1, rightindex = 2. The search item is greater than mid, so the next index values are leftindex = 2, rightindex = 2. If there is no equals in the comparison, the loop ends here, and the function returns false, which is incorrect. The loop condition must be <= so that the loop executes again and the item is found.

Iterator Comparison vs. Dereferencing the Iterators

When using <= for the loop condition, dereferencing the end() iterator is a problem in some cases.

Consider a sequence of just two elements (0, 10), and the search item is 20. Then leftindex = 0, mid = 0, rightindex = 1. The search item is greater than mid, so the next values are leftindex = 1, rightindex = 1. On this loop, the search item is still greater than mid, so the next values are leftindex = 2, rightindex = 1. Note that leftindex is 2, which is equal to end(). If the loop condition uses litr <= ritr, this is OK. But if the loop condition uses *litr <= *ritr, the attempt to dereference the end iterator is undefined behavior.

Iterator before begin()

Similar to above, consider a sequence of just two elements (0, 10), and the search item is -10. Then leftindex = 0, mid = 0, rightindex = 1. The search item is less than mid, so the next values are leftindex = 0, rightindex = -1. Just setting the iterator to this value is undefined behavior. Obviously dereferencing it is also undefined behavior.

Note that even your "working" variation while(litr <= ritr) has this problem. You will need some other code to prevent this.

Other

Your code does auto ritr = sorted_list.end()-1;, so it assumes that there are is at least one element in the sorted list. You should modify the code to handle the case of an empty list.

Upvotes: 1

Related Questions