CODEWITHSUNDEEP
c++11stliterator
TypeIA
TypeIA

Reputation: 17248

Are std::list iterators unique and persistent?

I know that std::list iterators are Equality Comparable (as Bidirectional Iterators). Now, is the following code well-defined and guaranteed to print "equal"?

std::list<int> nums = { 1, 2, 3 };
std::list<int>::iterator a = std::find(nums.begin(), nums.end(), 1);
nums.push_front(0);
std::list<int>::iterator b = std::find(nums.begin(), nums.end(), 1);
if (a == b) std::cout << "equal" << std::endl;

It works for me, but that doesn't mean it's well-defined or guaranteed!

In other words, if one finds an iterator to a particular std::list entry at different times (possibly with other elements having been added or removed in between), are the two iterators guaranteed to be equal?

This question is specifically about std::list iterators (if it matters), but an answer that also covers other STL containers in general would be excellent!

Upvotes: 1

Views: 936

Answers (2)

eerorika
eerorika

Reputation: 238351

It is well-defined and guaranteed, assuming both iterators are valid (which they are in this case). That is how the equality between (forward, and more specialized) iterators is defined.

[forward.iterators] (standard draft)

5 If a and b are equal, then either a and b are both dereferenceable or else neither is dereferenceable.

6 If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object.

Since your iterators a, and b point to the same object, they must compare equal.

(possibly with other elements having been added or removed in between)

For some containers, this could have effect on the validity of the iterator that was created before the modifications. If one of the iterators is invalidated, then it is no longer guaranteed to point to the object that it used to. In fact, it would no longer be guaranteed to point to the container at all, so the result of the comparison would not be defined.

Non-end iterators of std::list in particular won't be invalidated unless the particular element they point to is removed. Each container has their own invalidation rules, that must be looked up from the documentation.

Upvotes: 2

Marshall Clow
Marshall Clow

Reputation: 16670

Yes. This is guaranteed for std::list, but not for (say) vector.

[list.modifiers]/1 says (about all the calls to insert, push_back, etc): "Remarks: Does not affect the validity of iterators and references"

[vector.modifiers]/1 says instead: "Remarks: Causes reallocation if the new size is greater than the old capacity. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. If no reallocation happens, all the iterators and references before the insertion point remain valid. "

Upvotes: 3

Related Questions