C++ 中的双端队列到底是什么数据结构？

Question

C++ STL 中的双端队列是否应该实现特定的数据结构，或者双端队列只是一种可以从前面和后面增长的数组的模糊概念，无论实现选择如何实现？

我曾经总是假设双端队列是一个 循环缓冲区，但我最近正在阅读 C++ 参考< a href="http://www.cplusplus.com/reference/stl/deque/" rel="noreferrer">这里，听起来双端队列是某种数组的数组。它看起来不像是一个普通的旧循环缓冲区。那么它是一个间隙缓冲区，还是可增长数组的其他变体，或者它只是依赖于实现？

更新和答案摘要：

似乎普遍的共识是双端队列是一种数据结构，这样：

• 插入或删除元素的时间在列表的开头或结尾应该是恒定的，并且最多其他地方呈线性。如果我们将其解释为真正的恒定时间而不是摊销恒定时间，正如有人评论的那样，这似乎具有挑战性。有些人认为我们不应该将其解释为非摊销常数时间。
• “双端队列要求任何插入都应保持对成员元素的任何引用有效。迭代器无效是可以的，但成员本身必须保留在内存中的同一位置。”正如有人评论的那样：这很简单，只需将成员复制到堆上的某个位置并将 T* 存储在底层的数据结构中即可。
• “在双端队列的开头或结尾插入单个元素总是需要恒定的时间，并导致对 T 的构造函数的单次调用。”如果数据结构在底层存储 T*，也将实现 T 的单一构造函数。
• 数据结构必须具有随机访问能力。

如果我们将第一个条件设为“非摊销恒定时间”，似乎没有人知道如何获得第一个和第四个条件的组合。链表实现了 1) 但不能实现 4)，而典型的循环缓冲区实现了 4) 但不能实现 1)。我认为我有一个实现可以满足以下两个要求。评论？

我们从其他人建议的实现开始：我们分配一个数组并开始从中间放置元素，在前面和后面留出空间。在此实现中，我们跟踪从中心向前和向后方向有多少个元素，将这些值称为 F 和 B。然后，让我们使用一个两倍于原始大小的辅助数组来扩充此数据结构数组（所以现在我们浪费了大量的空间，但渐近复杂度没有变化）。我们还将从中间填充这个辅助数组，并为其赋予相似的值 F' 和 B'。策略是这样的：每次我们在给定方向上向主数组添加一个元素，如果 F > 则F'或B> B'（取决于方向），最多两个值从主数组复制到辅助数组，直到 F' 赶上 F（或 B' 赶上 B）。因此，插入操作涉及将 1 个元素放入主数组中，然后将最多 2 个元素从主数组复制到辅助数组，但它仍然是 O(1)。当主数组已满时，我们释放主数组，将辅助数组设为主数组，并创建另一个 2 倍大的辅助数组。这个新的辅助数组以 F' = B' = 0 开始，并且没有复制任何内容（因此，如果堆分配的复杂度为 O(1)，则调整大小操作为 O(1)）。由于辅助设备为添加到主设备的每个元素复制 2 个元素，并且主设备一开始最多为半满，因此当主设备再次耗尽空间时，辅助设备不可能赶不上主设备。同样，删除只需要从主元素中删除 1 个元素，从辅助元素中删除 0 或 1 个元素。因此，假设堆分配时间复杂度为 O(1)，则此实现满足条件 1)。我们将数组设置为 T* 并在插入时使用 new 来满足条件 2) 和 3)。最后，4) 得到满足，因为我们使用的是数组结构并且可以轻松实现 O(1) 访问。

Answer 1

这是特定于实现的。双端队列所需要的只是在开始/结束时的恒定时间插入/删除，并且在其他地方最多是线性的。元素不要求是连续的。

大多数实现都使用可被描述为展开列表的内容。固定大小的数组在堆上分配，指向这些数组的指针存储在属于双端队列的动态大小的数组中。

Answer 2

