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...
std::vector iterator invalidation
after erasing an element, is the iterator at that position still valid
No; all of the iterators at or after the iterator(s) passed to erase
are invalidated.
However, erase
returns a new iterator that points to the element immediately after the element(s) that were erased (or to the end if there is no such element). You can use this iterator to resume iteration.
Note that this particular method of removing odd elements is quite inefficient: each time you remove an element, all of the elements after it have to be moved one position to the left in the vector (this is O(n2)). You can accomplish this task much more efficiently using the erase-remove idiom (O(n)). You can create an is_odd
predicate:
bool is_odd(int x) { return (x % 2) == 1; }
Then this can be passed to remove_if
:
vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd), vec.end());
Vector iterator invalidation after inserting
First of all. STL iterators are the same insecure as pointers. Good or bad, this is so. We cannot change this. This means that you need to be careful when you are working with iterators.
Now what happens behind the scenes. Both iterators are essentially pointers. First one points to the current beginning of the vector body, the second one to the current end of the vector body. During insertion vector is allowed to move body of the vector to some other place. If vector will move the body, your iterator end
will continue pointing to the same place. Even if vector will not move the beginning of the vector (sometimes this happens), your iterator will point to the last valid element (not after that last one as it should in normal case). Again, this will not be what you are expecting.
What is written above is just for understanding. You should never use this knowledge. You should check what actions invalidate what types of iterators and base your code only on what is explicitly allowed in the documentation.
Why std::vector iterator is invalidated after the erase() call?
One of the principles on which the conceptual idea of iterator is built, is as follows: as long as iterator remains non-aliased, dereferenceable and non-modified, it should refer to the same entity. In other words, dereferencing the same iterator multiple times should yield the same value. Algorithms that use iterators may rely on that.
What you proposing would result in an iterator that would "magically" change the value it refers to even though the iterator itself remains unchanged. This is not acceptable within the conceptual idea of iterator.
On the second thought, what I said above is obviously flawed in a sense that we can always apply some modifying operation to the vector that shifts elements around (e.g. std::random_shuffle
). Such operation would not invalidate any iterators, but would easily change the values the iterators refer to. How is that different from element shifting triggered by erase
? It isn't.
Why is vector::iterator invalidated upon reallocation?
Just to add a citation to the performance-related justification: when designing C++, Stroustrup thought it was vital that template classes like std::vector approach the performance characteristics of native arrays:
One reason for the emphasis on run-time efficiency...was that I wanted
templates to be efficient enough in time and space to be used for
low-level types such as arrays and lists....
Higher-level alternatives -- say, a range-checked array with a size()
operation, a multidimensional array, a vector type with proper numeric
vector operations and copy semantics, etc. -- would be accepted by
users only if their run-time, space, and notational convenience
approached those of built-in arrays.In other words, the language mechanism supplying parameterized types
should be such that a concerned user should be able to afford to
eliminate the use of arrays in favor of a standard library class.
Bjarne Stroustrup, Design and Evolution of C++, p.342.
Does modifying a std::vector invalidate an iterator?
std::vector::push_back
invalidates all iterators on that vector if the new vector size is greater than the previous capacity. (The reason is due to the reallocation of the vector).
The behaviour of using an invalidated iterator is undefined.
std::list::push_back
does not invalidate any iterators.
Past-the-end iterator invalidation in C++11
My question is about all containers:
- In C++11, are there any container operations that may invalidate a past-the-end iterator, and where this behavior is ambiguous in the
language specification?
I am not sure what you mean with "where this behavior is ambiguous in the language specification", but there certainly are operations that invalidate past-the-end operators (like insert into a std::vector
or std::string
).
Said differently,
- Can I trust the validity of a past-the-end iterator after performing a container operation that does not say it may invalidate
the past-the-end iterators?
You can trust the past-the-end iterator like any other iterator: Any operation that does not (potentially) invalidate iterators won't invalidate them. Except for the possibility of the standard sporting a bug, that is all operations where it doesn't say that they (potentially) invalidate operators.
Does std::vector::reserve guarantee that the implementation will not invalidate iterators in this case?
As long as you don't exceed preallocated capacity no reallocation should happen and no references or iterators referring to vector items should get invalidated. However since iterator returned by end()
does not refer to any vector items it may still get invalidated.
23.3.11.3 vector capacity [vector.capacity]
- ...No reallocation shall take place during insertions that happen after a call to
reserve()
until the time when an insertion would make the size of the vector greater than the value ofcapacity()
...
23.3.11.5 vector modifiers [vector.modifiers]
- ...If no reallocation happens, all the iterators and references before the insertion point remain valid.
Related Topics
When Should You Use the "This" Keyword in C++
Using Std::Bind with Member Function, Use Object Pointer or Not for This Argument
How to Overload the Operator++ in Two Different Ways for Postfix A++ and Prefix ++A
Difference Between Rdtscp, Rdtsc:Memory and Cpuid/Rdtsc
How to Use Source_Location in a Variadic Template Function
How to Get the Real and Total Length of Char * (Char Array)
Return a "Null" Object If Search Result Not Found
How to Get the Gl Library/Headers
How to Safely Use Openmp with C++11
Passing Integers as Constant References Versus Copying
How to Erase Elements from Stl Containers
Opencv Multi Channel Element Access
Modifying a Char *Const String
Is Reading an Indeterminate Value Undefined Behavior
How to Test Whether a C++ Class Has a Default Constructor (Other Than Compiler-Provided Type Traits)