迭代器与指针(引用)的双插入失效

Question

基于 cplusplus.com 的引用

如果插入发生在序列的开头或结尾，则与此容器相关的所有迭代器都将失效，但指针和引用仍然有效，引用它们在调用之前引用的相同元素。

为什么插入到前端或结尾会使迭代器无效，而不是指针和引用？

Answer 1

基本上

，deque可以被认为是vector<array<T>*>。

换句话说，它由一个小的"索引"向量组成，其中包含指向一系列固定大小数组的指针。当您在双端的开头或结尾插入时，它会填充第一个/最后一个数组，然后在必要时添加另一个数组，因此它永远不需要移动现有元素。这就是为什么指针/引用不会失效的原因。

但是，由于此"索引"存储在类似向量中的内容中，因此在调整大小时可能会复制并重新分配它，因此每次将新数组添加到索引时，索引都可能复制到不同的内存位置。

迭代

器需要对容器有足够的了解，以便能够迭代它。换句话说，仅仅知道它当前指向的特定元素位于何处是不够的，它还需要知道它是哪个数组的一部分，以及索引在哪里，这样它才能找到下一个/上一个数组。

因此，冒着使"索引"无效的风险的操作也会使迭代器无效，因为虽然它们可能仍指向有效元素，但它们不再能够迭代整个双端座。

Answer 2

指针

仍然具有单个项目的正确内存地址，但是当您例如：

1. 获取指向序列开头的迭代器
2. 将新项目引入前面

你还有一个指向开头的迭代器吗？在此示例中，您将错过输出中的数字 5：

#include <deque>
#include <iostream>
using namespace std;
int main()
{
    deque<int> d;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    deque<int>::iterator it=d.begin();
    d.push_front(5);
    for(;it!=d.end();++it)
    {
        cout << *it << endl;
    }
}