Почему я предпочитаю использовать вектор для удаления

86

поскольку

  1. они оба являются непрерывными контейнерами памяти;
  2. Что касается функций, в deque есть почти все, что есть в векторе, но даже больше, поскольку его эффективнее вставлять спереди.

Почему whould кто предпочитает , std::vectorчтобы std::deque?

Леон
источник
2
Реализация Visual C ++ std::dequeимеет очень маленький максимальный размер блока (~ 16 байт, если я правильно помню; возможно, 32), и поэтому не очень хорошо работает для реалистичных приложений. A deque<T>where sizeof(T) > 8(или 16? Это небольшое число) имеет примерно те же характеристики производительности, что и a vector<T*>, где каждый элемент выделяется динамически. Другие реализации имеют разные максимальные размеры блоков, поэтому писать код с относительно одинаковыми характеристиками производительности на разных платформах сложно deque.
Джеймс МакНеллис
12
Deque не является непрерывным контейнером памяти.
Мохамед Эль-Накиб
@ravil Нет, это дубликат, указывающий на этот вопрос.
1
трудно поверить, что вопрос с нефиксированной явной фактической ошибкой находился на балансе в 34 голоса
underscore_d
2
@underscore_d вот почему это вопрос. Другая история, если бы это был ответ;)
Assimilater

Ответы:

115

Элементы в dequeявляются не смежными в памяти; vectorэлементы гарантированно будут. Так что, если вам нужно взаимодействовать с простой библиотекой C, которой требуются непрерывные массивы, или если вы (очень сильно) заботитесь о пространственной локальности, тогда вы можете предпочесть vector. Кроме того, поскольку существует некоторая дополнительная бухгалтерия, другие vectorоперации, вероятно, (немного) дороже, чем их эквивалентные операции. С другой стороны, использование многих / больших экземпляров vectorможет привести к ненужной фрагментации кучи (замедлению вызовов new).

Кроме того, как указано в другом месте на StackOverflow , здесь есть более интересное обсуждение: http://www.gotw.ca/gotw/054.htm .

фоджи
источник
3
Похоже, что ссылка на «другое место» теперь мертва (из-за модерации?).
esilk
37

Чтобы понять разницу, нужно знать, как dequeэто вообще реализовано. Память распределяется блоками равного размера, и они связаны вместе (как массив или, возможно, вектор).

Итак, чтобы найти n-й элемент, вы находите соответствующий блок, а затем получаете доступ к элементу внутри него. Это постоянное время, потому что это всегда ровно 2 поиска, но это все равно больше, чем вектор.

vectorтакже хорошо работает с API-интерфейсами, которым нужен непрерывный буфер, потому что они либо являются API-интерфейсами C, либо более универсальны с точки зрения возможности принимать указатель и длину. (Таким образом, у вас может быть вектор под ним или обычный массив и вызов API из вашего блока памяти).

Где dequeего самые большие преимущества:

  1. При увеличении или уменьшении коллекции с любого конца
  2. Когда вы имеете дело с очень большими коллекциями.
  3. Когда вы имеете дело с bools и вам действительно нужны bools, а не bitset.

Второй из них менее известен, но для очень больших размеров коллекции:

  1. Стоимость перераспределения велика
  2. Накладные расходы, связанные с поиском непрерывного блока памяти, являются ограничительными, поэтому вы можете быстрее исчерпать память.

Когда в прошлом я имел дело с большими коллекциями и перешел от непрерывной модели к блочной модели, мы смогли хранить примерно в 5 раз больше коллекции, прежде чем у нас закончилась память в 32-битной системе. Отчасти это связано с тем, что при перераспределении фактически необходимо было сохранить старый блок, а также новый, прежде чем копировать элементы.

Сказав все это, вы можете столкнуться с проблемами std::dequeв системах, которые используют «оптимистичное» распределение памяти. Хотя его попытки запросить большой размер буфера для перераспределения a vector, вероятно, будут отклонены в какой-то момент с помощью a bad_alloc, оптимистичный характер распределителя, вероятно, всегда будет предоставлять запрос на меньший буфер, запрошенный a, dequeи это может вызвать операционная система, чтобы убить процесс, чтобы попытаться получить некоторую память. То, что он выберет, может оказаться не слишком приятным.

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

Дойная корова
источник
29

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

Если вам нужна двусторонняя очередь, явным победителем будет deque. Но если вы делаете большую часть своих вставок и стираний на спине, вектор будет явным победителем. Если вы не уверены, объявите свой контейнер с помощью typedef (чтобы было легко переключаться туда и обратно) и измерьте.

