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

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

Кто-нибудь знает, есть ли уже версия на C ++ 11?

Это предыдущий:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

1. Я хочу 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: двусторонний ?

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

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

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

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

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

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

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

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

Нужен Bools

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

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

Поиск

Если вам нужно найти элементы в контейнере, а поисковый тег не может быть просто индексом, то вам, возможно, придется отказаться std::vectorв пользу setи map. Обратите внимание на ключевое слово « может »; Сортировка std::vectorиногда является разумной альтернативой. Или Boost.Container 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. Таким образом, фактический размер может варьироваться, и вы получаете только одно выделение памяти (если вы не увеличите емкость).

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

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

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) Большому количеству элементов нужны собственные алгоритмы, а не разные контейнеры.