I used std::map in STL. Can I use iterator after some other element inserted to the map? Is it still valid?
Add a comment |
3 Answers
When in doubt as to the semantics of an operation on a container, consult the documentation:
Map has the important property that inserting a new element into a
mapdoes not invalidate iterators that point to existing elements.Erasing an element from a
mapalso does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased.
This is taken from the SGI STL documentation. While this documentation technically does not specify the behavior of the C++ Standard Library containers, the differences are generally insignificant, aside from the parts of the STL that are not part of the C++ Standard Library, of course.
The SGI STL documentation is an indispensable reference, especially if you don't have a copy of the C++ Standard.
4 Comments
David Rodríguez - dribeas
+1, the SGI docs are quite good. The only better source of information --even if harder to read-- is the standard. You can buy your own electronic copy of the standard for around $30, or you can download it from google's codeassist here
Alexis Wilke
Note that your link to the SGI documentation doesn't (probably hasn't for a long time). I would suggest you remove it.
Hi-Angel
Interestingly,
unordered_map::insert OTOH invalidates iterators. This blows my mind, you'd expect it the other way round: map is tree-based, so it'd need to rebalance (and hence to invalidate), whereas unordered_map uses hashes that could be left as is.
Miljen Mikic
@Hi-Angel For
unordered_map::insert, it is easy to grasp, as the map's capacity can be exceeded after insertion, and then rehashing is required. However, I am also surprised by how std::map achieves this, considering that it needs to rebalance.From standard 23.1.2/8
The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.
1 Comment
Ben Voigt
This answer covers an important case that the accepted answer misses. Specifically,
somemap.end() is an iterator to the container, but it is not an iterator that points to an existing element, which the other answer discusses exclusively.Inserting into std::map does not invalidate existing iterators.
