4

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.

Community
  • 1
  • 1
PoweredByRice
  • 2,479
  • 1
  • 20
  • 26

2 Answers2

6

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.

Community
  • 1
  • 1
Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • thanks for the answer, I agree with everything you say. However, in this particular case, it looks like `it` may be **non-singular**. See http://stackoverflow.com/questions/5441893/what-is-singular-and-non-singular-values-in-the-context-of-stl-iterators . While `it` is invalid, it is "associated" with the container (more accurately, *was* associated), which makes it non-singular. – PoweredByRice Apr 19 '17 at 23:38
  • @PoweredByRice: I don't see any relevant and/or authoritative statements of the matter on that page. You said it yourself: ***was*** associated, the past tense being the key. It is no longer associated. – Lightness Races in Orbit Apr 20 '17 at 14:29
  • so I guess the question is: when is an invalid iterator non-singular ? – PoweredByRice Apr 20 '17 at 15:02
  • @PoweredByRice: That I don't know for sure. My interpretation at the moment is that this comes down to the difference between iterator invalidation, and actually "physically" breaking the iterator. That is, for example, an iterator is invalidated after rehashing occurs, even though the resulting state of the container _may_ be the same as it was before. I think the standard wants us to consider all invalid iterators potentially singular and proceed on that basis. – Lightness Races in Orbit Apr 20 '17 at 15:12
1

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.

Bathsheba
  • 231,907
  • 34
  • 361
  • 483
  • 1
    Some C++ libraries use a class type for vector iterators (this leads to differing behaviour of the same code across libraries due to ADL, e.g. `find(v.begin(), v.end(), x);`). In debug mode they attempt to diagnose , for example, comparison of iterators into different vectors – M.M Apr 20 '17 at 00:15