Iterator invalidation rules for C++ containers

Question

What are the iterator invalidation rules for C++ containers?

_{(Note: This Q&A is an entry in Stack Overflow's C++ FAQ. Meta-discussion about the question itself should be posted on the Meta question that started all of this, not here.)}

Churrigueresque

Should the answers be in the same format as your answer? – Enduring

@Enduring IMO that would be preferred for symmetry but I can't enforce it :P – Fouquiertinville

Answer 1

C++17 (All references are from the final working draft of CPP17 - n4659)

---

Insertion

Sequence Containers

• vector: The functions insert, 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 the reserve 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 to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity(). [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].
  The insert, emplace_front, emplace_back, emplace, push_front, push_back functions are covered under this rule.

• forward_list: None of the overloads of insert_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: The insert and emplace 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]
  The insert and emplace members shall not affect the validity of references to container elements, but may invalidate all iterators to the container. [26.2.7/14]
  The insert and emplace members shall not affect the validity of iterators if (N+n) <= z * B, where N 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, and z 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 to a will be invalidated, but iterators to elements remaining in a2 will remain valid. (Table 91 — Unordered associative container requirements)

Container Adaptors

• stack: inherited from underlying container
• queue: inherited from underlying container
• priority_queue: inherited from underlying container

---

Erasure

Sequence Containers

• vector: The functions erase and pop_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 a deque 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 a deque 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 a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque. [ Note: pop_front and pop_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 to erase, pop_front, pop_back, clear functions.
  remove and remove_if member functions: Erases all the elements in the list referred by a list iterator i 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 iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version of unique with no arguments) or pred(*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 and remove_if member functions - Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value (for remove()), pred(*i) is true (for remove_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) or pred(*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 for forward_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. For vector and deque, also invalidates the past-the-end iterator. (Table 87 — Sequence container requirements)

Associative Containers

• All Associative Containers: The erase members shall invalidate only iterators and references to the erased elements [26.2.6/9]

• All Associative Containers: The extract 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 container
• queue: inherited from underlying container
• priority_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: The op and binary_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...

Enduring

can we also have a listing for std::string? I think it's different from std::vector due to SSO – Tucana

@sp2danny: Due to SSO, string fails the second general requirement listed above. So I did not include it. Also tried to stick to the same pattern of the previous FAQ entries. – Enduring

@LightnessRaceswithMonica Thank you guys for the hard work. I have a question confusing me for days. What does "invalidated" exactly mean on these contexts? Does it mean "invalidated" can mean "no longer points to what it used to", not just "may not point to any valid element" as @Marshall Clow described in this answer ? Or it just indicates only 1 of the 2 condtions? – Labors

@Rick: Recommended reading: "What is iterator invalidation?" – Fouquiertinville

Answer 2

C++03 (Source: Iterator Invalidation Rules (C++03))

---

Insertion

Sequence containers

• vector: all iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated) [23.2.4.3/1]
• deque: all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected) [23.2.1.3/1]
• list: all iterators and references unaffected [23.2.2.3/1]

Associative containers

• [multi]{set,map}: all iterators and references unaffected [23.1.2/8]

Container adaptors

• stack: inherited from underlying container
• queue: inherited from underlying container
• priority_queue: inherited from underlying container

---

Erasure

Sequence containers

• vector: every iterator and reference after the point of erase is invalidated [23.2.4.3/3]
• deque: all iterators and references are invalidated, unless the erased members are at an end (front or back) of the deque (in which case only iterators and references to the erased members are invalidated) [23.2.1.3/4]
• list: only the iterators and references to the erased element is invalidated [23.2.2.3/3]

Associative containers

• [multi]{set,map}: only iterators and references to the erased elements are invalidated [23.1.2/8]

Container adaptors

• stack: inherited from underlying container
• queue: inherited from underlying container
• priority_queue: inherited from underlying container

---

Resizing

• vector: as per insert/erase [23.2.4.2/6]
• deque: as per insert/erase [23.2.1.2/1]
• list: as per insert/erase [23.2.2.2/1]

---

Note 1

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. [23.1/11]

Note 2

It's not clear in C++2003 whether "end" iterators are subject to the above rules; you should assume, anyway, that they are (as this is the case in practice).

Note 3

The rules for invalidation of pointers are the sames as the rules for invalidation of references.

Fouquiertinville

Good idea, just to remark: I think that the associative containers could be folded together in a single line, and it could be worth then adding another line of the unordered associative ones... though I am not sure how the rehashing part could be mapped on insert/erase, do you know of a way to check whether a rehash will be triggered or not ? – Sumptuous

@Matthieu: There's certainly scope here for a bit of C++0x magic. The associative containers were originally semi-folded together, but Martinho changed that and I don't entirely disagree with him. – Fouquiertinville

I changed it because the way it was originally (with '' meaning "same as above") it looked a bit weird and confusing. I didn't think of placing them in a single line :( @Matthieu: Unless the containers provide a means to check it, there's no way to know if a rehash will happen. – Carduaceous

I prefer to see the rules itemised by container. That's the point of this FAQ entry. I don't want prose bundled together. – Fouquiertinville

@Tomalak, @Martinho: unfolded is fine with me :) And the more I think about it the more I fear that for the unordered we may have to consider that all insert/erase potentially invalidate references. They expose the number of buckets, so perhaps we would be able to check a posteriori. – Sumptuous

