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

поскольку

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

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

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

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

Чтобы понять разницу, нужно знать, как 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и это может вызвать операционная система, чтобы убить процесс, чтобы попытаться получить некоторую память. То, что он выберет, может оказаться не слишком приятным.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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