Какая структура данных, в точности, является deques в С++?

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

Я всегда полагал, что deque был круговой буфер, но я недавно читал ссылку на С++ здесь, и это звучит как deque - это какой-то массив массивов. Кажется, это не простой старый круговой буфер. Это буфер пробелов, затем или некоторый другой вариант растущего массива, или это просто зависит от реализации?

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

Похоже, общий консенсус заключается в том, что 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 и не имеет ничего скопированного с ним (поэтому параметр resize op равен O (1), если распределение кучи является сложностью O (1)). Так как вспомогательные копии 2 элементов для каждого элемента, добавленного в первичный и первичный, запускаются не более половины, невозможно, чтобы вспомогательный элемент не догнал первичный к моменту, когда первичный пробег снова исчезнет. Удаление также просто нужно удалить 1 элемент из первичного и 0 или 1 из вспомогательного. Таким образом, если предположить, что распределение кучи O (1), эта реализация выполняет условие 1). Мы делаем массив из T * и используем new всякий раз, когда вставляем для выполнения условий 2) и 3). Наконец, 4) выполняется, потому что мы используем структуру массива и можем легко реализовать доступ O (1).

Ответы

Ответ 1

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

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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/capacity). Поскольку указатели тривиально скопированы, возможен один вызов memcpy, поэтому на практике это в основном постоянный... но этого недостаточно для прохождения с летающими цветами.

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

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

  • Случайный доступ

и

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

Я знаю несколько "близких" совпадений:

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

Ответ 4

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

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

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

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

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

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

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

'Для нашего 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. И мы обнаружили, что они независимы друг от друга. Поскольку стандарт требует, чтобы сложность выполнялась с точки зрения операций-on-T, мы можем сказать, что это имеет постоянную сложность.

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

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

Ответ 5

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

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

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

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

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

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

Ответ 6

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

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

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

Балансировка нагрузки обоих буферов требует перемещения между 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 образует правильный круг в первичном кольце.