45

我读过通过位置索引访问元素可以在 STL 双端队列中以恒定时间完成。据我所知,双端队列中的元素可能存储在几个不连续的位置,从而消除了通过指针算法进行的安全访问。例如:

abc->defghi->jkl->mnop

上述双端队列的元素由单个字符组成。一组中的字符集表明它是在连续内存中分配的(例如,abc 位于单个内存块中,defhi 位于另一块内存中,等等)。谁能解释如何通过位置索引访问可以在恒定时间内完成,特别是如果要访问的元素位于第二个块中?还是双端队列有指向块组的指针?

更新:或者双端队列还有其他常见的实现吗?

4

4 回答 4

34

我从Wikipedia找到了这个双端队列实现:

将内容存储在多个较小的数组中,根据需要在开头或结尾分配额外的数组。索引是通过保持一个包含指向每个较小数组的指针的动态数组来实现的。

我想它回答了我的问题。

于 2010-02-22T03:44:26.487 回答
15

中的数据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,主要讲两部分:

  1. 迭代器

  2. 如何随机访问一个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];
}

您还会看到这个问题,它给出了主要代码deque

https://stackoverflow.com/a/50959796/6329006

于 2018-06-21T03:25:06.017 回答
1

一种可能的实现可以是 const 大小数组的动态数组;当需要更多空间时,可以将这种 const 大小的数组添加到任一端。除了可能部分为空的第一个和最后一个数组之外,所有数组都是满的。这意味着知道每个数组的大小和第一个数组中使用的元素数量,可以通过索引轻松找到元素的位置。
http://cpp-tip-of-the-day.blogspot.ru/2013/11/how-is-stddeque-implemented.html

于 2016-11-24T10:14:28.093 回答
-1

如果 deque 被实现为顶部的环形缓冲区std::vector,当它的大小增长时会重新分配自己,那么通过索引访问确实是 O(1)。

该标准提供了证据表明这种实现是有意义的——至少它符合复杂性估计的标准。条款 23.2.1.3/4 和 23.2.1.3/5 要求

  • 插入到双端队列的开头或结尾需要恒定时间,而插入到中间需要双端队列大小的线性时间

  • 当从双端队列中擦除元素时,它可能会调用尽可能多的赋值运算符,就像从被擦除的元素到双端队列末尾的距离一样。

而且,当然,您应该依靠标准要求,而不是您自己对如何实现容器和算法的愿景。

请注意,该标准要求的不仅仅是上面列出的这两点。它还要求对元素的引用必须在插入到双端队列的后面或前面之间保持有效。如果环形缓冲区包含指向实际元素而不是元素本身的指针,则可以满足这一点。无论如何,我的回答只是证明了多个实现可以满足某些要求的想法。

于 2010-02-19T15:02:55.950 回答