为什么push_back或push_front使deque的迭代器无效？

Question

正如标题所要求的那样.

我对双端队列的理解是它分配了"块".我没有看到如何分配更多的空间使迭代器无效,如果有的话,人们会认为deque的迭代器比矢量更有保证,而不是更少.

Answer 1

C++标准没有规定deque的实现方式.不需要通过分配新的块并将其链接到先前的块来分配新的空间,所需要的只是在每一端的插入是分摊的常量时间.

因此,虽然很容易看到如何实现deque以便它提供您想要的保证[*],但这不是唯一的方法.

[*]迭代器具有对元素的引用,以及对它所在块的引用,以便它们在到达时可以继续向前/向后退出块的末尾.另外,我假设对deque本身的引用,因此operator+对于随机访问迭代器可以是预期的常量时间 - 从块到块之间的链接链不够好.

Answer 2

更有趣的是,push_back和push_front将不会作废任何引用到一个deque的元素.只有迭代器才被认为是无效的.

据我所知,标准没有说明原因.但是,如果一个迭代开始实施,这些人知道它的近邻 - 作为一个清单 - 这个迭代将成为无效的,如果它指出,这是无论是在双端队列的边缘和块的边缘的元素.

Answer 3

关键是不做任何假设只是将迭代器视为无效.

即使它现在工作正常,编译器的更高版本或不同平台的编译器可能会出现并破坏您的代码.或者,同事可能会出现并决定将您的双端队列转换为向量或链接列表.

Answer 4

我猜.push_back/push_front可以分配新的内存块.deque迭代器必须知道递增/递减运算符何时应跳转到下一个块.实现可以将该信息存储在迭代器本身中.在push_back/push_front之后递增/递减旧迭代器可能无法按预期工作.

此代码可能会或可能不会因运行时错误而失败.在我的Visual Studio上,它在调试模式下失败,但在发布模式下运行结束.在Linux上它导致了分段错误.

#include <iostream>
#include <deque>

int main() {
    std::deque<int> x(1), y(1);
    std::deque<int>::iterator iterx = x.begin();
    std::deque<int>::iterator itery = y.begin();

    for (int i=1; i<1000000; ++i) {
        x.push_back(i);
        y.push_back(i);
        ++iterx;
        ++itery;
        if(*iterx != *itery) {
            std::cout << "increment failed at " << i << '\n';
            break;
        }
    }
}