Why std :: vector :: insert invalidates all iterators after the insertion point

Question

When insert entry in std::vector , the C ++ standard ensures that all iterators up to the insertion point remain valid until capacity is exhausted (see [23.2.4.3/1] or std :: vector for canceling an iterator ).

What is the reason why iterators after the entry point remains valid (if the capacity is not exhausted)? Of course, they would then point to another element, but (from the proposed implementation of std::vector ) it would still be possible to use such an iterator (for example, dereference it or increase it).

Answer 1

The fact that iterators can refer to another element is sufficient for their invalidity. The iterator is supposed to refer to the same element for its actual lifetime.

You are right that in practice you may not experience any glitches or nasal demons if you want to dereference such an iterator, but this does not make it valid.

Answer 2

You seem to think of the “invalid” iterator as something that might cause a crash when using, but the standard definition is wider. It includes the possibility that the iterator can be dereferenced safely, but no longer indicates the element to which it should refer. (This is a special case of observing that “undefined behavior” does not mean that “your program immediately crashes”, it may also mean that “your program will silently calculate the wrong result” or even “nothing observable will happen incorrectly on this implementation. ")

It is easier to demonstrate why this is a problem with erase :

 #include <vector> #include <iostream> int main(void) { std::vector<int> a { 0, 1, 2, 3, 4, 4, 6 }; for (auto p = a.begin(); p != a.end(); p++) // THIS IS WRONG if (*p == 4) a.erase(p); for (auto p = a.begin(); p != a.end(); p++) std::cout << ' ' << *p; std::cout << '\n'; } 

In typical C ++ implementations, this program will not crash, but it will print 0 1 2 3 4 6 , and not 0 1 2 3 6 , as possible, because erasing the first 4 invalid p is by moving it along the second 4 .

Your C ++ implementation may have a special "debugging" mode in which this program will work at startup. For example, with GCC 4.8:

 $ g++ -std=c++11 -W -Wall test.cc && ./a.out 0 1 2 3 4 6 

but

 $ g++ -std=c++11 -W -Wall -D_GLIBCXX_DEBUG test.cc && ./a.out /usr/include/c++/4.8/debug/safe_iterator.h:307:error: attempt to increment a singular iterator. Objects involved in the operation: iterator "this" @ 0x0x7fff5d659470 { type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPiNSt9__cxx19986vectorIiSaIiEEEEENSt7__debug6vectorIiS6_EEEE (mutable iterator); state = singular; references sequence with type `NSt7__debug6vectorIiSaIiEEE' @ 0x0x7fff5d659470 } Aborted 

Understand that the program provokes undefined behavior anyway. The fact is that the consequences of undefined behavior are more dramatic in debug mode.

Answer 3

A vector grows dynamically, so when you click on a vector, if there is no space for an element, it needs to allocate memory. The standard provides that vector should store its elements in contiguous memory, so when the memory is allocated, it should be enough to save ALL existing elements, as well as new.

Vector does not know about any iterators for itself, therefore it cannot update them in the new element store. Therefore, iterators are not valid after memory redistribution.

Answer 4

The vector does not know which iterators exist. However, the memory location of the elements after the inserted element has changed. This means that iterators must be updated to reflect this change if they remain valid. But the vector cannot perform this update because it does not know which iterators exist.