IIRC, somewhere the spec says that the end iterator is not an iterator "to objects within that container". I wonder how those guarantees look for the end iterator in each case? – Rambow

@Johannes: #6440892 – Fouquiertinville

how can insertion to vector leave all iterators unaffected, even if there was no reallocation? Insertion must shift some elements, vector is guaranteed to be contiguous, so...? Or do you refer to back insertion only? – Subito

@davka: The idea is that, if you have an iterator, the iterator being invalidated is not the same as the iterator suddenly pointing to a different, valid, element. Invalidation != "Modification". – Fouquiertinville

do you have any reference supporting that? I don't see much difference. Perhaps the program would not crash, but the algorithm would be wrong, which is arguably even worth – Subito

@davka: In fact of course it's only iterators and references before the insertion point that remain valid; fixing. However note that swap() does not invalidate iterators [23.1/10], even though the result will be that they essentially now point to different elements. – Fouquiertinville

It is not exactly "unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)", instead, it should be "greater than the size specified in the most recent call to reserve()". This is one thing that C++03 differs from C++11. In C++03, once an insert() causes the size of the vector to reach the the value specified in the previous reserve() call (which could well be smaller than the current capacity()), any subsequent insert() could cause reallocation and invalidate all the iterators. In C++11, it won't. – Kinase

Is there a point in listing the container adapters? They don't provide iterators, so they don't really have invalidation rules. – Microgroove

@SebastianRedl: I only included them because I envision people referring to this list from the point of view of the containers they're using, not the containers that exist, and it's easy to forget that those adaptors are adaptors. This way, that fact is right there in front of you, perhaps saving someone a few moments trying to figure out why I'd forgotten about them. – Fouquiertinville

in fact resizing is not as insertion/erasure, as " If the container expands, the end iterator is invalidated and, if it has to reallocate storage, all iterators, pointers and references related to this container are also invalidated." In fact this is a main argument Rust Language proved with the insafety of C++, and they developed their language to fix problem like this without using Garabge Collection as other languages fixed this problem. see cplusplus.com/reference/vector/vector/resize and doc.rust-lang.org/nightly/book/README.html . – Homebody

@MuhammadAnnaqeeb: This answer admittedly doesn't make it clear, as I took a shortcut, but the intention is to say that resizing is insertion/erasure, as in if a reallocation is required, you may consider that to be the same as erasing then re-inserting all affected elements. That section of the answer could certainly be improved. – Fouquiertinville

"every iterator and reference after the point of erase is invalidated" -- clarify that "after" includes "at"? (and same below in C++11 case). – Alleyn

@Yakk: But it doesn't; see the cited standard text. Looks like that was fixed in C++11 though. :) – Fouquiertinville

How could deque insertion at an end or beginning invalidate iterators but not pointers/references? – Decolorant

@metamorphosis: deque stores data in non-contiguous blocks. Inserting at the beginning or end may allocate a new block, but it never moves around previous elements, so pointers remain valid. But the rules for going to the next/previous element change if a new block is allocated, so iterators are invalidated. – Jocundity

@Kundor - so what you're saying is, the beginning/end iterators get shifted - makes sense. Would that necessarily invalidate non-begin()/end() iterators though? – Decolorant

@metamorphosis: It depends if the increment/decrement operators on the iterator access information from the deque object, or keep their own internal copy, which the standard is probably trying to leave up to the implementation. In the latter case, the iterator might appear to work, up until you try to increment past the old endpoint, when it will claim to have exhausted the container or just break somehow. – Jocundity

Is there any evidence in the standard for Note 3? I cannot find any rule for invalidation of pointers referring to sequence containers. – North

@xskxzr: If a reference is invalidated then how is an equivalent pointer not going to be invalidated also? They are handles to the same object. By saying "iterators and references" The standard either relies on this fact, or relies on pointers being kinds of iterators, or both. – Fouquiertinville

