调整向量大小会使迭代器失效吗？

StackOverflow https://stackoverflow.com/questions/1624803

  •  06-07-2019
  •  | 
  •  

题

我发现这个C++代码：

vector<int> a;
a.push_back(1);
a.push_back(2);
vector<int>::iterator it = a.begin();
a.push_back(4);
cout << *it;

打印一些大的随机数；但如果你添加 a.push_back(3) 在第 3 行和第 4 行之间，它将打印 1。你能给我解释一下吗？

有帮助吗？

解决方案

用更谨慎的措辞编辑

是的，调整向量大小可能会使指向向量的所有迭代器无效。

通过在内部分配存储数据的数组来实现向量。当向量增长时，该数组可能会用完空间，当它出现时，向量会分配一个更大的新数组，将数据复制到该数组，然后删除旧数组。

因此，指向旧内存的旧迭代器不再有效。 但是，如果向量向下（例如通过 pop_back（））调整大小，则使用相同的数组。数组永远不会自动缩小尺寸。

避免这种重新分配（和指针失效）的一种方法是首先调用 vector :: reserve（），留出足够的空间以便不需要这种复制。在你的情况下，如果你在第一个 push_back（）操作之前调用 a.reserve（3），那么内部数组就足够大了 push_back 可以在不重新分配数组的情况下执行，因此迭代器将保持有效。

其他提示

向量迭代器仅在向量执行重新分配时失效。

对 push_back（4）的调用导致向量分配新的内存块 - 这就是导致迭代器失效。当您还使用 push_back（3）时，不会对 push_back（4）执行重新分配，因此迭代器仍然有效。

是的，任何可能改变向量大小的操作都会使迭代器失效。

编辑：包括减少容器大小的操作（例如 erase（）， resize（））。 erase（）不会使所有迭代器无效，但它会使任何引用擦除元素之后的任何点的迭代器无效。 resize（）是根据 insert（）和 erase（）定义的，因此具有相同的潜力。

迭代器失效的规则特定于容器。

现在，失效对于向量来说可能有两种含义：

  1. 无效 = 点超出 [begin,end] 定义的范围
  2. 无效=指向与原始对象不同的对象

正如您所看到的，第二个要严格得多：

std::vector<int> myVector;
myVector.push_back(0);
myVector.push_back(1);

std::vector<int>::iterator it = myVector.begin(); // it points to 0
myVector.erase(it); // it points to 1
myVector.erase(it); // it == myVector.end()

在这种情况下，它是“有效的”，因为它始终在包含范围 [begin,end] 内，因此可以安全地用于 myVector 上的任何操作。另一方面，表达式 (*it) 不断变化：首先它返回 0，然后返回 1，然后它有未定义的行为......

一般来说，人们更愿意谈论第二个要求，而使迭代器无效仅仅意味着 (*it) 可能不会产生与以前相同的结果。

话虽如此，有几种方法可以使 Vector 上的迭代器无效（事实上，它是 STL 中不太稳定的结构）。

添加元素期间：

  • 这可能会触发 重新分配 (1) if myVector.size() == myVector.capacity()，由于检查这个容易出错，我们通常认为任何添加都会使迭代器失效
  • 如果你想“挑剔”并且知道重新分配没有被触发，那么你仍然需要担心 insert. 。插入元素会使指向当前位置和所有后续位置的迭代器无效，因为元素会向向量末尾移动一步。

删除元素期间：

  • 即使缓冲区现在比需要的大得多，也不会重新分配。不过，可以使用以下方法强制执行此操作 缩小以适合 成语（2）。
  • 所有指向已删除元素之后的迭代器都将失效。特别是，之前的“end”迭代器现在超出了 [begin,end] 范围，并且无法在 STL 算法中安全使用。

(1) std::vector 的内部结构是 T 的数组，这是由于与 C 程序的兼容性（使用 &myVector.front() 作为数组的地址），并且因为它保证了连续性和最小值空间开销（即向量自身数据占用的空间量 vs 对象占用的空间量）

任何时候，您都可以使用 .capacity() 方法知道一个向量可以容纳多少个对象。

当您想要插入一个对象并且向量没有必要的容量时，会触发对 .reserve(size_t) 方法的调用。此方法，如果所需的项目数量超过当前容量，则会触发 重新分配.

然后向量分配一个新的元素数组（其大小通常为 2*n+1，其中 n 是当前容量），将当前数组的元素复制到新数组，丢弃当前数组。

因为它会丢弃当前数组，所以您的迭代器将失效，因为向量迭代器通常是简单的指针（为了提高效率）。

请注意，如果迭代器实现为：对向量的引用 + 计数，取消引用实际上是 *(&m_vector.front() + n) 重新分配不会使它们无效......但他们的效率会较低。

(2) 收缩以适合：警告，这会触发元素的复制并使迭代器无效。

// myVector has 10 elements, but myVector.capacity() == 1000
myVector.swap(std::vector<int>(myVector));

它首先创建一个临时向量，该向量将仅分配所需的内存（最小值取决于库），并复制 myVector 的元素。然后，交换操作交换 myVector 和此副本中的缓冲区，因此 myVector 现在占用所需内存量最少的缓冲区。操作结束时，临时对象将被销毁，并释放其所持有的内存。

为了将来参考，像这样的所有STL类别的花絮都在SGI的网站上： http://www.sgi.com/tech/stl/Vector.html

如果在添加或删除集合后需要迭代器保持有效，请查看另一种集合，如列表。

最好的办法是从集合中识别出你想要的特征矩阵（随机访问等），然后选择合适的容器。

有关起点，请参阅有关Standard_Template_Library容器的维基百科文章。如果您有现金，我强烈推荐Scott Meyer的“有效STL：50种改进您使用标准模板库的具体方法”。

对于缺乏支持链接的抱歉，我在这里是一个新手，并且缺少与多个人发布此信息的声誉。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top