双端队列通常被实现为 T 数组的动态数组。

 (a) (b) (c) (d)
 +-+ +-+ +-+ +-+
 | | | | | | | |
 +-+ +-+ +-+ +-+
  ^   ^   ^   ^
  |   |   |   |
+---+---+---+---+
| 1 | 8 | 8 | 3 | (reference)
+---+---+---+---+

数组(a)、(b)、(c)和(d)一般是固定容量的，并且内部数组(b)和(c)必然是满的。 (a) 和 (d) 未满，这会在两端插入 O(1) 次。

想象一下，我们做了很多push_front，(a)将会填满，当它满了并且执行插入时，我们首先需要分配一个新数组，然后增长（参考）向量并推送指向新数组前面的指针。

此实现简单地提供了：

• 随机访问
• 两端推送时的
• 引用保留在中间插入，与 min(distance(begin, it), distance(it, end)) 成正比（标准略有不同）比您所要求的更严格）

但是它未能满足摊销O(1)增长的要求。因为只要（参考）向量需要增长，数组就有固定的容量，所以我们有 O(N/容量) 的指针副本。由于指针的复制很简单，因此可以进行一次 memcpy 调用，因此实际上这基本上是恒定的......但这不足以出色地通过。

尽管如此，push_front 和 push_back 比 vector 更高效（除非您使用 MSVC 实现，该实现由于存储容量非常小而非常慢）数组...）

---

老实说，我知道没有数据结构或数据结构组合可以同时满足：

• 随机访问

和

• 两端插入 O(1)

我确实知道一些“接近”匹配：

• 摊销 O(1 ) 可以进行插入对于在中间写入的动态数组，这与双端队列的“引用保存”语义不兼容。B
• +树可以调整为通过索引而不是通过键提供访问，次数接近常数，但访问和插入（常数较小）复杂度为O(log N)，需要在中间层节点使用Fenwick Tree。
• 手指树也可以进行类似的调整，不过它的时间复杂度还是 O(log N)。

Answer 3

使用向量可以正确实现deque。所有元素都被复制到堆上，指针存储在向量中。 （稍后将详细介绍向量）。

为什么使用 T* 而不是 T？因为标准要求

“在双端队列任一端插入都会使所有迭代器无效
到双端队列，但对引用的有效性没有影响
双端队列的元素。"

（我的重点）。T* 有助于满足这一点。它还帮助我们满足这一点：

“在双端队列的开头或结尾插入单个元素总是......导致对 T 的构造函数的单次调用。”

现在来说说（有争议的）部分。为什么使用向量来存储T*？它为我们提供了随机访问，这是一个好的开始。让我们暂时忘记向量的复杂性，并仔细构建这一点：

标准谈论“所包含对象上的操作数量”。对于 deque::push_front 来说，这显然是 1，因为恰好构造了一个 T 对象，并且在任何一个中读取或扫描了零个现有的 T 对象。方式。这个数字 1 显然是一个常量，并且与当前双端队列中的对象数量无关。这让我们可以这样说：

“对于我们的 deque::push_front，所包含对象（Ts）上的操作数量是固定的，并且与双端队列中已有的对象数量无关。”

当然，T*上的操作数就不会那么乖了。当向量变得太大时，它将被重新分配，并且许多T*将被复制。所以，是的，T* 上的操作数量会有很大差异，但 T 上的操作数量不会受到影响。

为什么我们要关心 T 上的计数操作和 T* 上的计数操作之间的区别？这是因为标准说：

本条款中的所有复杂性要求仅根据所包含对象的操作数量来说明。

对于deque，包含的对象是T，而不是T*，这意味着我们可以忽略任何复制（或重新分配）a的操作T*。

我没有过多谈论向量在双端队列中的行为。也许我们会将其解释为循环缓冲区（向量始终占用其最大容量（），然后当向量已满时将所有内容重新分配到更大的缓冲区中。细节并不重要。

在前面几段中，我们分析了 deque::push_front 以及双端队列中已经存在的对象数量与 push_front 对包含的 T 执行的操作数量之间的关系-我们发现它们是物体。 由于标准要求复杂性以 T 上的操作为单位，因此我们可以说它具有恒定的复杂性。

