Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Invalidated iterator in a vector

I'm aware erasing will invalidate iterators at and after the point of the erase. Consider:

std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int>::iterator it = vec.end() - 1; //last element
vec.erase(vec.begin()); //shift everything one to the left, 'it' should be the new 'end()' ?
std::cout << (it == vec.end()); //not dereferencing 'it', just comparing, UB ?

Is it undefined behavior to compare (not dereference) an invalidated iterator (it in this case)? If not, is it == vec.end() guaranteed to hold true?

Edit: from the top answer it looks like this is UB if only it is a singular value. But from What is singular and non-singular values in the context of STL iterators? it seems like it is (or was) associated with the container hence making it non-singular.

I'd appreciate further analysis on this, thank you.

like image 771
PoweredByRice Avatar asked Mar 09 '23 07:03

PoweredByRice


2 Answers

Once your iterator has been invalidated, it may be UB to even compare it to something else:

[C++14: 24.2.1/10]: An invalid iterator is an iterator that may be singular.

[C++14: 24.2.1/5]: [..] Results of most expressions are undefined for singular values; the only exceptions are destroying an iterator that holds a singular value, the assignment of a non-singular value to an iterator that holds a singular value, and, for iterators that satisfy the DefaultConstructible requirements, using a value-initialized iterator as the source of a copy or move operation. [..]

Note that this means you also can't compare a default-constructed iterator to any .end().

Contrary to popular belief that "pointers are just memory addresses", these rules are also largely true for pointers. Indeed, the rules for iterators are a generalisation of the rules for pointers.

like image 174
Lightness Races in Orbit Avatar answered Mar 15 '23 16:03

Lightness Races in Orbit


Formally any iterator pointing to an element on or after the erased element is invalidated. So

  1. Yes this is UB (despite it being a pointer under the hood.)

  2. UB again, despite the obvious plausibility.

like image 20
Bathsheba Avatar answered Mar 15 '23 16:03

Bathsheba