Какая структура данных, собственно, и есть требования в C ++?

Question

Существует ли конкретная структура данных, которую должна реализовывать deque в C ++ STL, или же это deque - это только смутное представление о массиве, растущем как спереди, так и сзади, которое будет реализовано, как выберет реализация?

Раньше я всегда предполагал, что deque - это циклический буфер , но я недавно читал ссылку на C ++ здесь , и звучит так, будто deque - это некий массив массивов. , Не похоже, что это обычный старый круговой буфер. Это буфер-пробел , или какой-то другой вариант расширяемого массива , или это просто зависит от реализации?

ОБНОВЛЕНИЕ И РЕЗЮМЕ ОТВЕТОВ :

Похоже, что общее мнение состоит в том, что deque - это структура данных, такая что:

• время для вставки или удаления элемента должно быть постоянным в начале или конце списка и самое большее линейным в других местах. Если мы интерпретируем это как истинное постоянное время, а не амортизированное постоянное время, как кто-то комментирует, это кажется сложной задачей. Некоторые утверждают, что мы не должны интерпретировать это как постоянное время без амортизации.
• «Для удаления требуется, чтобы при любой вставке любая ссылка на элемент-член оставалась действительной. Это нормально, если итераторы признаны недействительными, но сами члены должны оставаться в том же месте в памяти». Кто-то комментирует: Это достаточно просто, просто скопировав элементы куда-то в кучу и сохранив T * в структуре данных под капотом.
• «Вставка одного элемента в начале или в конце deque всегда занимает постоянное время и вызывает один вызов конструктора T». Единственный конструктор T также будет достигнут, если структура данных хранит T * под капотом.
• Структура данных должна иметь произвольный доступ.

Кажется, никто не знает, как получить комбинацию 1-го и 4-го условий, если мы примем первое условие как "неамортизированное постоянное время". Связанный список достигает 1), но не 4), тогда как типичный циклический буфер достигает 4), но не 1). Я думаю, что у меня есть реализация, которая выполняет оба ниже. Комментарии?

Мы начнем с реализации, которую предложил кто-то другой: мы выделяем массив и начинаем размещать элементы посередине, оставляя пространство как спереди, так и сзади. В этой реализации мы отслеживаем, сколько элементов находится от центра в обоих направлениях: передний и задний, вызываем эти значения F и B. Затем добавим в эту структуру данных вспомогательный массив, который в два раза больше исходного массив (так что теперь мы теряем тонну пространства, но без изменения асимптотической сложности). Мы также заполним этот вспомогательный массив из его середины и дадим ему аналогичные значения F 'и B'. Стратегия такова: каждый раз, когда мы добавляем один элемент в первичный массив в заданном направлении, если F> F 'или B> B' (в зависимости от направления), до двух значений копируются из первичный массив к вспомогательному массиву, пока F 'не догонит с F (или B' с B). Таким образом, операция вставки включает в себя помещение 1 элемента в первичный массив и копирование до 2 из первичного в вспомогательный, но это все равно O (1). Когда первичный массив заполняется, мы освобождаем первичный массив, делаем вспомогательный массив первичным массивом и делаем еще один вспомогательный массив, который еще в 2 раза больше. Этот новый вспомогательный массив начинается с F '= B' = 0 и в него ничего не копируется (поэтому операция изменения размера - это O (1), если выделение кучи - сложность O (1)). Поскольку вспомогательные элементы копируют 2 элемента для каждого элемента, добавляемого к первичному элементу, а первичный элемент запускается не более чем наполовину, вспомогательный элемент не может догнать первичный элемент к тому времени, когда первичному элементу снова не хватит места. Удаление также просто необходимо удалить 1 элемент из основного и 0 или 1 из вспомогательного. Таким образом, предполагая, что выделения кучи равны O (1), эта реализация удовлетворяет условию 1). Мы делаем массив из T * и используем new при вставке для выполнения условий 2) и 3). Наконец, 4) выполняется, потому что мы используем структуру массива и можем легко реализовать доступ O (1).

