27

正如标题所问。

我对双端队列的理解是它分配了“块”。我看不出分配更多空间如何使迭代器无效，如果有的话，人们会认为双端队列的迭代器比向量的迭代器有更多的保证，而不是更少。

4

7 回答 7

21

C++ 标准没有指定如何实现双端队列。不需要通过分配一个新块并将其链接到以前的块来分配新空间，所需要的只是在每一端的插入被摊销恒定时间。

因此，虽然很容易看到如何实现双端队列以提供您想要的保证[*]，但这并不是唯一的方法。

[*] 迭代器有一个元素的引用，加上它所在的块的引用，这样当它们到达它们时，它们可以继续向前/向后离开块的末端。另外，我假设对双端队列本身的引用，因此operator+对于随机访问迭代器而言，它可以是常数时间——遵循从块到块的链接链还不够好。

于 2009-05-27T00:16:52.763 回答
15

更有趣的是，它push_back不会push_front使对双端队列元素的任何引用无效。只有迭代器被假定为无效。

据我所知，该标准没有说明原因。但是，如果实现了一个知道其直接邻居的迭代器 - 作为一个列表 - 如果它指向一个同时位于双端队列边缘和块边缘的元素，则该迭代器将变得无效。

于 2009-05-27T04:07:53.483 回答
7

我猜。push_back/push_front可以分配一个新的内存块。双端队列迭代器必须知道递增/递减运算符何时应该跳转到下一个块。该实现可以将该信息存储在迭代器本身中。在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;
        }
    }
}
于 2011-03-18T04:08:19.787 回答
6

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

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

于 2009-05-26T23:00:14.273 回答
4

迭代器不仅仅是对数据的引用。它必须知道如何增加等。

为了支持随机访问，实现将有一个指向块的动态指针数组。deque 迭代器将指向这个动态数组。当双端队列增长时，可能需要分配一个新块。动态数组将增长，使其迭代器失效，从而使双端队列的迭代器失效。

所以不是块被重新分配，而是指向这些块的指针数组可以。事实上，正如 Johannes Schaub 所指出的，引用并没有失效。

还要注意，双端队列的迭代器保证不小于向量的，当容器增长时它们也会失效。

于 2016-09-09T22:07:18.320 回答
2

即使您以块的形式分配，如果没有足够的空间（如向量的情况），插入也会导致该特定块被重新分配。

于 2009-05-26T22:31:02.600 回答
0

因为标准说可以。它不要求将双端队列实现为块列表。它要求具有特定前置条件和后置条件以及特定算法复杂度最小值的特定接口。

实现者可以自由地以他们选择的任何方式来实现它，只要它满足所有这些要求。一个明智的实现可能会使用块列表，或者它可能会使用其他一些具有不同权衡的技术。

对于所有情况下的所有用户来说，可能不可能说一种技术绝对优于另一种技术。这就是为什么该标准给了实现者一些选择的自由。

于 2010-04-02T14:14:43.617 回答