Home > database >  Why "operator<" for std::vector<int>::iterator seems to compare absolute values w
Why "operator<" for std::vector<int>::iterator seems to compare absolute values w

Time:04-02

cppreference on std::vector doesn't seem to have any links for std::vector<T>::iterator type. Since it is a bidirectional iterator on a contigious memory, I supposed that it can be "negative".
std::distance(vec.begin(), std::prev(vec.begin()) yields -1, and I ended up using std::distance to compare iterators for a loop.
But I was expecting while(iterLeft < iterRight) to be a valid check, and it is shorter than while(std::distance(iterLeft, iterRight) > 0).

This code, however, demonstrates that operator< for some reason seems to compare absolute values:
(This code surved to recreate the problem. The actual code had a variable-sized vector as an input)


#include <vector>
#include <iostream>

int main()
{
    std::vector<int> vec{};
    auto iterLeft = vec.begin(),
        iterRight = std::prev(vec.end());

    std::cout << "Left = " << std::distance(vec.begin(), iterLeft) 
        << ", Right = " << std::distance(vec.begin(), iterRight) 
        << ", Left < Right: " << std::boolalpha << bool(iterLeft < iterRight)
        << std::endl;

    return 0;
}

Program returned: 0
Left = 0, Right = -1, Left < Right: true

https://godbolt.org/z/PErY35Ynj


UPDATE 2

So basically the UB is caused Not by std::prev(vec.end()), but by an iterator goind out of range (before .begin()).


UPDATE 1

I don't get why so many downvotes. The policy of SO is about the quality of a question, not about someone implicitly knowing if the code is UB or invalid.

The code example is just to recreate the problem. Initially the code is to traverse an array with 2 iterators and the intent was to make the code declarative (meaning to handle empty arrays without an explicit check).

for (auto leftIter = vec.begin(), rightIter = std::prev(vec.end()); leftIter < rightIter;)
{
 // do stuff
   leftIter;
 --rightIter;
}

The code worked fine for most cases, but empty arrays. Hence the question.

CodePudding user response:

std::distance can yield negative values if applied to valid iterators to the same range and operator< can be used to compare the ordering of valid iterators into the same range. And it does this comparison in the expected way. iterLeft < iterRight will be equivalent to std::distance(iterLeft, iterRight) > 0.

However the only valid iterators are those in the range from begin() to end(). Trying to obtain an iterator "before" begin() or "after" end() causes undefined behavior.

So std::distance(vec.begin(), std::prev(vec.begin()) does not result in -1. It has undefined behavior.

Similarly in your code block std::prev(vec.end()) has undefined behavior because the vector is empty and so vec.begin() == vec.end().

  •  Tags:  
  • c
  • Related