c++ - STL 中的双端队列到底是什么？

Question

我正在查看 STL 容器并试图弄清楚它们到底是什么（即使用的数据结构），而双端队列阻止了我：我起初以为它是一个双链表，它允许从两端插入和删除恒定时间，但我对运算符 []承诺在恒定时间内完成感到困扰。在链表中，任意访问应该是 O(n)，对吧？

如果它是一个动态数组，它怎么能在恒定时间内添加元素呢？应该提到的是，可能会发生重新分配，并且 O(1) 是摊销成本，就像 vector 一样。

所以我想知道这个结构是什么，它允许在恒定时间内任意访问，同时永远不需要移动到一个新的更大的地方。

score 218 · Accepted Answer

双端队列在某种程度上是递归定义的：在内部它维护一个固定大小的块的双端队列。每个块都是一个向量，块本身的队列（下图中的“映射”）也是一个向量。

对性能特征以及它与CodeProjectvector的比较进行了很好的分析。

GCC 标准库实现在内部使用 aT**来表示映射。每个数据块都是一个T*分配有一些固定大小__deque_buf_size（取决于sizeof(T)）的数据块。

score 33 · Accepted Answer

从概述中，您可以将deque其视为double-ended queue

中的数据deque由固定大小的向量块存储，它们是

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

的主要部分代码deque iterator如下：

