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

Question

Поскольку

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

Почему кто-то предпочитает std::vector std::deque?

Answer 1

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

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

Answer 2

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

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

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

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

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

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

1. Стоимость перераспределения велика
2. Затраты на поиск смежного блока памяти ограничены,так что вы можете быстрее исчерпать память.

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

Answer 7

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

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

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

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

Answer 8

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

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

Answer 9

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