什么是STL的双端队列？

Question

我正在查看STL容器并试图弄清楚它们到底是什么(即使用的数据结构),并且deque阻止了我:我起初认为它是一个双链表,它允许从两端插入和删除恒定时间,但我对运营商[]在恒定时间内做出的承诺感到不安.在链表中,任意访问应该是O(n),对吗？

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

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

Answer 1

deque在某种程度上是递归定义的:在内部它维护一个固定大小的块的双端队列.每个块都是一个向量,块本身的队列(下图中的"map")也是一个向量.

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

GCC标准库实现在内部使用a T**来表示地图.每个数据块都是一个T*固定大小__deque_buf_size(取决于sizeof(T))的数据块.

Answer 2

想象它是矢量的矢量.只有他们不是标准std::vector的.

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

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

对任何元素的访问需要抵消并除以在O(1)中出现的适当外向量索引,并且索引到内向量中,该向量也是O(1).这假设内部向量都是固定大小,除了在开头或末尾的那些deque.

Answer 3

deque =双端队列

一个可以向任一方向生长的容器.

双端队列通常实现为vector的vectors(向量的列表不能给恒定时的随机接入).虽然辅助向量的大小取决于实现,但常见的算法是使用以字节为单位的常量大小.

Answer 4

(这是我在另一个帖子中给出的答案.基本上我在争论即使是相当天真的实现,使用单一vector,符合"常量非摊销push_ {front,back}"的要求.你可能会感到惊讶,并认为这是不可能的,但我在标准中找到了其他相关的引用,以令人惊讶的方式定义了上下文.请耐心等待;如果我在这个答案中犯了错误,那么识别哪些东西会非常有帮助我已经说得对了,我的逻辑已经崩溃了.)

在这个答案中,我并不是要确定一个好的实现,我只是想帮助我们解释C++标准中的复杂性要求.我引用了N3242,根据维基百科的说法,这是最新的免费C++ 11标准化文档.(它看起来与最终标准的组织方式不同,因此我不会引用确切的页码.当然,这些规则可能在最终标准中有所改变,但我认为这种情况并未发生.)

A deque<T>可以通过使用a正确实现vector<T*>.所有元素都复制到堆上,指针存储在向量中.(稍后有关矢量的更多信息).

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

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

(我的重点).将T*有助于满足这一点.它也有助于我们满足这一要求:

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

现在为(有争议的)位.为什么用a vector来存储T*？它为我们提供随机访问,这是一个良好的开端.让我们暂时忘记向量的复杂性并仔细构建:

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

'对于我们来说deque::push_front,包含对象上的操作数(Ts)是固定的,并且与双端队列中已有的对象数无关.

当然,对它的操作次数T*不会那么好.当它vector<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),但我们只对T-Complexity操作感兴趣,这是常数(非摊销).

vector :: push_back或vector :: push_front的复杂性在此实现中无关紧要; 这些考虑涉及操作T*,因此无关紧要.如果标准指的是复杂性的"传统"理论概念,那么它们就不会明确地将自己局限于"所包含对象的操作次数".我是否过度解释这句话？

Answer 5

从概述,你能想到deque的double-ended queue

在DATAS deque由固定大小的矢量的chuncks,这是存储

由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,主要是关于三个部分:

1. 迭代器

2. 如何构建一个 deque

迭代器(__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个元素为i_deque:

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

它的内部结构如下:

然后再次push_back,它将调用分配新块:

push_back(3)

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

注意当push_back元素进入双端队列时,如果所有的地图和块都被填充,它将导致分配新的地图,并调整块.但是上面的代码可能足以让你理解deque.

Answer 6

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

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

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

一张图片胜过千言万语。

Answer 7

虽然该标准没有强制要求任何特定的实现(只有恒定时间随机访问),但是deque通常被实现为连续的存储器"页面"的集合.根据需要分配新页面,但您仍然可以随机访问.不同的是std::vector,你不承诺数据是连续存储的,但是像矢量一样,中间的插入需要大量的重新定位.