c++ - C++ 中的容器失效是什么意思？

Question

我今天了解到 C++ 容器上下文中的术语 invalidation。谁能解释一下是什么意思？

在容器上循环时，似乎不允许以某种方式修改容器的元素。但究竟是什么方式呢？

请帮助我理解这个主题。

谢谢，Boda Cydo。

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 容器的文档应该描述在什么情况下迭代器失效将会或可能发生。