按索引访问的STL deque是O(1)？

Question

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

ABC-> defghi-> jkl-> MNOP

上面的双端队列元素由一个字符组成.一组中的字符集表示它被分配在连续的存储器中(例如,abc在单个存储器块中,defhi位于另一个存储器块中,等等).任何人都可以解释如何通过位置索引进行访问可以在恒定时间内完成,特别是如果要访问的元素在第二个块中？或者双端队列是否有指向这组块的指针？

更新:或者deque还有其他常见的实现吗？

Answer 1

我从维基百科发现了这个deque实现:

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

我想它回答了我的问题.

Answer 2

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

以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. iterator（__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

/sf/answers/3567185751/