Что на самом деле является deque в STL?

Я смотрел на STL контейнеры и пытаясь понять , что они на самом деле (то есть структура данных , используемая), а Deque остановил меня: я сначала подумал , что это был двойной связанный список, который позволил бы вставку и удаление с обоих концов в постоянное время, но меня беспокоит обещание , данное оператором [], которое должно быть выполнено в постоянное время. В связанном списке произвольный доступ должен быть O (n), верно?

И если это динамический массив, как он может добавлять элементы в постоянное время? Следует отметить, что может произойти перераспределение, и что O (1) является амортизированной стоимостью, как для вектора .

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

Deque несколько рекурсивно определен: внутренне он поддерживает двустороннюю очередь кусков фиксированного размера. Каждый чанк является вектором, и очередь («карта» на рисунке ниже) самих чанков также является вектором.

Там отличный анализ характеристик производительности и , как он сравнивает с , vectorпо меньшей CodeProject .

Реализация стандартной библиотеки GCC внутренне использует T**для представления карты. Каждый блок данных имеет T*определенный фиксированный размер __deque_buf_size(который зависит от sizeof(T)).

Вообразите это как вектор векторов. Только они не стандартные 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.

deque = двусторонняя очередь

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

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

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

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

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

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

«Вставка на любом конце deque делает недействительными все итераторы для deque, но не влияет на достоверность ссылок на элементы deque ».

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

«Вставка одного элемента в начале или в конце deque всегда ..... вызывает один вызов конструктора T ».

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

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

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

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

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

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

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

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

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

Да, сложность Operations-On-T *-Амортизируется (из-за vector), но нас интересует только сложность Operations-On-T, и она постоянна (не амортизируется).

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

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

Данные в 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;
}

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 элемента (0, 1, 2) для i_deque:

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

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

Затем push_back снова вызовет выделение нового чанка:

push_back(3)

Если мы push_front, он будет выделять новый кусок доstart

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

Я читал «Структуры данных и алгоритмы в C ++» Адама Дроздека и нашел это полезным. НТН.

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

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

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

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