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

чтобы узнать разницу, нужно знать, как deque обычно реализуется. Память выделяется в блоках равных размеров, и они соединены вместе (как массив или, возможно, вектор).

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

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

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

1. при увеличении или уменьшении коллекции с любого конца
2. когда вы имеете дело с очень большими размерами коллекции.
3. когда имеешь дело с булами, и вы действительно хотите булов скорее чем bitset.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

вы бы не предпочли vector deque acording to эти результаты теста (с источником).

конечно, вы должны проверить в своем приложении / среде, но в целом:

• push_back в основном то же самое для всех
• вставка, стирание в deque намного быстрее, чем список и незначительно быстрее, чем вектор

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

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

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