STL双端访问的指标是O(1)?

Question

我读过访问因素的位置指数可以在固定的时间在一STL双端.据我所知元素在双端可能会存在几个非毗连的地点，消除安全地进入通过的指针算。例如：

abc->子->捷海->mnop

元素的双端上述由一个单一的角色。设置的字在一个集团表示它被分配在连续的存储器(例如abc是在单个区块的存储器，defhi位于另一块的存储器，等等)。任何人都可以解释如何访问的位置指数可以在固定的时间，尤其是如果元素被访问是在第二块？或者一个双端有一个指向的群块？

更新：或是有任何其他共同执行一个双端?

Answer 1

我发现从维基此双端队列实现：

在多个较小的阵列中存储的内容，根据需要分配的开始或结束的额外阵列。索引是通过保持包含指向每个较小阵列的动态数组实现。

我想这回答我的问题。

Answer 2

该数据在 deque 存储chuncks固定大小的矢量，这都是

pointered通过一个 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)。例如，有三个数据块: 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++, --

//prefix形式的递增

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个步骤/random access

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

Answer 3

其中一个可能的实施方式可以是常量大小的数组的动态数组的;需要更多的空间时，这样的常量大小的数组可以被添加到任何一端。所有的阵列是全除，也许，第一个和最后的可以部分空。这意味着相知阵列的大小和在所述第一阵列的一个用于可以很容易地找到由索引的元素的位置的元素的数量。结果 的http：// CPP- tip-of-the-day.blogspot.ru/2013/11/how-is-stddeque-implemented.html

Answer 4

如果双端是实现为 环缓冲 顶上 std::vector, ，其中重新分配本身当它长大，然后访问过指数的确是O(1)。

该标准提供的证据表明，这种实现是指--至少符合标准的复杂性评估。条款23.2.1.3/4和23.2.1.3/5要求

• 插入的开始或结束的一个双端需要不断的时间，同时插入中间需要直线时间的双端的尺寸

• 当删除元素从双端，它可能叫作为许多分配运营商，因为距离元件被删除，以结束双端。

当然，你应该计标准要求，而不是你自己的愿景如何容器和算法可以实现的。

注意到 这种标准需要比这两点上面列出的。它还提出了要求，即所提及的要素必须留有效之间插入以后或前的双端.这可以感到满意，如果环缓冲包含指实际因素，而不是该元素自己。无论如何，我的回答只是表明的想法，多种实现可满足某些要求。