What does container invalidation in C++ mean?

Question

I learned today about the term invalidation in context of C++ containers. Can anyone explain what it means?

It seems like you're not allowed to modify elements of a container in some way when looping over the container. But what way exactly?

Please help me understand this topic.

Thanks, Boda Cydo.

Answer 1

If you had an array (or list) of objects and looping over them you deleted some items - then a simple index into the array might not be valid, but iterators still would be.

Answer 2

Certain iterators become invalidated when the underlying container changes in a certain way.

For example: vector iterators are invalidated when the size of the container changes. list iterators are invalidated when the underlying data is deleted.

This means that the iterator is no longer valid. Attempts to dereference it may cause exceptions or undefined behavior. Attempts to manipulate it are not guaranteed to work.

Answer 3

I think it is all about iterator invalidating. There few examples :

std::vector<int> v1(10);
std::vector<int> v2(11);
//1
for (std::vector<int>::iterator it = v1.begin(); it != v2.end(); ++it);
//2
for (std::vector<int>::iterator it = v1.begin(); it != v1.end(); ++it)
{
    v1.erase(it);
}

Answer 4

Containers don't become invalidated -- iterators referring to elements in containers become invalidated.

An iterator is a handle to a particular item within a container. The iterator is valid so long as that item remains inside the container, and the container does not internally rearrange itself. An iterator is invalidated when one of those two things happens, since afterwords the iterator is no longer valid as a handle into the container.

The most obvious way to invalidate an iterator is to remove its referred-to item from the collection, e.g.:

std::set<int> s;

s.insert(4);
s.insert(2);

std::set<int>::iterator itr = s.find(4); // itr is a handle to 4

std::cout << *itr << std::endl; // prints 4

s.erase(4); // removes 4 from collection, invalidates itr

std::cout << *itr << std::endl; // undefined behavior

The more subtle way to invalidate an iterator is to cause the container to internally rearrange itself (e.g. reallocate its internal storage). This can be done, for example, by causing certain types of containers to expand:

std::vector<int> v;

v.push_back(4);
v.push_back(2);

std::vector<int>::iterator itr = v.begin(); // itr is a handle to 4

std::cout << *itr << std::endl; // prints 4

v.push_back(12); // MIGHT invalidate itr, if v expands its internal allocation

You can prevent this in some containers by pre-reserving space:

std::vector<int> v;

v.reserve(3); // Pre-allocate 3 elements

v.push_back(4);
v.push_back(2);

std::vector<int>::iterator itr = v.begin(); // itr is a handle to 4

std::cout << *itr << std::endl; // prints 4

v.push_back(12); // WILL NOT invalidate itr, since it will never cause v to expand

The documentation for each STL container should describe under what circumstances iterator invalidation will or might occur.