是的， Operations-On-T*-Complexity 已摊销（由于向量），但我们只对 Operations-On-T 感兴趣>-复杂性并且这是恒定的（非摊销）

：在此实现中，向量::push_back 或向量::push_front 的复杂性是无关紧要的；这些考虑因素涉及T* 上的操作，因此是无关紧要的。

Answer 4

（使这个答案成为社区维基。请坚持下去。）

首先要做的事情是：deque 要求对前面或后面的任何插入都应保持对成员元素的任何引用有效。迭代器失效是可以的，但成员本身必须保留在内存中的同一位置。这很简单，只需将成员复制到堆上的某个位置并将 T* 存储在底层的数据结构中即可。请参阅另一个 StackOverflow 问题“关于 deque的额外间接”

（vector 不保证保留迭代器或引用，而 list 则保留两者）。

因此，让我们认为这种“间接”是理所当然的，然后看看问题的其余部分。有趣的是从列表的开头或结尾插入或删除的时间。乍一看，deque 似乎可以用 vector 简单地实现，也许可以将其解释为 循环缓冲区。

但是双端队列必须满足“在队列的开头或结尾插入单个元素
deque 总是花费常数时间并导致对 T 的构造函数的一次调用。”

由于我们已经提到的间接，很容易确保只有一个构造函数调用，但挑战是保证常数时间如果我们只使用常数摊销时间，这将很容易，这将允许简单的向量实现，但它必须是常数（非摊销）时间。

Answer 5

我对双端队列的理解

它从堆中分配“n”个空连续对象作为第一个子数组。
其中的对象在插入时由头指针仅添加一次。

当头指针到达数组末尾时
分配/链接一个新的非连续子数组并在其中添加对象。

它们在提取时被尾指针删除一次。
当尾指针完成一个对象的子数组时，它会移动
到下一个链接的子数组，并释放旧的。

双端队列永远不会在内存中移动头部和尾部之间的中间对象。

随机访问首先确定哪个子阵列具有
对象，然后从它在子数组中的相对偏移量访问它。

Answer 6

这是对用户重力对 2 阵列解决方案进行评论的挑战的回答。

• 这里讨论了一些细节
• 给出了改进建议

细节讨论：
用户“重力”已经给出了非常简洁的总结。 “重力”还要求我们评论平衡两个数组之间的元素数量的建议，以实现 O(1) 最坏情况（而不是平均情况）运行时间。好吧，如果两个数组都是环形缓冲区，则该解决方案可以有效地工作，并且在我看来，将双端队列分成两个段就足够了，按照建议进行平衡。
我还认为，出于实际目的，标准 STL 实现至少足够好，但在实时要求和经过适当调整的内存管理的情况下，人们可能会考虑使用这种平衡技术。 Eric Demaine 在一篇较旧的 Dr.Dobbs 文章中也给出了不同的实现，具有类似的最坏情况运行时间。

平衡两个缓冲区的负载需要根据情况在 0 或 3 个元素之间移动。例如，如果我们将前段保留在主数组中，pushFront(x) 必须将最后 3 个元素从主环移动到辅助环，以保持所需的平衡。后面的 PushBack(x) 必须掌握负载差异，然后决定何时将一个元素从主数组移动到辅助数组。

改进建议：
如果前部和后部都存放在辅助环中，则需要做的工作和记账工作就会减少。这可以通过将双端队列切割成三段 q1,q2,q3 来实现，按以下方式排列： 前部 q1 位于辅助环（双倍大小的环）中，并且可以从元素所在的任何偏移处开始随后按顺时针方向排列。 q1 中的元素数量恰好是辅助环中存储的所有元素的一半。后部 q3 也在辅助环中，与辅助环中的 q1 部分完全相反，在后续顺序中也是顺时针方向。必须在所有双端队列操作之间保留此不变量。只有中间部分 q2 位于主环中（按顺时针顺序）。

