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

Ответ 1

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

Theres большой анализ характеристик производительности и того, как он сравнивается с vector в CodeProject.

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

Ответ 2

Представьте это как вектор векторов. Только они не являются стандартными 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.

Ответ 3

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

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

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

Ответ 4

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

В этом ответе я не пытаюсь определить хорошую реализацию, я просто пытаюсь помочь нам интерпретировать требования сложности в стандарте 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) фиксировано и не зависит от количества объектов, уже находящихся в deque. '

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

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

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

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

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

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

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

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

Ответ 5

Из обзора вы можете представить 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. итератор (__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 member *cur
    return *start;
}

reference back(){
    // cna't use *finish
    iterator tmp = finish;
    --tmp; 
    return *tmp; //return finish  *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, и теперь отправим 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.

Ответ 6

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

Ответ 7

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

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

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

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