C ++: Каковы причины выбора связанного списка / deque над вектором? [Дубликат]

Вот версия C ++ 11 приведенной выше блок-схемы. [изначально опубликовано без атрибуции его оригинального автора, Микаэль Перссон ]

[/g1]

Вот быстрый поворот, хотя ему, вероятно, нужна работа

Should the container let you manage the order of the elements?
Yes:
  Will the container contain always exactly the same number of elements? 
  Yes:
    Does the container need a fast move operator?
    Yes: std::vector
    No: std::array
  No:
    Do you absolutely need stable iterators? (be certain!)
    Yes: boost::stable_vector (as a last case fallback, std::list)
    No: 
      Do inserts happen only at the ends?
      Yes: std::deque
      No: std::vector
No: 
  Are keys associated with Values?
  Yes:
    Do the keys need to be sorted?
    Yes: 
      Are there more than one value per key?
      Yes: boost::flat_map (as a last case fallback, std::map)
      No: boost::flat_multimap (as a last case fallback, std::map)
    No:
      Are there more than one value per key?
      Yes: std::unordered_multimap
      No: std::unordered_map
  No:
    Are elements read then removed in a certain order?
    Yes:
      Order is:
      Ordered by element: std::priority_queue
      First in First out: std::queue
      First in Last out: std::stack
      Other: Custom based on std::vector????? 
    No:
      Should the elements be sorted by value?
      Yes: boost::flat_set
      No: std::vector

Вы можете заметить, что это отличается от диким от версии C ++ 03, в первую очередь из-за того, что что мне действительно не нравятся связанные узлы. Контейнеры с связанными узлами обычно могут бить по производительности не связанным контейнером, за исключением нескольких редких ситуаций. Если вы не знаете, что такое ситуации, и у вас есть доступ к boost, не используйте контейнеры связанных узлов. (std :: list, std :: slist, std :: map, std :: multimap, std :: set, std :: multiset). В этом списке основное внимание уделяется контейнерам с малой и средней стороны, потому что (A) это 99,99% от того, что мы имеем в коде, и (B) Большое количество элементов требует специальных алгоритмов, а не разных контейнеров.

Мне нравится ответ Маттиу, но я собираюсь пересчитать блок-схему следующим образом:

Когда НЕ использовать std :: vector

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

Конструкторы

std::vector требуют, чтобы его содержимое было конструктивным, поскольку оно должно быть способный перемешать предметы вокруг. Это не страшная нагрузка на содержимое (обратите внимание, что конструкторы по умолчанию не требуются , благодаря emplace и т. Д.). Однако большинство других контейнеров не требуют какого-либо конкретного конструктора (опять же, благодаря emplace). Итак, если у вас есть объект, в котором вы абсолютно не можете реализовать конструктор перемещения, тогда вам нужно будет выбрать что-то еще.

A std::deque будет общей заменой, имеющей много свойств std::vector, но вы можете вставлять только на обоих концах deque. Вставки в середине требуют перемещения. A std::list не накладывает никаких требований на его содержимое.

Требует Bools

std::vector<bool> is ... not. Ну, это стандарт. Но в обычном смысле это не vector, так как операции, которые обычно разрешают std::vector, запрещены. И это, безусловно, не содержит bool s .

Поэтому, если вам нужно реальное поведение vector из контейнера из bool s, вы не собираетесь чтобы получить его от std::vector<bool>.

Поиск

Если вам нужно найти элементы в контейнере, а тег поиска не может быть просто индексом , вам может потребоваться отказаться от std::vector в пользу set и map. Обратите внимание на ключевое слово « может »; сортировка std::vector иногда является разумной альтернативой. Или Boost.Container's flat_set/map , который реализует сортировку std::vector.

В настоящее время существует четыре варианта их, каждый со своими собственными потребностями.

• Используйте тег map, если тег поиска не совпадает с тем элементом, который вы ищете. В противном случае используйте set.
• Используйте unordered, если у вас есть лот элементов в контейнере, а производительность поиска должна быть O(1), а не O(logn) ].
• Используйте multi, если вам нужно, чтобы несколько элементов имели один и тот же тег поиска.

Заказ

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

Или вы можете использовать отсортированный std::vector, но вам придется его сортировать.

Стабильность

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

std::list предлагает твердую гарантию: итератор и связанные с ним ссылки / указатели становятся недействительными только тогда, когда сам элемент удаляется из контейнера , std::forward_list есть, если память является серьезной проблемой.

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

Производительность вставки

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

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

std::deque обеспечивает вставку / удаление постоянной времени по голове и хвосту, но вставка в середине может быть довольно дорогостоящим. Поэтому, если вам нужно добавить / удалить вещи как спереди, так и сзади, возможно, вам понадобится std::deque.

Следует отметить, что благодаря семантике перемещения std::vector производительность вставки может быть не так плохо, как раньше. В некоторых реализациях реализована форма перемещения семантического элемента перемещения (так называемая «swaptimization»), но теперь, когда перемещение является частью языка, оно задано стандартом.

Нет динамических распределений

std::array - это прекрасный контейнер, если вы хотите наименьшее количество динамических распределений. Это всего лишь оболочка вокруг C-массива; это означает, что его размер должен быть известен в время компиляции . Если вы можете с этим справиться, используйте std::array.

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