Could you advise about the references like [23.2.4.3/3] ? Are these references to the C++ standard ? – Supportive

This is why I don't use C++ anymore, too complicated. – Confiteor

Answer 3

C++11 (Source: Iterator Invalidation Rules (C++0x))

---

Insertion

Sequence containers

• vector: all iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated) [23.3.6.5/1]
• deque: all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected) [23.3.3.4/1]
• list: all iterators and references unaffected [23.3.5.4/1]
• forward_list: all iterators and references unaffected (applies to insert_after) [23.3.4.5/1]
• array: (n/a)

Associative containers

• [multi]{set,map}: all iterators and references unaffected [23.2.4/9]

Unsorted associative containers

• unordered_[multi]{set,map}: all iterators invalidated when rehashing occurs, but references unaffected [23.2.5/8]. Rehashing does not occur if the insertion does not cause the container's size to exceed z * B where z is the maximum load factor and B the current number of buckets. [23.2.5/14]

Container adaptors

• stack: inherited from underlying container
• queue: inherited from underlying container
• priority_queue: inherited from underlying container

---

Erasure

Sequence containers

• vector: every iterator and reference at or after the point of erase is invalidated [23.3.6.5/3]
• deque: erasing the last element invalidates only iterators and references to the erased elements and the past-the-end iterator; erasing the first element invalidates only iterators and references to the erased elements; erasing any other elements invalidates all iterators and references (including the past-the-end iterator) [23.3.3.4/4]
• list: only the iterators and references to the erased element is invalidated [23.3.5.4/3]
• forward_list: only the iterators and references to the erased element is invalidated (applies to erase_after) [23.3.4.5/1]
• array: (n/a)

Associative containers

• [multi]{set,map}: only iterators and references to the erased elements are invalidated [23.2.4/9]

Unordered associative containers

• unordered_[multi]{set,map}: only iterators and references to the erased elements are invalidated [23.2.5/13]

Container adaptors

• stack: inherited from underlying container
• queue: inherited from underlying container
• priority_queue: inherited from underlying container

---

Resizing

• vector: as per insert/erase [23.3.6.5/12]
• deque: as per insert/erase [23.3.3.3/3]
• list: as per insert/erase [23.3.5.3/1]
• forward_list: as per insert/erase [23.3.4.5/25]
• array: (n/a)

---

Note 1

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. [23.2.1/11]

Note 2

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 ] [23.2.1/10]

Note 3

Other than the above caveat regarding swap(), it's not clear whether "end" iterators are subject to the above listed per-container rules; you should assume, anyway, that they are.

Note 4

vector and all unordered associative containers support reserve(n) which guarantees that no automatic resizing will occur at least until the size of the container grows to n. Caution should be taken with unordered associative containers because a future proposal will allow the specification of a minimum load factor, which would allow rehashing to occur on insert after enough erase operations reduce the container size below the minimum; the guarantee should be considered potentially void after an erase.

Fouquiertinville

Beside swap(), what's the rules for iterator validity upon copy/move assignment? – Gastrectomy

@LightnessRacesinOrbit: Like insertion, erasure, resizing and swap, copy/move assignment are also member functions of std::vector, so I think you could provide the rules of iterator validity for them too. – Gastrectomy

@goodbyeera: You mean copy/move assigning an element? This will not affect any iterators. Why would it? You're hitting Note 1 above. – Fouquiertinville

@LightnessRacesinOrbit: Not the element. I mean copy/move assignment on a vector. – Gastrectomy

@goodbyeera: If you assign to a vector, you're replacing the vector. The original elements are removed. Clearly, then, all iterators are invalidated. – Fouquiertinville

@LightnessRacesinOrbit: I really doubt the conclusion could be this simple. Imagine copy-assign a vector to another one with the exact same size and capacity. – Gastrectomy

@goodbyeera: It's possible that your iterators will still "work" without crashing, but they are invalidated because this cannot be guaranteed in the general case. – Fouquiertinville

@LightnessRacesinOrbit: Any excerpts from the standard? – Gastrectomy

@LightnessRacesinOrbit: I can't find any spec for copy assignment in 23.2.3. I do find there a spec for the assignment of the form a=il; in which il designates an object of type initializer_list<value_type>, and it says:"Assigns the range [il.begin(),il.end()) into a. All existing elements of a are either assigned to or destroyed." For those elements got assigned but not destroyed (e.g. if destination and source has the exact same size and capacity), I really doubt their iterators are invalidated. This form of assignment at least can be comparable to the actual copy assignment. – Gastrectomy

