Сегодня я узнал о термине invalidation в контексте контейнеров C++. Кто-нибудь может объяснить, что это значит?
Похоже, вам не разрешено каким-либо образом изменять элементы контейнера при циклическом просмотре контейнера. Но каким именно образом?
Пожалуйста, помогите мне понять эту тему.
Спасибо, Бода Сидо.
Контейнеры не становятся недействительными — итераторы, ссылающиеся на элементы в контейнерах, становятся недействительными.
Итератор — это дескриптор определенного элемента внутри контейнера. Итератор действителен до тех пор, пока этот элемент остается внутри контейнера, а контейнер не перестраивается внутри себя. Итератор становится недействительным, когда происходит одна из этих двух вещей, поскольку после слов итератор больше не действует как дескриптор контейнера.
Самый очевидный способ сделать итератор недействительным — это удалить его элемент из коллекции, например:
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 должно быть описано, при каких обстоятельствах произойдет или может произойти аннулирование итератора.
std::deque вставка в начало может сделать недействительными итераторы, оставив действительными ссылки и указатели на содержащиеся элементы. Прочитайте документы для каждого контейнера/операции.
- person David Rodríguez - dribeas; 27.07.2010
Некоторые итераторы становятся недействительными, когда базовый контейнер изменяется определенным образом.
Например: vector итераторы становятся недействительными при изменении размера контейнера. list итераторы становятся недействительными при удалении базовых данных.
Это означает, что итератор больше недействителен. Попытки разыменовать его могут вызвать исключения или поведение undefined. Попытки манипулировать им не гарантированно сработают.
Если бы у вас был массив (или список) объектов, и, перебирая их, вы удалили некоторые элементы, тогда простой индекс в массиве может быть недействительным, но итераторы все равно будут.
Я думаю, что все дело в аннулировании итератора. Там несколько примеров:
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);
}