现在，每个操作要么恰好移动一个元素，要么在任一元素变空时分配一个新的空环形缓冲区。例如，pushFront(x) 将 x 存储在辅助环中 q1 之前。为了保持不变性，我们将q2的最后一个元素移动到后面q3的前面。因此，q1 和 q3 在其前面都增加了一个元素，从而保持彼此相对。 PopFront() 的工作方式相反，后面的操作也以同样的方式工作。当 q1 和 q3 相互接触并在辅助环内形成完整的后续元件时，主环（与中间部分 q2 相同）变空。此外，当双端队列收缩时，当 q2 在主环中形成适当的圆时，q1,q3 将清空。

Answer 7

deque 中的数据由固定大小的向量块存储，这些块

由 map 指针（它也是一个向量块，但它的大小可能会改变）

deque迭代器的主要部分代码如下：

/*
buff_size is the length of the chunk
*/
template <class T, size_t buff_size>
struct __deque_iterator{
    typedef __deque_iterator<T, buff_size>              iterator;
    typedef T**                                         map_pointer;

    // pointer to the chunk
    T* cur;       
    T* first;     // the begin of the chunk
    T* last;      // the end of the chunk

    //because the pointer may skip to other chunk
    //so this pointer to the map
    map_pointer node;    // pointer to the map
}

deque的主要部分代码如下：

/*
buff_size is the length of the chunk
*/
template<typename T, size_t buff_size = 0>
class deque{
    public:
        typedef T              value_type;
        typedef T&            reference;
        typedef T*            pointer;
        typedef __deque_iterator<T, buff_size> iterator;

        typedef size_t        size_type;
        typedef ptrdiff_t     difference_type;

    protected:
        typedef pointer*      map_pointer;

        // allocate memory for the chunk 
        typedef allocator<value_type> dataAllocator;

        // allocate memory for map 
        typedef allocator<pointer>    mapAllocator;

    private:
        //data members

        iterator start;
        iterator finish;

        map_pointer map;
        size_type   map_size;
}

下面我给大家介绍一下deque的核心代码，主要是两部分：

1. iterator

2. 关于deque的简单函数

1. iterator(__deque_iterator)

迭代器的主要问题是，当++、--迭代器时，它可能会跳到其他块（如果它的指针指向块的边缘）。例如，存在三个数据块：chunk 1、chunk 2、chunk 3。

pointer1 指针指向 chunk 2 的开头，当操作符 --pointer 时，它将指向 chunk 1 的结尾code>，从而指向pointer2。

下面我将给出__deque_iterator的主要功能：

首先，跳到任何块：

void set_node(map_pointer new_node){
    node = new_node;
    first = *new_node;
    last = first + chunk_size();
}

注意，chunk_size()函数计算块size，你可以认为这里返回8是为了简化。

operator* 获取chunk中的数据

reference operator*()const{
    return *cur;
}

operator++, --

// 增量的前缀形式

self& operator++(){
    ++cur;
    if (cur == last){      //if it reach the end of the chunk
        set_node(node + 1);//skip to the next chunk
        cur = first;
    }
    return *this;
}

// postfix forms of increment
self operator++(int){
    self tmp = *this;
    ++*this;//invoke prefix ++
    return tmp;
}
self& operator--(){
    if(cur == first){      // if it pointer to the begin of the chunk
        set_node(node - 1);//skip to the prev chunk
        cur = last;
    }
    --cur;
    return *this;
}

self operator--(int){
    self tmp = *this;
    --*this;
    return tmp;
}

2.关于deque

常用函数的 简单函数>deque

iterator begin(){return start;}
iterator end(){return finish;}

reference front(){
    //invoke __deque_iterator operator*
    // return start's member *cur
    return *start;
}

reference back(){
    // cna't use *finish
    iterator tmp = finish;
    --tmp; 
    return *tmp; //return finish's  *cur
}

reference operator[](size_type n){
    //random access, use __deque_iterator operator[]
    return start[n];
}

如果你想更深入地理解deque你也可以看这个问题https://stackoverflow.com/a/50959796/6329006