Does insertion to STL map invalidate other existing iterator?
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
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.
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.
Does inserting/erasing an element from a std::map modify the iteration sequence?
In a std::map
the elements will be visited in order.
If you store an iterator that refers to an element that is not deleted, and hence not invalidated, the iterator will still refer to that same element. (If it was the end iterator, it remains the end iterator, as it is not invalidated).
When you advance that iterator, it will advance to the next element in order after the element you refer to.
For your particular example, yes, every element will be visited exactly once, because all deletion of elements was elements that are before the current iterator state of your loop.
If you insert elements ahead of whatever iterator you are using to iterate, then you'll eventually reach them as you iterate forward with your iterator. If you delete elements ahead of whatever iterator you are using to iterate, then they are no longer part of the future elements you'll reach if you iterate with that iterator.
If you insert or delete elements that are before the current location of the iterator, unless you start calling --
or similar functions, your current iteration will continue without noticing that they went away.
This is because ++
on a valid iterator in an ordered container is guaranteed to return the next element in the order, and operations on other iterators that do not invalidate an iterator don't change that iterator's invariants (like what element they refer to).
Iterator invalidation rules for C++ containers
C++17 (All references are from the final working draft of CPP17 - n4659)
Insertion
Sequence Containers
vector
: The functionsinsert
,emplace_back
,emplace
,push_back
cause 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. [26.3.11.5/1]
With respect to thereserve
function, reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. No reallocation shall take place during insertions that happen after a call toreserve()
until the time when an insertion would make the size of the vector greater than the value ofcapacity()
. [26.3.11.3/6]deque
: An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque. [26.3.8.4/1]list
: Does not affect the validity of iterators and references. If an exception is thrown there are no effects. [26.3.10.4/1].
Theinsert
,emplace_front
,emplace_back
,emplace
,push_front
,push_back
functions are covered under this rule.forward_list
: None of the overloads ofinsert_after
shall affect the validity of iterators and references [26.3.9.5/1]array
: As a rule, iterators to an array are never invalidated throughout the lifetime of the array. One should take note, however, that during swap, the iterator will continue to point to the same array element, and will thus change its value.
Associative Containers
All Associative Containers
: Theinsert
andemplace
members shall not affect the validity of iterators and references to the container [26.2.6/9]
Unordered Associative Containers
All Unordered Associative Containers
: Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements. [26.2.7/9]
Theinsert
andemplace
members shall not affect the validity of references to container elements, but may invalidate all iterators to the container. [26.2.7/14]
Theinsert
andemplace
members shall not affect the validity of iterators if(N+n) <= z * B
, whereN
is the number of elements in the container prior to the insert operation,n
is the number of elements inserted,B
is the container’s bucket count, andz
is the container’s maximum load factor. [26.2.7/15]All Unordered Associative Containers
: In case of a merge operation (e.g.,a.merge(a2)
), iterators referring to the transferred elements and all iterators referring toa
will be invalidated, but iterators to elements remaining ina2
will remain valid. (Table 91 — Unordered associative container requirements)
Container Adaptors
stack
: inherited from underlying containerqueue
: inherited from underlying containerpriority_queue
: inherited from underlying container
Erasure
Sequence Containers
vector
: The functionserase
andpop_back
invalidate iterators and references at or after the point of the erase. [26.3.11.5/3]deque
: An erase operation that erases the last element of adeque
invalidates only the past-the-end iterator and all iterators and references to the erased elements. An erase operation that erases the first element of adeque
but not the last element invalidates only iterators and references to the erased elements. An erase operation that erases neither the first element nor the last element of adeque
invalidates the past-the-end iterator and all iterators and references to all the elements of thedeque
.
[ Note:pop_front
andpop_back
are erase operations. —end note ] [26.3.8.4/4]list
: Invalidates only the iterators and references to the erased elements. [26.3.10.4/3]. This applies toerase
,pop_front
,pop_back
,clear
functions.remove
andremove_if
member functions: Erases all the elements in the list referred by a list iteratori
for which the following conditions hold:*i == value
,pred(*i) != false
. Invalidates only the iterators and references to the erased elements [26.3.10.5/15].unique
member function - Erases all but the first element from every consecutive group of equal elements referred to by the iteratori
in the range[first + 1, last)
for which*i == *(i-1)
(for the version of unique with no arguments) orpred(*i, *(i - 1))
(for the version of unique with a predicate argument) holds. Invalidates only the iterators and references to the erased elements. [26.3.10.5/19]forward_list
:erase_after
shall invalidate only iterators and references to the erased elements. [26.3.9.5/1].remove
andremove_if
member functions - Erases all the elements in the list referred by a list iterator i for which the following conditions hold:*i == value
(forremove()
),pred(*i)
is true (forremove_if()
). Invalidates only the iterators and references to the erased elements. [26.3.9.6/12].unique
member function - Erases all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first + 1, last) for which*i == *(i-1)
(for the version with no arguments) orpred(*i, *(i - 1))
(for the version with a predicate argument) holds. Invalidates only the iterators and references to the erased elements. [26.3.9.6/16]All Sequence Containers
:clear
invalidates all references, pointers, and iterators referring to the elements of a and may invalidate the past-the-end iterator (Table 87 — Sequence container requirements). But forforward_list
,clear
does not invalidate past-the-end iterators. [26.3.9.5/32]All Sequence Containers
:assign
invalidates all references, pointers and
iterators referring to the elements of the container. Forvector
anddeque
, also invalidates the past-the-end iterator. (Table 87 — Sequence container requirements)
Associative Containers
All Associative Containers
: Theerase
members shall invalidate only iterators and references to the erased elements [26.2.6/9]All Associative Containers
: Theextract
members invalidate only iterators to the removed element; pointers and references to the removed element remain valid [26.2.6/10]
Container Adaptors
stack
: inherited from underlying containerqueue
: inherited from underlying containerpriority_queue
: inherited from underlying container
General container requirements relating to iterator invalidation:
Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container. [26.2.1/12]
no
swap()
function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. [ Note: The end() iterator does not refer to any element, so it may be invalidated. —end note ] [26.2.1/(11.6)]
As examples of the above requirements:
transform
algorithm: Theop
andbinary_op
functions shall not invalidate iterators or subranges, or modify elements in the ranges [28.6.4/1]accumulate
algorithm: In the range [first, last],binary_op
shall neither modify elements nor invalidate iterators or subranges [29.8.2/1]reduce
algorithm: binary_op shall neither invalidate iterators or subranges, nor modify elements in the range [first, last]. [29.8.3/5]
and so on...
Do STL iterators guarantee validity after collection was changed?
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
(includingpush_front
andpush_back
) invalidates all iterators that refer to adeque
.Erase
in the middle of adeque
invalidates all iterators that refer to thedeque
.Erase
at the beginning or end of adeque
(includingpop_front
andpop_back
) invalidates an iterator only if it points to the erased element. [2]
List
s 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 amap
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 forset
,multiset
andmultimap
)
Can std::map move contained elements?
From the C++ standard: a std::map
is an associative container:
Class template map overview [map.overview]
A map is an associative container that supports unique keys...
The shown code uses the []
operator to modify the map, which is specified in terms of try_emplace()
:
26.4.4.3 map element access [map.access]
T& operator[](const key_type& x);
Effects: Equivalent to:
return try_emplace(x).first->second;
One of the requirements of all associative containers is that neither the insert nor the emplace members invalidate any existing iterators and references to the container, and erase invalidates only the affected elements:
26.2.6 Associative containers [associative.reqmts]
The insert and emplace 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.
In other words, your handle
remains valid, and is not affected by any other changes to the same map. Only actual removal from the map container invalidates any references or pointers, and only to the elements in the container that are affected by the erase.
Can a reference to an element inside an std::map be invalidated?
The iterator invalidation rule for associative containers (which std::map
is) says at [associative.reqmts]/9:
The insert and emplace 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.
So if one thread inserts an element, it won't affect any references to existing elements. But if it removes something, other threads may be borked. Some form of element-wise locking is in order, I'd say.
Related Topics
How to Append to a File with Fstream Fstream::App Flag Seems Not to Work
Writing X264 from Opencv 3 with Ffmpeg on Linux
Windows Named Pipe Support in Linux
How to Use External Dlls in Cmake Project
Getopt Fails to Detect Missing Argument for Option
Create Objects in Conditional C++ Statements
Xlib How Does This (Removing Window Decoration) Work
How to Check That I Didn't Break Anything When Refactoring
Can Someone Explain About Linux Library Naming
How to Perform Rgb->Yuv Conversion in C/C++
Pointer to Class Member as a Template Parameter
Import Nested Classes into Namespace - C++
Communicate with Codesys Program on a Linux-Based Wago Pfc200 Plc
Boost Interprocess Mutexes and Checking for Abandonment
Constructor with By-Value Parameter & Noexcept
Is Returning Local Static Object Thread Safe for Pre-C++11 Compilers
Dealing with Library Dependencies on Linux
How to Reproduce Tcp Protocol 3-Way Handshake with Raw Sockets Correctly