Что означает недействительность контейнера в C++?

Question

Я узнал сегодня о сроке invalidation в контексте контейнеров C++. Кто-нибудь может объяснить, что это значит?

Кажется, что вы не можете каким-либо образом изменять элементы контейнера при циклическом перемещении по контейнеру. Но каким именно образом?

Пожалуйста, помогите мне понять эту тему.

Спасибо, Бода Кидо.

Answer 1

Контейнеры не становятся недействительными - итераторы, ссылающиеся на элементы в контейнерах, становятся недействительными.

Итератор - это дескриптор определенного элемента в контейнере. Итератор действителен до тех пор, пока этот элемент остается внутри контейнера, и контейнер не перестраивается внутри себя. Итератор становится недействительным, когда происходит одна из этих двух вещей, поскольку после слов итератор больше не является допустимым в качестве дескриптора в контейнере.

Самый очевидный способ сделать недействительным итератор - удалить его элемент из коллекции, например:

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

Более тонкий способ аннулировать итератор состоит в том, чтобы заставить контейнер внутренне переставить себя (например, перераспределить его внутреннее хранилище). Это может быть сделано, например, путем расширения определенных типов контейнеров:

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

Вы можете предотвратить это в некоторых контейнерах, предварительно зарезервировав пространство:

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

Документация для каждого контейнера STL должна описывать, при каких обстоятельствах будет или может произойти недействительность итератора.

Answer 2

Некоторые итераторы становятся недействительными, когда базовый контейнер изменяется определенным образом.

Например: vector итераторы становятся недействительными при изменении размера контейнера. list итераторы становятся недействительными, когда базовые данные удаляются.

Это означает, что итератор больше не действителен. Попытки разыменования могут вызвать исключения или неопределенное поведение. Попытки манипулировать им не гарантированы.

Answer 3

Я думаю, что это все об аннулировании итератора. Там несколько примеров:

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

Если у вас есть массив (или список) объектов, и вы зацикливаете их, то удаляете некоторые элементы - тогда простой индекс в массиве может быть недействительным, но итераторы все равно будут.