Почему std :: vector гораздо популярнее, чем std :: deque?

Question

Почему std :: vector гораздо популярнее, чем std :: deque?

Возможный дубликат:
Почему я предпочитаю использовать vector для деку

Мне любопытно, почему std::vector гораздо популярнее, чем std::deque. Deque почти так же эффективен при поиске, более эффективен при вставке (без vector :: reserve) и позволяет вставлять / удалять спереди.

Херб Саттер однажды рекомендовал если вы хотите использовать вектор, просто предпочитайте deque (Я перефразирую). Однако в недавнем разговоре о Написание современного C ++ он снова настоятельно рекомендует подумать о std::vector как контейнер по умолчанию. Согласно GOTW Я связал ранее, даже стандарт имеет аналогичную формулировку.

Есть ли причина для такого несоответствия? Это просто так vector проще и общеизвестно, или есть техническая причина? Или это vector это просто кулер имя ..?

51

c++deque vector

Решение

Другие решения

std::vector очень хорошо понят, прост и совместим с C (как с точки зрения разметки памяти, так и с точки зрения использования указателей в качестве итераторов).

Для некоторых операций это также более эффективно, чем std::deque, Доступ к элементам по индексу является одним из примеров.

Для данной задачи имеет смысл использовать простейший контейнер, который хорошо справляется со своей задачей. Во многих случаях этот самый простой контейнер std::vector,

14

Люди используют std :: vector вместо std :: deque по простой причине. Они взаимодействуют со многими библиотеками C и имеют функции с параметрами, для которых требуется указатель на непрерывное хранилище, что std :: deque не гарантирует (не может).

Другая причина заключается в том, что когда вы создаете код в соответствии с std :: deque, и ваши требования изменяются, так что вам приходится поддерживать непрерывный доступ, вам придется немного рефакторинга.

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

5

Структура std::deque немного сложнее, что делает наивную итерацию немного дороже, чем std::vector, Вставки в std::vector с его перераспределением, как правило, не является большой проблемой, особенно при использовании reserve() и только добавление до конца. Кроме того, есть более простые для понимания правила признания std::vector хотя на самом деле это преимущество std::deque что объекты остаются на месте при вставке / удалении только на обоих концах (обратите внимание, что std::deque итераторы становятся недействительными при каждой вставке, независимо от того, где вставка происходит). Еще один плюс для std:vector является гарантией того, что значения являются непрерывными в памяти, что приводит к меньшему выделению памяти.

Я думаю, я бы порекомендовал использовать std::deque алгоритмы были последовательно оптимизированы для использования сегментированных последовательностей (я не знаю, что любая стандартная библиотека C ++ делает эту оптимизацию), и пользователи обращались к последовательностям последовательно, используя алгоритмы (насколько я могу судить, только небольшая часть пользователей считает вариант использовать алгоритмы). Иначе я бы заподозрил, что std::deque это лучший вариант в отношении производительности, только если вы используете его специфические свойства (например, что объекты остаются на месте и что вы можете вставить / удалить в конце). Однако стоит описать две альтернативы.

5

Помимо std::vector Будучи наиболее известным контейнерным классом, он также имеет ряд преимуществ перед std::dequeа именно:

Типичный std::deque требует дополнительного косвенного доступа для доступа к элементам в отличие от случая std::vector,
Итераторы в случае std::deque должны быть умные указатели, а не указатели, как в случае std::vector,
Элементы std::vector гарантированно будут смежными и, следовательно, совместимы с функциями в стиле c, которые принимают массивы в качестве параметров.
std::deque не оказывают никакой поддержки, чтобы контролировать емкость и момент перераспределения.

Особенно последний пункт заслуживает внимания.

5

Источник

Accepted Answer

Я не могу говорить за кого-то еще, но я могу за себя.

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

Затем кто-то спросил о том, почему, и я подробно объяснил его достоинства и почему он был лучшим контейнером для использования практически во всем, и как он был гораздо более универсальным, чем std::vector,

К счастью, парень, ставящий под сомнение мое решение по этому поводу, был достаточно убедителен, и я провел некоторое тестирование. Тестирование показало, что почти в каждом случае std::deque был медленнее, чем std::vector — часто существенным фактором (например, около 2). На самом деле, из кода, который я написал, используя std::dequeзаменяю std::deque с std::vector ускорился во всех случаях, кроме нескольких.

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

Я должен добавить, однако, что я достаточно уверен, что при правильном мог быть почти эквивалентным std::vector практически во всех случаях. Большинство используют представление, которое, несомненно, великолепно с асимптотической точки зрения, но в реальном мире не работает так чудесно (для многих целей).

55