@goodbyeera: Table 96. I suggest starting a new question if you wish to take this any further! – Fouquiertinville

@LightnessRacesinOrbit: Table 96 also says "all existing elements of a are either move assigned to or destroyed" for move-assignment, and specifies only one post-condition r==a for copy-assignment. I have already asked this as a separate question two days ago: #22253855 No reliable answer so far. You are welcome to provide an answer if you can find strong support from the standard. – Gastrectomy

And in another related question: #18468124 @JamesKanze mentions in one of the comments of the answer that, a copy/move assignment is not allowed to reduce the vector's capacity, and with a smaller-sized right hand side vector, the copy/move assignment shouldn't cause reallocation and invalidate the iterators of the remaining elements. – Gastrectomy

@LightnessRacesinOrbit: You may have a look at James Kanze's answer in #22253855 I don't know for sure if he's correct or not, but he does provide some strong points. – Gastrectomy

@LightnessRacesinOrbit you should probably mention the rules for things like reordering the elements (sorting on a list doesn't invalidate iterators to the elements since they point to the same elements that they did point before). – Savoyard

Regarding note-2: How does that work with small-string-optimization for std::basic_string<>? – Wineglass

@Wineglass Poorly, I'm afraid; since C++11, the SSO is effectively banned. – Fouquiertinville

I think I made an error, because std::basic_string does not seem to be counted as a container, and certainly not a container in the section of the standard that note applies to. Still, where does it say SSO is disallowed (I know COW is)? – Wineglass

Are these rules all the same in C++14? C++17 (as far as is now known)? – Halsy

@Deduplicator: I may have been thinking of COW. – Fouquiertinville

@SiddheshRane: Not quite but thanks anyway! – Fouquiertinville

Answer 4

It is probably worth adding that an insert iterator of any kind (std::back_insert_iterator, std::front_insert_iterator, std::insert_iterator) is guaranteed to remain valid as long as all insertions are performed through this iterator and no other independent iterator-invalidating event occurs.

For example, when you are performing a series of insertion operations into a std::vector by using std::insert_iterator it is quite possible that these insertions will trigger vector reallocation, which will invalidate all iterators that "point" into that vector. However, the insert iterator in question is guaranteed to remain valid, i.e. you can safely continue the sequence of insertions. There's no need to worry about triggering vector reallocation at all.

This, again, applies only to insertions performed through the insert iterator itself. If iterator-invalidating event is triggered by some independent action on the container, then the insert iterator becomes invalidated as well in accordance with the general rules.

For example, this code

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);

for (unsigned n = 20; n > 0; --n)
  *it_ins++ = rand();

is guaranteed to perform a valid sequence of insertions into the vector, even if the vector "decides" to reallocate somewhere in the middle of this process. Iterator it will obviously become invalid, but it_ins will continue to remain valid.

Lunsford

Answer 5

Here is a nice summary table from cppreference.com:

Here, insertion refers to any method which adds one or more elements to the container and erasure refers to any method which removes one or more elements from the container.

Peach

Answer 6

Since this question draws so many votes and kind of becomes an FAQ, I guess it would be better to write a separate answer to mention one significant difference between C++03 and C++11 regarding the impact of std::vector's insertion operation on the validity of iterators and references with respect to reserve() and capacity(), which the most upvoted answer failed to notice.

C++ 03:

Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes 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 size specified in the most recent call to reserve().

C++11:

Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes 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 of capacity().

So in C++03, it is not "unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)" as mentioned in the other answer, instead, it should be "greater than the size specified in the most recent call to reserve()". This is one thing that C++03 differs from C++11. In C++03, once an insert() causes the size of the vector to reach the value specified in the previous reserve() call (which could well be smaller than the current capacity() since a reserve() could result a bigger capacity() than asked for), any subsequent insert() could cause reallocation and invalidate all the iterators and references. In C++11, this won't happen and you can always trust capacity() to know with certainty that the next reallocation won't take place before the size overpasses capacity().

In conclusion, if you are working with a C++03 vector and you want to make sure a reallocation won't happen when you perform insertion, it's the value of the argument you previously passed to reserve() that you should check the size against, not the return value of a call to capacity(), otherwise you may get yourself surprised at a "premature" reallocation.

Kinase

However, I'd shoot any compiler who did this to me, and no jury in the land would convict me. – Alleyn

I didn't "fail to notice" this; it was an editorial error in C++03 that was corrected in C++11. No mainstream compiler takes advantage of the error. – Fouquiertinville

@Yakk I think gcc already invalidates iterators in such situations. – Hansel