C++中的容器失效意味着什么？

Question

我今天invalidation在C++容器的上下文中学到了这个术语.任何人都可以解释它的含义吗？

在循环容器时,似乎不允许以某种方式修改容器的元素.但到底是什么方式？

请帮我理解这个话题.

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