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

Ответ 1

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

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

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

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

Существуют две большие категории контейнеров:

• Ассоциативные контейнеры: они имеют операцию find
• Контейнеры Simple Sequence

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

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

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

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

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

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

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

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

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

Пример:

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

• Я хочу функцию find, поэтому ассоциативный контейнер

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

  1,2. Мой ключ (ID) отделен от значения, с которым он связан, таким образом, map

  1,3. Идентификатор уникален, поэтому дубликат не должен появляться.

Последний ответ: std::unordered_map<ID, PersonData>.

Вопрос 2: Устойчивость к памяти?

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

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

• Установить для list; a forward_list полезен только для уменьшения объема памяти.

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

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

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

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

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

Ответ 2

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

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

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

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

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

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

Требует Bools

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

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

Поиск

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

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

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

Заказ

Если вам нужно, чтобы контейнер элементов всегда сортировался на основе конкретной операции сравнения, вы можете использовать set. Или a 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. Таким образом, фактический размер может меняться, и вы получаете только одно распределение памяти (если только вы не взорвали емкость).

Ответ 3

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

Ответ 4

Здесь быстрый поворот, хотя, вероятно, он нуждается в работе

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

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