CODEWITHSUNDEEP
c++stliteratorcontainers
user88637
user88637

Reputation: 12140

Do STL iterators guarantee validity after collection was changed?

Let's say I have some kind of collection and I obtained an iterator for the beginning of it. Now let's say I modified the collection. Can I still use the iterator safely, regardless of the type of the collection or the iterator?

To avoid confusion, here is the order of operations I talk about:

  1. Get an iterator of the collection.
  2. Modify the collection (obviously not an element in it, but the collection itself).
  3. Use the iterator obtained at step 1. Is it stil valid according to STL standard?!

Upvotes: 34

Views: 10986

Answers (4)

lkel
lkel

Reputation: 26

As a person from the future wondering if I can happily implement LRU cache with list::iterator objects. Here are some extracted requirements from the a c++ standard draft: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4849.pdf dated 2020-01-14.

ISO/IEC N4849 Working Draft, Standard for Programming Language C++

22.3.10.4

...
void push_back(T&& x);

1 Remarks: Does not affect the validity of iterators and references. If an exception is thrown there are no effects.

iterator erase(const_iterator position);
iterator erase(const_iterator first, const_iterator last);
void pop_front();
void pop_back();
void clear() noexcept;

3 Effects: Invalidates only the iterators and references to the erased elements. ...

However, these same requirements are not composed on other containers. A good place to start for your specific container is section 22, Containers Library.

Upvotes: 1

kennytm
kennytm

Reputation: 523304

Depends on the container. e.g. if it's a vector, after modifying the container all iterators can be invalidated. However, if it's a list, the iterators irrelevant to the modified place will remain valid.

  • A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point. It follows that you can prevent a vector's iterators from being invalidated if you use reserve() to preallocate as much memory as the vector will ever use, and if all insertions and deletions are at the vector's end. [1]

  • The semantics of iterator invalidation for deque is as follows. Insert (including push_front and push_back) invalidates all iterators that refer to a deque. Erase in the middle of a deque invalidates all iterators that refer to the deque. Erase at the beginning or end of a deque (including pop_front and pop_back) invalidates an iterator only if it points to the erased element. [2]

  • Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. [3]

  • Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased. [4] (same for set, multiset and multimap)

Upvotes: 50

Jerry Coffin
Jerry Coffin

Reputation: 490148

That depends on the collection in question. Just for example, modifying a std::vector (e.g., adding an element somewhere) can invalidate all iterators into that vector. By contrast, with a std::list, iterators remain valid when you add another element to the list. In some cases, the rules are even more complex (e.g., if memory serves, with a std::deque, adding to the beginning or end leaves existing iterators valid, but adding anywhere else can invalidate them -- but my memory is sufficiently poor that you should check before depending on that).

Upvotes: 8

m1tk4
m1tk4

Reputation: 3467

No, iterators are only good while the iterated container is unchanged. If a collection is modified, the iterator should be obtained anew.

Upvotes: 3

Related Questions