Что на самом деле-это очереди в STL?

deque = двойная очередь

контейнер, который может расти в любом направлении.

Дека обычно реализован как vector на vectors (список векторов не может дать постоянное время произвольного доступа). В то время как размер вторичных векторов зависит от реализации, общий алгоритм должен использовать постоянный размер в байтах.

представьте себе, что это вектор векторов. Только они не стандартные std::vector s.

внешний вектор содержит указатели на внутренние векторы. Когда его емкость изменяется путем перераспределения, а не выделения всего пустого пространства до конца как 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.

(это ответ, который я дал в другое нить. По сути я утверждаю, что даже довольно наивные реализации, используя один vector, соответствуют требованиям "постоянного не амортизированного push_{front, back}". Вы можете быть удивлены, и думаю, что это невозможно, но я нашел другие соответствующие цитаты в стандарте, которые определяют контекст удивительным образом. Пожалуйста, потерпите меня; если я сделал ошибку в этом ответе, было бы очень полезно определить какие вещи я сказал правильно и где моя логика сломалась. )

в этом ответе, я не пытаюсь определить хороший реализация, я просто пытаюсь помочь нам интерпретировать требования к сложности в стандарте C++. Я цитирую из N3242, который, согласно Википедия, последний свободно доступный документ по стандартизации C++11. (Он, по-видимому, организован иначе, чем окончательный стандарт, и поэтому я не буду цитировать точные номера страниц. Конечно, эти правила могли бы измениться в окончательном стандарте, но я не думаю, что это произошло.)

A deque<T> может быть реализовано правильно с помощью vector<T*>. Все элементы копируются в кучу и указатели хранятся в векторе. (Подробнее о векторе позже).

почему T* вместо T? Потому что стандарт требует, чтобы

" вставка на обоих концах дека делает недействительными все итераторы к Деку, но имеет не влияет на правильность ссылок на элементы дека."

(Курсив мой). Элемент T* помогает удовлетворить это. Это также помогает нам удовлетворить это:

"вставка одного элемента либо в начале, либо в конце дека всегда ..... вызывает один вызов конструктора T."

теперь для (спорного) бита. Почему используйте vector для хранения T*? Это дает нам случайный доступ, что является хорошим началом. Давайте на мгновение забудем о сложности вектора и построим до этого тщательно:

стандарт говорит о " количестве операций над содержащимися объектами.". Ибо deque::push_front это очевидно, потому что ровно 1 T объект построен и ноль из существующих T объекты считываются или сканируются любым способом. Это число, 1, явно является константой и не зависит от количество объектов в настоящее время в очереди. Это позволяет нам сказать, что:

для deque::push_front, количество операций над содержащимися объектами (Ts) фиксировано и не зависит от количества объектов, уже находящихся в deque.-

конечно, количество операций на T* не будет так хорошо себя вел. Когда vector<T*> растет слишком большой, он будет перераспределен и многие T*S будут скопированы. Так что да, количество операций на T* будет меняться дико, но количество операций на T не будут затронуты.

почему мы заботимся об этом различии между операциями подсчета на T и счетных операций на T*? Это потому, что стандарт говорит:

все требования к сложности в этом пункте изложены исключительно с точки зрения количества операций над содержащимися объектами.

на deque, содержащиеся объекты являются T, не T*, что означает, что мы можем игнорировать любую операцию, которая копирует (или перераспределяет) a T*.

я не говорил о том, как вектор будет вести себя в очереди. Возможно, мы бы интерпретировали его как круговой буфер (с вектором, всегда занимающим свой максимум capacity(), а затем перераспределить все в больший буфер, когда вектор заполнен. Детали не имеют значения.

в последних нескольких абзацах мы проанализировали deque::push_front и связь между количеством объекты в deque уже и количество операций, выполняемых push_front на contained T-объекты. И мы обнаружили, что они независимы друг от друга. как стандартные мандаты, что сложность с точки зрения операций-на -T, то мы можем сказать, что это имеет постоянную сложность.

да Операции-На-Т * - Сложность амортизируется (за счет vector), но нас интересует только Operations-On-T-Complexity и это постоянная величина (не амортизируемая).

сложность vector:: push_back или vector:: push_front не имеет значения в этой реализации; эти соображения включают операции над T* и, следовательно, не имеют никакого отношения. Если бы стандарт имел в виду "обычное"теоретическое понятие сложности, то они явно не ограничились бы "количеством операций над содержащимися объектами". Я что, переоцениваю это предложение?

хотя стандарт не требует какой-либо конкретной реализации (только произвольный доступ с постоянным временем), deque обычно реализуется как коллекция смежных "страниц"памяти. Новые страницы выделяются по мере необходимости, но у вас все еще есть произвольный доступ. В отличие от std::vector, вам не обещают, что данные хранятся непрерывно, но, как и вектор, вставки в середине требуют большого перемещения.

из обзора, вы можете думать deque как double-ended queue

данные в deque хранятся чанки вектора фиксированного размера, которые

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)

основная проблема итератора заключается в том, что когда++, -- iterator, он может перейти к другому фрагменту(если он указывает на край фрагмента). Например, существует три блока данных: chunk 1,chunk 2,chunk 3.

The 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(1);
i_deque.push_back(2);
i_deque.push_back(3);

это внутренняя структура, как показано ниже:

затем push_back снова, он вызовет выделить новый кусок:

push_back(3)

если мы push_front, он выделит новый кусок перед prev start

обратите внимание, когда push_back элемент в deque, если все карты и куски заполнены, это приведет к выделению новой карты и корректировке фрагментов.Но приведенный выше код может быть достаточно для вас, чтобы понять deque.

Я читал "структуры данных и алгоритмы в C++" Адам Drozdek, и нашел, что это полезно. ХТ.

очень интересным аспектом STL deque является его реализация. STL deque реализуется не как связанный список, а как массив указателей на блоки или массивы данных. Количество блоков изменяется динамически в зависимости от потребностей хранения, и размер массива меняется указатели.

вы можете заметить в середине массив указателей на данные (блоки справа), а также вы можете заметить, что массив в середине динамично меняется.

изображение стоит тысячи слов.