Answer 1

Это зависит от реализации. Все, что требуется для deque, - это постоянное время вставки / удаления в начале / конце, и самое большее линейное в других местах. Элементы не обязательно должны быть смежными.

Большинство реализаций используют то, что можно описать как развернутый список. Массивы фиксированного размера выделяются в куче, а указатели на эти массивы сохраняются в массиве динамического размера, принадлежащем деке.

Answer 2

Deque обычно реализуется как динамический массив массивов T.

 (a) (b) (c) (d)
 +-+ +-+ +-+ +-+
 | | | | | | | |
 +-+ +-+ +-+ +-+
  ^   ^   ^   ^
  |   |   |   |
+---+---+---+---+
| 1 | 8 | 8 | 3 | (reference)
+---+---+---+---+

Массивы (a), (b), (c) и (d) обычно имеют фиксированную емкость, а внутренние массивы (b) и (c) обязательно заполнены. (a) и (d) не заполнены, что дает вставку O (1) на обоих концах.

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

Эта реализация тривиально обеспечивает:

• Произвольный доступ
• Сохранение эталона при нажатии на обоих концах
• Вставка в середине, пропорциональная min(distance(begin, it), distance(it, end)) (Стандарт немного более строг, чем то, что вам требуется)

Однако это не соответствует требованию роста амортизированной O (1). Поскольку массивы имеют фиксированную емкость всякий раз, когда (опорный) вектор должен расти, у нас есть O (N / емкость) копий указателя. Поскольку указатели копируются тривиально, возможен один вызов memcpy, поэтому на практике он в основном постоянен ... но этого недостаточно для передачи с летающими цветами.

Тем не менее, push_front и push_back более эффективны, чем для vector (если только вы не используете реализацию MSVC, которая заведомо медленная из-за очень маленькой емкости для массивов ...)

---

Честно говоря, я не знаю ни структуры данных, ни комбинации структур данных, которые могли бы удовлетворить оба:

• Произвольный доступ

и

• O (1) вставка на обоих концах

Я знаю несколько "ближних" матчей:

• Вставка амортизированного O (1) может выполняться с помощью динамического массива, в котором вы пишете посередине, это несовместимо с семантикой «сохранения ссылок» deque
• Дерево B + может быть адаптировано для обеспечения доступа по индексу, а не по ключу, времена близки к константам, но сложность O (log N) для доступа и вставки (с небольшой константой), она требует использования Деревья Фенвика в узлах промежуточного уровня.
• Пальцевые деревья можно адаптировать аналогичным образом, опять же, это действительно O (log N).

Answer 3

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

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

"Вставка в любой конец очереди делает недействительными все итераторы в 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*, что означает, что мы можем игнорировать любую операцию, которая копирует (или перераспределяет) T*.

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

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

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

Эпилог: сложность vector :: push_back или vector :: push_front не имеет значения в этой реализации; эти соображения связаны с операциями на T* и, следовательно, не имеют значения.

Answer 4

(Создание этого ответа на вики-сообществе. Пожалуйста, застрять.)

Перво-наперво: A deque требует, чтобы любая вставка вперед или назад сохраняла любую ссылку на элемент member действительной,Это нормально для итераторов, которые будут признаны недействительными, но сами члены должны оставаться в том же месте в памяти.Это достаточно просто, просто скопировав элементы куда-то в кучу и сохранив T* в структуре данных под капотом.См. Этот другой вопрос StackOverflow " О дополнительной косвенности deque "

(vector не гарантирует сохранение итераторов или ссылок, тогда как list сохраняет оба).

Итак, давайте просто примем эту «косвенность» как само собой разумеющееся и рассмотрим остальную часть проблемы.Интересным моментом является время для вставки или удаления из начала или конца списка.Поначалу похоже, что deque можно легко реализовать с vector, возможно, интерпретируя его как циклический буфер .

