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

Question

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

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

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

Answer 1

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

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

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

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

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

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

и тогда вы можете построить несколько адаптеров поверх них: 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, Оказывается, это также рекомендация Саттера и Страуструпа.

Answer 2

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

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

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

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

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

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

Нуждается в Bools

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

Поэтому, если вам нужно реальное vector поведение из контейнера bool s, вы не получите его от 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 производительность вставки может быть не такой плохой, как раньше. В некоторых реализациях реализована форма копирования элементов на основе семантики перемещения (так называемая "сваптимизация"), но теперь, когда перемещение является частью языка, оно предписано стандартом.

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

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

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

Answer 3

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

Answer 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

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