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

What really is a deque in STL?

提问by Zonko

I was looking at STL containers and trying to figure what they really are (i.e. the data structure used), and the dequestopped me: I thought at first that it was a double linked list, which would allow insertion and deletion from both ends in constant time, but I am troubled by the promise madeby the operator [] to be done in constant time. In a linked list, arbitrary access should be O(n), right?

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

And if it's a dynamic array, how can it add elementsin constant time? It should be mentioned that reallocation may happen, and that O(1) is an amortized cost, like for a vector.

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

So I wonder what is this structure that allows arbitrary access in constant time, and at the same time never needs to be moved to a new bigger place.

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

采纳答案by Konrad Rudolph

A deque is somewhat recursively defined: internally it maintains a double-ended queue of chunksof fixed size. Each chunk is a vector, and the queue (“map” in the graphic below) of chunks itself is also a vector.

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

There's a great analysis of the performance characteristics and how it compares to the vectorover at CodeProject.

还有的性能有很大的分析和如何比较的vector超过CodeProject上。

The GCC standard library implementation internally uses a T**to represent the map. Each data block is a T*which is allocated with some fixed size __deque_buf_size(which depends on sizeof(T)).

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

回答by Mark Ransom

Imagine it as a vector of vectors. Only they aren't standard std::vectors.

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

The outer vector contains pointers to the inner vectors. When its capacity is changed via reallocation, rather than allocating all of the empty space to the end as std::vectordoes, it splits the empty space to equal parts at the beginning and the end of the vector. This allows push_frontand push_backon this vector to both occur in amortized O(1) time.

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

The inner vector behavior needs to change depending on whether it's at the front or the back of the deque. At the back it can behave as a standard std::vectorwhere it grows at the end, and push_backoccurs in O(1) time. At the front it needs to do the opposite, growing at the beginning with each push_front. In practice this is easily achieved by adding a pointer to the front element and the direction of growth along with the size. With this simple modification push_frontcan also be O(1) time.

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

Access to any element requires offsetting and dividing to the proper outer vector index which occurs in O(1), and indexing into the inner vector which is also O(1). This assumes that the inner vectors are all fixed size, except for the ones at the beginning or the end of the deque.

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

回答by Alok Save

deque = double ended queue

deque = 双端队列

A container which can grow in either direction.

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

Deque is typicallyimplemented as a vectorof vectors(a list of vectors can't give constant time random access). While the size of the secondary vectors is implementation dependent, a common algorithm is to use a constant size in bytes.

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

回答by Aaron McDaid

(This is an answer I've given in another thread. Essentially I'm arguing that even fairly naive implementations, using a single vector, conform to the requirements of "constant non-amortized push_{front,back}". You might be surprised, and think this is impossible, but I have found other relevant quotes in the standard that define the context in a surprising way. Please bear with me; if I have made a mistake in this answer, it would be very helpful to identify which things I have said correctly and where my logic has broken down. )

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

In this answer, I am not trying to identify a goodimplementation, I'm merely trying to help us to interpret the complexity requirements in the C++ standard. I'm quoting from N3242, which is, according to Wikipedia, the latest freely available C++11 standardization document. (It appears to be organized differently from the final standard, and hence I won't quote the exact page numbers. Of course, these rules might have changed in the final standard, but I don't think that has happened.)

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

A deque<T>could be implemented correctly by using a vector<T*>. All the elements are copied onto the heap and the pointers stored in a vector. (More on the vector later).

Adeque<T>可以通过使用vector<T*>. 所有元素都被复制到堆上，指针存储在一个向量中。（稍后会详细介绍向量）。

Why T*instead of T? Because the standard requires that

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

"An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque."

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

(my emphasis). The T*helps to satisfy that. It also helps us to satisfy this:

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

"Inserting a single element either at the beginning or end of a deque always ..... causes a single call to a constructor of T."

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

Now for the (controversial) bit. Why use a vectorto store the T*? It gives us random access, which is a good start. Let's forget about the complexity of vector for a moment and build up to this carefully:

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

The standard talks about "the number of operations on the contained objects.". For deque::push_frontthis is clearly 1 because exactly one Tobject is constructed and zero of the existing Tobjects are read or scanned in any way. This number, 1, is clearly a constant and is independent of the number of objects currently in the deque. This allows us to say that:

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

'For our deque::push_front, the number of operations on the contained objects (the Ts) is fixed and is independent of the number of objects already in the deque.'

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

Of course, the number of operations on the T*will not be so well-behaved. When the vector<T*>grows too big, it'll be realloced and many T*s will be copied around. So yes, the number of operations on the T*will vary wildly, but the number of operations on Twill not be affected.

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

Why do we care about this distinction between counting operations on Tand counting operations on T*? It's because the standard says:

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

All of the complexity requirements in this clause are stated solely in terms of the number of operations on the contained objects.

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

For the deque, the contained objects are the T, not the T*, meaning we can ignore any operation which copies (or reallocs) a T*.

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

I haven't said much about how a vector would behave in a deque. Perhaps we would interpret it as a circular buffer (with the vector always taking up its maximum capacity(), and then realloc everything into a bigger buffer when the vector is full. The details don't matter.

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

In the last few paragraphs, we have analyzed deque::push_frontand the relationship between the number of objects in the deque already and the number of operations performed by push_front on contained T-objects. And we found they were independent of each other. As the standard mandates that complexity is in terms of operations-on-T, then we can say this has constant complexity.

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

Yes, the Operations-On-T*-Complexityis amortized (due to the vector), but we're only interested in the Operations-On-T-Complexityand this is constant (non-amortized).

是的，Operations-On-T*-Complexity是摊销的（由于vector），但我们只对Operations-On-T-Complexity感兴趣并且这是常数（非摊销）。

The complexity of vector::push_back or vector::push_front is irrelevant in this implementation; those considerations involve operations on T*and hence are irrelevant. If the standard was referring to the 'conventional' theoretical notion of complexity, then they wouldn't have explicitly restricted themselves to the "number of operations on the contained objects". Am I overinterpreting that sentence?

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

回答by Jayhello

From overview, you can think dequeas a double-ended queue

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

The datas in dequeare stored by chuncks of fixed size vector, which are

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

pointered by a map(which is also a chunk of vector, but its size may change)

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

The main part code of the deque iteratoris as below:

主要部分代码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
}