НО Deque должен удовлетворять «Вставка одного элемента в начале или в конце deque всегда занимает постоянное время и вызывает один вызов конструктора T».

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

Answer 5

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

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 6

Это ответ на вызов пользователя gravity прокомментировать решение с двумя массивами.

• Некоторые детали обсуждаются здесь
• Дается предложение по улучшению

Обсуждение деталей: Пользователь «Гравитация» уже дал очень аккуратное резюме. «Гравитация» также заставила нас прокомментировать предложение сбалансировать количество элементов между двумя массивами, чтобы достичь времени выполнения O (1) в наихудшем (а не в среднем) случае. Что ж, решение работает эффективно, если оба массива являются кольцевыми буферами, и мне кажется, что достаточно разделить деку на два сегмента, сбалансированных как предложено. Я также думаю, что для практических целей стандартная реализация STL, по крайней мере, достаточно хороша, но в соответствии с требованиями реального времени и с должным образом настроенным управлением памятью можно рассмотреть использование этой техники балансировки. Существует также другая реализация, предложенная Эриком Демейном в более ранней статье Dr.Dobbs, с аналогичным временем выполнения в худшем случае.

Для балансировки нагрузки обоих буферов необходимо перемещаться между 0 или 3 элементами в зависимости от ситуации. Например, pushFront (x) должен, если мы сохраним передний сегмент в первичном массиве, переместить последние 3 элемента из первичного кольца во вспомогательное кольцо, чтобы сохранить необходимый баланс. PushBack (x) сзади должен получить разницу нагрузки, а затем решить, когда пора переместить один элемент из основного в вспомогательный массив.

Предложение по улучшению: Меньше работы и бухгалтерии, если передняя и задняя части хранятся во вспомогательном кольце. Этого можно достичь, разрезав деку на три сегмента q1, q2, q3, расположенных следующим образом: передняя часть q1 находится во вспомогательном кольце (удвоенного размера) и может начинаться с любого смещения, от которого элементы расположены по часовой стрелке в следующем порядке. Количество элементов в q1 составляет ровно половину всех элементов, хранящихся во вспомогательном кольце. Задняя часть q3 также находится во вспомогательном кольце, расположенном точно напротив относительно части q1 во вспомогательном кольце, также по часовой стрелке в следующем порядке. Этот инвариант должен храниться между всеми операциями deque. Только средняя часть q2 расположена (в следующем порядке по часовой стрелке) в первичном кольце.

Теперь каждая операция либо перемещает ровно один элемент, либо выделяет новый пустой кольцевой буфер, когда любой из них становится пустым. Например, pushFront (x) хранит x до q1 во вспомогательном кольце. Чтобы сохранить инвариант, мы перемещаем последний элемент из q2 в переднюю часть заднего q3. Таким образом, оба q1 и q3 получают дополнительный элемент на своих фронтах и, таким образом, остаются напротив друг друга. PopFront () работает наоборот, а тыловые операции работают так же. Первичное кольцо (так же, как и средняя часть q2) становится пустым ровно тогда, когда q1 и q3 касаются друг друга и образуют полный круг последующих элементов внутри вспомогательного кольца. Кроме того, когда deque сокращается, q1, q3 станут пустыми именно тогда, когда q2 образует правильный круг в первичном кольце.

Answer 7

Мое понимание deque

Он выделяет 'n' пустых смежных объектов из кучи в качестве первого подмассива. Объекты в нем добавляются ровно один раз указателем головы при вставке.

Когда указатель заголовка доходит до конца массива, он выделяет / связывает новый несмежный подмассив и добавляет туда объекты.

Они удаляются ровно один раз указателем хвоста при извлечении. Когда указатель хвоста завершает под-массив объектов, он перемещается на следующий связанный подмассив и освобождает старый.

Промежуточные объекты между головой и хвостом никогда не перемещаются в памяти деком.

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