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

Ответ 1

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

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

Ответ 2

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

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

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

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

• При выращивании или сжатии коллекции с любого конца
• Когда вы имеете дело с очень большими размерами коллекций.
• Когда вы работаете с bools, и вы действительно хотите bools, а не bitet.

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

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

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

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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

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

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

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

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

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

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

Ответ 9

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

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