The main part code of the dequeis as below:

主要部分代码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;
}

Below i will give you the core code of deque, mainly about three parts:

下面给大家介绍一下核心代码deque，主要讲三部分：

1. iterator

2. How to construct a deque

1. 迭代器

2. 如何构建一个 deque

1. iterator(__deque_iterator)

1.迭代器( __deque_iterator)

The main problem of iterator is, when ++, -- iterator, it may skip to other chunk(if it pointer to edge of chunk). For example, there are three data chunks: chunk 1,chunk 2,chunk 3.

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

The pointer1pointers to the begin of chunk 2, when operator --pointerit will pointer to the end of chunk 1, so as to the pointer2.

pointer1指向开始的指针chunk 2，当操作符时--pointer它会指向结束的chunk 1，从而指向pointer2。

Below I will give the main function of __deque_iterator:

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

Firstly, skip to any chunk:

首先，跳到任何块：

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

Note that, the chunk_size()function which compute the chunk size, you can think of it returns 8 for simplify here.

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

operator*get the data in the chunk

operator*获取块中的数据

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

operator++, --

operator++, --

// prefix forms of increment

// 递增的前缀形式

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

iterator skip n steps / random access迭代器跳过 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. How to construct a deque

2. 如何构建一个 deque

common function of 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();
}

Let's assume i_dequehas 20 int elements 0~19whose chunk size is 8, and now push_back 3 elements (0, 1, 2) to i_deque:

假设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);

It's internal structure like below:

它的内部结构如下：

Then push_back again, it will invoke allocate new chunk:

然后再次 push_back，它将调用分配新块：

push_back(3)

If we push_front, it will allocate new chunk before the prev start

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

Note when push_backelement into deque, if all the maps and chunks are filled, it will cause allocate new map, and adjust chunks.But the above code may be enough for you to understand deque.

注意push_backelement进入deque的时候，如果map和chunk都被填满了，会导致allocate new map，adjust chunks。但是上面的代码可能已经足够你理解了deque。

回答by Keloo

I was reading "Data structures and algorithms in C++" by Adam Drozdek, and found this useful. HTH.

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

A very interesting aspect of STL deque is its implementation. An STL deque is not implemented as a linked list but as an array of pointers to blocks or arrays of data. The number of blocks changes dynamically depending on storage needs, and the size of the array of pointers changes accordingly.

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

You can notice in the middle is the array of pointers to the data (chunks on the right), and also you can notice that the array in the middle is dynamically changing.

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

An image is worth a thousand words.

一张图片胜过千言万语。

回答by Kerrek SB

While the standard doesn't mandate any particular implementation (only constant-time random access), a deque is usually implemented as a collection of contiguous memory "pages". New pages are allocated as needed, but you still have random access. Unlike std::vector, you're not promised that data is stored contiguously, but like vector, insertions in the middle require lots of relocating.

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