Categories
c++ c++-faq c++-standard-library iterator

Iterator invalidation rules for C++ containers

595

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.)

2

  • Should the answers be in the same format as your answer?

    – P.W

    Jan 1, 2019 at 11:58

  • @P.W IMO that would be preferred for symmetry but I can’t enforce it 😛

    Jan 1, 2019 at 17:24

173

+250

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…

5

  • 2

    @LightnessRacesinOrbit: Tried to do it as per your original answer format. 🙂

    – P.W

    Jan 2, 2019 at 10:56

  • 1

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

    – sp2danny

    Jan 18, 2019 at 12:16

  • 1

    @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.

    – P.W

    Jan 18, 2019 at 12:53

  • @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?

    – Rick

    Dec 10, 2019 at 2:17


  • @Rick: Recommended reading: “What is iterator invalidation?”

    Dec 10, 2019 at 11:17


371

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.

20

  • Beside swap(), what’s the rules for iterator validity upon copy/move assignment?

    Mar 8, 2014 at 2:35

  • @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.

    Mar 8, 2014 at 11:17

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

    Mar 8, 2014 at 11:22


  • 1

    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)?

    Sep 10, 2014 at 21:35


  • 2

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

    – einpoklum

    Jan 10, 2016 at 17:28

173

+250

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…

5

  • 2

    @LightnessRacesinOrbit: Tried to do it as per your original answer format. 🙂

    – P.W

    Jan 2, 2019 at 10:56

  • 1

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

    – sp2danny

    Jan 18, 2019 at 12:16

  • 1

    @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.

    – P.W

    Jan 18, 2019 at 12:53

  • @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?

    – Rick

    Dec 10, 2019 at 2:17


  • @Rick: Recommended reading: “What is iterator invalidation?”

    Dec 10, 2019 at 11:17