/*
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，主要是三个部分：

迭代器
如何构建一个deque

1. 迭代器（`__deque_iterator`）

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

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

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

首先，跳到任何块：

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

请注意，chunk_size()计算块大小的函数，您可以认为它返回 8 以进行简化。

operator*获取块中的数据

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;
}

迭代器跳过 n 步/随机访问

self& operator+=(difference_type n){ // n can be postive or negative
    difference_type offset = n + (cur - first);
    if(offset >=0 && offset < difference_type(buffer_size())){
        // in the same chunk
        cur += n;
    }else{//not in the same chunk
        difference_type node_offset;
        if (offset > 0){
            node_offset = offset / difference_type(chunk_size());
        }else{
            node_offset = -((-offset - 1) / difference_type(chunk_size())) - 1 ;
        }
        // skip to the new chunk
        set_node(node + node_offset);
        // set new cur
        cur = first + (offset - node_offset * chunk_size());
    }

    return *this;
}

// skip n steps
self operator+(difference_type n)const{
    self tmp = *this;
    return tmp+= n; //reuse  operator +=
}

self& operator-=(difference_type n){
    return *this += -n; //reuse operator +=
}

self operator-(difference_type n)const{
    self tmp = *this;
    return tmp -= n; //reuse operator +=
}

// random access (iterator can skip n steps)
// invoke operator + ,operator *
reference operator[](difference_type n)const{
    return *(*this + n);
}

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];
}


template<typename T, size_t buff_size>
deque<T, buff_size>::deque(size_t n, const value_type& value){
    fill_initialize(n, value);
}

template<typename T, size_t buff_size>
void deque<T, buff_size>::fill_initialize(size_t n, const value_type& value){
    // allocate memory for map and chunk
    // initialize pointer
    create_map_and_nodes(n);

    // initialize value for the chunks
    for (map_pointer cur = start.node; cur < finish.node; ++cur) {
        initialized_fill_n(*cur, chunk_size(), value);
    }

    // the end chunk may have space node, which don't need have initialize value
    initialized_fill_n(finish.first, finish.cur - finish.first, value);
}

template<typename T, size_t buff_size>
void deque<T, buff_size>::create_map_and_nodes(size_t num_elements){
    // the needed map node = (elements nums / chunk length) + 1
    size_type num_nodes = num_elements / chunk_size() + 1;

    // map node num。min num is  8 ，max num is "needed size + 2"
    map_size = std::max(8, num_nodes + 2);
    // allocate map array
    map = mapAllocator::allocate(map_size);

    // tmp_start，tmp_finish poniters to the center range of map
    map_pointer tmp_start  = map + (map_size - num_nodes) / 2;
    map_pointer tmp_finish = tmp_start + num_nodes - 1;

    // allocate memory for the chunk pointered by map node
    for (map_pointer cur = tmp_start; cur <= tmp_finish; ++cur) {
        *cur = dataAllocator::allocate(chunk_size());
    }

    // set start and end iterator
    start.set_node(tmp_start);
    start.cur = start.first;

    finish.set_node(tmp_finish);
    finish.cur = finish.first + num_elements % chunk_size();
}

假设i_deque有 20 个 int 元素0~19，其块大小为 8，现在 push_back 3 个元素 (0, 1, 2) 到i_deque：

i_deque.push_back(0);
i_deque.push_back(1);
i_deque.push_back(2);

它的内部结构如下：

然后再次 push_back，它会调用 allocate new chunk：

push_back(3)

如果我们push_front，它将在 prev 之前分配新的块start

注意push_backelement进入deque时，如果map和chunk都被填满，会导致分配新的map，并调整chunk。不过上面的代码可能已经足够你理解了deque。

score 27 · Accepted Answer

把它想象成一个向量的向量。只有它们不是标准std::vector的。

外部向量包含指向内部向量的指针。当它的容量通过重新分配而改变时，它不是将所有空白空间都分配到末尾std::vector，而是在向量的开头和结尾将空白空间分成相等的部分。这允许push_front和push_back在这个向量上都发生在摊销的 O(1) 时间内。

内部向量行为需要根据它是在deque. 在后面，它可以作为一个标准std::vector，它在最后增长，并push_back在 O(1) 时间内发生。在前面它需要做相反的事情，在开始时与 each 一起增长push_front。在实践中，这很容易通过添加指向前端元素的指针和增长方向以及大小来实现。通过这个简单的修改push_front也可以是 O(1) 时间。

访问任何元素都需要偏移和划分到出现在 O(1) 中的适当的外部向量索引，并索引到也是 O(1) 的内部向量。这假设内部向量都是固定大小的，除了开头或结尾的向量deque。

score 18 · Accepted Answer

deque = 双端队列

可以向任一方向生长的容器。

双端队列通常被实现为vector（vectors向量列表不能提供恒定时间随机访问）。虽然辅助向量的大小取决于实现，但常见的算法是使用以字节为单位的恒定大小。

score 18 · Accepted Answer

（这是我在另一个线程中给出的答案。本质上，我认为即使是相当幼稚的实现，使用单个vector，也符合“常量非摊销 push_{front,back}”的要求。你可能会感到惊讶, 并认为这是不可能的, 但我在标准中发现了其他相关的引用, 以一种令人惊讶的方式定义上下文. 请多多包涵; 如果我在这个答案中犯了错误, 找出哪些东西会很有帮助我说得对，我的逻辑在哪里崩溃了。）

在这个答案中，我不是想确定一个好的实现，我只是想帮助我们解释 C++ 标准中的复杂性要求。我引用了N3242，根据Wikipedia，这是最新的免费提供的 C++11 标准化文档。（它的组织方式似乎与最终标准不同，因此我不会引用确切的页码。当然，这些规则在最终标准中可能已经改变，但我认为没有发生这种情况。）

Adeque<T>可以通过使用正确实现vector<T*>。所有元素都复制到堆上，指针存储在向量中。（稍后将详细介绍矢量）。

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

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

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

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

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

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

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

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

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

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

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

关于向量在双端队列中的行为，我没有说太多。也许我们会将它解释为一个循环缓冲区（向量总是占用它的最大值capacity()，然后当向量已满时将所有内容重新分配到一个更大的缓冲区中。细节无关紧要。

在最后几段中，我们已经分析deque::push_front了 deque 中的对象数量与 push_front 对包含的对象执行的操作数量之间的关系T。我们发现它们是相互独立的。由于标准要求复杂性是基于操作的T，那么我们可以说这具有恒定的复杂性。

是的，Operations-On-T*-Complexity是摊销的（由于vector），但我们只对Operations-On-T-Complexity感兴趣，它是恒定的（非摊销的）。

vector::push_back 或 vector::push_front 的复杂性在此实现中无关紧要；这些考虑涉及操作T*，因此是无关紧要的。如果该标准指的是复杂性的“传统”理论概念，那么他们就不会明确地将自己限制为“对所包含对象的操作数量”。我是否过度解释了这句话？

score 9 · Accepted Answer

我正在阅读 Adam Drozdek 的“C++ 中的数据结构和算法”，发现这很有用。HTH。

STL deque 的一个非常有趣的方面是它的实现。STL 双端队列不是作为链表实现的，而是作为指向块或数据数组的指针数组实现的。块的数量根据存储需求动态变化，指针数组的大小也会相应变化。

您可以注意到中间是指向数据的指针数组（右侧的块），并且您还可以注意到中间的数组是动态变化的。

一张图片胜过千言万语。

score 6 · Accepted Answer

虽然该标准没有强制要求任何特定的实现（仅是恒定时间随机访问），但双端队列通常被实现为连续内存“页面”的集合。根据需要分配新页面，但您仍然可以随机访问。与不同std::vector的是，您不能保证数据是连续存储的，但就像向量一样，中间的插入需要大量的重定位。

score 0 · Accepted Answer

deque可以实现为固定大小数组的循环缓冲区：

使用循环缓冲区，因此我们可以通过添加/删除具有 O(1) 复杂度的固定大小的数组来在两端增长/缩小
使用固定大小的数组，因此很容易计算索引，因此通过索引访问两个指针取消引用 - 也是 O(1)

c++ - STL 中的双端队列到底是什么？

8 回答 8

1. 迭代器（__deque_iterator）

2. 如何构建一个deque

Related

Reference

1. 迭代器（`__deque_iterator`）

2. 如何构建一个`deque`