Do STL iterators guarantee validity after collection was changed?

by

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)

More Related Contents:

  1. Why use iterators instead of array indices?
  2. What is an iterator’s default value?
  3. How can I use std::maps with user-defined types as key?
  4. What are the complexity guarantees of the standard containers?
  5. Why are Standard iterator ranges [begin, end) instead of [begin, end]?
  6. What happens if you call erase() on a map element while iterating from begin to end?
  7. Removing item from vector while iterating?
  8. Heterogeneous containers in C++
  9. Why use non-member begin and end functions in C++11?
  10. Sorting a vector in descending order
  11. What’s faster, iterating an STL vector with vector::iterator or with at()?
  12. What is the difference between const_iterator and non-const iterator in the C++ STL?
  13. Copy map values to vector in STL [duplicate]
  14. Custom Iterator in C++
  15. how portable is end iterator decrement?
  16. Why does storing references (not pointers) in containers in C++ not work?
  17. Can std::begin work with array parameters and if so, how?
  18. std::vector iterator invalidation
  19. Template class with template container
  20. Checking if an iterator is valid
  21. How does std::copy work with stream iterators
  22. Can raw pointers be used instead of iterators with STL algorithms for containers with linear storage?
  23. How to remove constness of const_iterator?
  24. What is the right approach when using STL container for median calculation?
  25. Are const_iterators faster?
  26. Incrementing iterators: Is ++it more efficient than it++? [duplicate]
  27. How to increment an iterator by 2?
  28. Types of iterator : Output vs. Input vs. Forward vs. Random Access Iterator
  29. iterator for 2d vector
  30. How can I copy one map into another using std::copy?

Leave a Comment