Как я могу эффективно выбрать контейнер стандартной библиотеки в С++ 11?

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

Чтобы построить такую ​​диаграмму, вам просто нужны две простые рекомендации:

• Сначала выберите семантику
• Когда есть несколько вариантов, выбирайте самый простой

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

Есть две большие категории контейнеров:

• Ассоциативные контейнеры: у них есть операция find
• Контейнеры Simple Sequence

а потом поверх них можно построить несколько адаптеров: stack, queue, priority_queue. Я оставлю здесь адаптеры, они достаточно специализированы, чтобы быть узнаваемыми.

Вопрос 1: Ассоциативный?

• Если вам нужно легко искать по одному ключу, вам нужен ассоциативный контейнер
• Если вам нужно отсортировать элементы, вам нужен упорядоченный ассоциативный контейнер
• В противном случае переходите к вопросу 2.

Вопрос 1.1: Заказано?

• Если вам не нужен определенный порядок, используйте контейнер unordered_, в противном случае используйте его традиционный упорядоченный аналог.

Вопрос 1.2: Отдельный ключ?

• Если ключ отделен от значения, используйте map, в противном случае используйте set.

Вопрос 1.3: Дубликаты?

• Если вы хотите сохранить дубликаты, используйте multi, иначе не делайте этого.

Пример:

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

1. Мне нужна функция find, то есть ассоциативный контейнер

1.1. Мне наплевать на порядок, поэтому контейнер unordered_

1.2. Мой ключ (ID) отделен от значения, с которым он связан, поэтому map

1.3. Идентификатор уникален, поэтому не должно быть дубликатов.

Окончательный ответ: std::unordered_map<ID, PersonData>.

Вопрос 2: Стабильная память?

• Если элементы должны быть стабильными в памяти (т. е. они не должны перемещаться при изменении самого контейнера), то используйте некоторые list
• В противном случае переходите к вопросу 3.

Вопрос 2.1: Какой?

• Соглашайтесь на list; forward_list полезен только для меньшего объема памяти.

Вопрос 3: Динамический размер?

• Если контейнер имеет известный размер (во время компиляции), и этот размер не будет изменен в ходе работы программы, и элементы являются конструируемыми по умолчанию или вы можете предоставить полный список инициализации (используя синтаксис { ... }), а затем использовать array. Он заменяет традиционный C-массив, но с удобными функциями.
• В противном случае переходите к вопросу 4.

Вопрос 4: Двусторонний?

• Если вы хотите иметь возможность удалять элементы как спереди, так и сзади, используйте deque, в противном случае используйте vector.

Вы заметите, что по умолчанию, если вам не нужен ассоциативный контейнер, ваш выбор будет vector. Оказывается, это также рекомендации Саттера и Страуструпа.

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

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

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

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

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

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

Нужны логические значения

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

Следовательно, если вам нужно настоящее vector поведение из контейнера bool, вы не получите его от std::vector<bool>. Так что вам придется заплатить std::deque<bool>.

Searching

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

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

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

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, прежде всего из-за того, что я очень не люблю связанные узлы. Контейнеры связанных узлов обычно могут быть лучше несвязанных контейнеров по производительности, за исключением нескольких редких ситуаций. Если вы не знаете, что это за ситуации, и у вас есть доступ к ускорению, не используйте контейнеры связанных узлов. (std::list, std::slist, std::map, std::multimap, std::set, std::multiset). Этот список в основном сосредоточен на малых и средних контейнерах, потому что (А) это 99,99% того, с чем мы имеем дело в коде, и (Б) для большого количества элементов нужны специальные алгоритмы, а не разные контейнеры.