Говард Хиннант
источник
3
Вопрос - рассматривал ли комитет добавление гибрида из двух (скажем, «колоды») в C ++? (т. е. двусторонний vector.) Я написал реализацию, ссылка на которую приведена ниже в моем ответе . Это может быть так же быстро, как и vectorгораздо более широко применимое (например, при создании быстрой очереди).
user541686
5

std::dequeне имеет гарантированной непрерывной памяти - и часто бывает несколько медленнее для индексированного доступа. Двусторонняя очередь обычно реализуется как «список векторов».

Эрик
источник
14
Я не думаю, что «список векторов» правильный: я понял, что большинство реализаций были «вектором указателей на массивы», хотя это зависит от вашего определения «списка» (я читаю «список» как «связанный список» , "что не соответствовало бы требованиям сложности.)
Джеймс МакНеллис
2

Согласно http://www.cplusplus.com/reference/stl/deque/ , «в отличие от векторов, deques не гарантируется, что все его элементы находятся в смежных местах хранения, что исключает возможность безопасного доступа с помощью арифметики указателей».

Deques немного сложнее, отчасти потому, что они не обязательно имеют непрерывную структуру памяти. Если вам нужна эта функция, вы не должны использовать двухстороннюю очередь.

(Раньше в моем ответе говорилось об отсутствии стандартизации (из того же источника, что и выше, «deques могут быть реализованы конкретными библиотеками по-разному»), но на самом деле это применимо практически к любому стандартному типу данных библиотеки.)

Патриквачек
источник
5
std::dequeне менее стандартизирован, чем std::vector. Я не верю, что требования к сложности std::dequeможно удовлетворить с помощью непрерывного хранилища.
Джерри Коффин
1
Возможно, моя формулировка была неудачной: хотя это правда, что стандартизация не является исчерпывающей, насколько я понимаю, векторы стандартизированы, чтобы представлять собой сопряженную последовательность, а deques - нет. Кажется, это единственный решающий фактор.
patrickvacek
1
@JerryCoffin: Какие требования к сложности dequeнельзя удовлетворить при непрерывном хранилище?
user541686
1
@Mehrdad: Если честно, я не помню, что имел в виду. Я не смотрел на эту часть стандарта в последнее время достаточно долго, чтобы с уверенностью утверждать категорически, что мой предыдущий комментарий был неправильным, но, глядя на него прямо сейчас, я тоже не могу думать, насколько он был бы правильным.
Джерри Коффин
3
@JerryCoffin: требования к сложности на самом деле тривиальны: вы можете выделить большой массив и начать продвигать свою последовательность от середины наружу (я думаю, это то, что делает реализация Mehrdad), а затем перераспределить, когда дойдете до концов. Проблема с этим подходом заключается в том, что он не удовлетворяет одному из требований deque, а именно, что вставка на концах не должна аннулировать ссылки на существующие элементы. Это требование подразумевает прерывистую память.
Яков Галка
0

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

Шон
источник
0

Я думаю, что это хорошая идея - проверять работоспособность каждого случая. И принимайте решение, опираясь на эти тесты.

Я бы предпочел, std::dequeчем std::vectorв большинстве случаев.

Джордж Гаал
источник
1
Вопрос, который можно выделить из фактических ошибок и пропущенных слов, заключался в следующем: почему кто-то предпочел бы vector. Мы можем сделать вывод, что почему не является следствием. Сказать, что вы dequeпо неизвестным причинам предпочитаете результаты неуказанных тестов, не является ответом.
underscore_d
0

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

Конечно, вы должны тестировать в своем приложении / среде, но в итоге:

  • push_back в основном одинаков для всех
  • вставка, стирание в двухсторонней очереди намного быстрее, чем список, и немного быстрее, чем вектор

Еще несколько размышлений и примечание для рассмотрения round_buffer.

Ник Вестгейт
источник
0

С одной стороны, vector довольно часто просто быстрее, чем deque. Если вы на самом деле не нужно все функции deque, используйте вектор.

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

Бен Гольдберг
источник
На самом деле, в одной push_backи той же серии pop_backопераций и deque<int>всегда, как минимум на 20% быстрее, чем vector<int>в моих тестах (gcc с O3). Думаю, именно поэтому dequeэто стандартный выбор для таких вещей, как std::stack...
игель
-1

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

Кроме того, если вы удалите элемент, итераторы станут недействительными (но не «for (auto ...)»).

Изменить: изменено 'deque' на 'vector'

Пьер
источник
-1: Вставка и стирание в начале или в конце НЕ делает недействительными ссылки и указатели на другие элементы. (Хотя вставка и стирание в середине делают)
Шёрд
@Sjoerd Я изменил его на "вектор".
Пьер,