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

135

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

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

Это предыдущий: Выбор контейнера eC ++

BlakBat
источник
6
Никогда не видел этого раньше. Спасибо!
WeaselFox
6
@WeaselFox: это уже часть C ++ - Faq здесь на SO.
Alok Save
4
В C ++ 11 появился только один новый истинный тип контейнера: контейнеры unordered_X. Их включение только значительно запутало бы таблицу, поскольку при принятии решения о целесообразности использования хэш-таблицы необходимо учитывать ряд факторов.
Никол Болас
13
Джеймс прав, есть больше случаев использовать вектор, чем показано в таблице. Преимущество локальности данных во многих случаях превосходит неэффективность некоторых операций (более скоро C ++ 11). Я не нахожу электронную диаграмму настолько полезной даже для c ++ 03
Дэвид Родригес - dribeas
33
Это мило, но я думаю, что чтение любого распространенного учебника по структурам данных оставит вас в состоянии, при котором вы не только сможете заново изобрести эту блок-схему за несколько минут, но и узнаете гораздо больше полезных вещей, которые эта блокнот замалчивает.
Эндрю Томазос

Ответы:

97

Не то, чтобы я знал, однако это может быть сделано в тексте, я думаю. Кроме того, график немного смещен, потому что 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. Оказывается, это также рекомендация Саттера и Страуструпа .

Матье М.
источник
5
+1, но с некоторыми примечаниями: 1) arrayне требует конструируемого типа по умолчанию; 2) выбор multis не столько о разрешении дубликатов, сколько о сохранении их значения (вы можете поместить дубликаты в не- multiконтейнеры, просто бывает, что хранится только один).
Р. Мартиньо Фернандес
2
Пример немного не такой. 1) мы можем «найти» (не функцию-член, «<алгоритм>») в неассоциативном контейнере, 1.1), если нам нужно найти «эффективно», и неупорядоченным_ будет O (1), а не O ( войти n).
BlakBat
4
@BlakBat: map.find(key)гораздо приятнее на вкус, чем std::find(map.begin(), map.end(), [&](decltype(map.front()) p) { return p.first < key; }));, поэтому, семантически важно, чтобы findэто была функция-член, а не функция из нее <algorithm>. Что касается O (1) против O (log n), это не влияет на семантику; Я удалю «эффективно» из примера и заменю на «легко».
Матье М.
«Если элементы должны быть стабильны в памяти ... тогда используйте некоторый список» ... хм, я думал, dequeбыло ли это свойство тоже?
Мартин Ба
@MartinBa: да и нет. В a dequeэлементы стабильны, только если вы нажмете / поп с любого конца; если вы начнете вставлять / стирать в середине, то до N / 2 элементов будут перетасовываться, чтобы заполнить созданный промежуток.
Матье М.
51

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

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

Николь Болас
источник
1
Ну, мне тоже очень нравится ваш ответ :) WRT, сохраняющий вектор отсортированным, кроме того std::sort, есть еще и то, std::inplace_mergeчто интересно легко размещать новые элементы (а не вызов std::lower_bound+ std::vector::insert). Приятно узнать flat_setи flat_map!
Матье М.
2
Вы также не можете использовать вектор с 16-байтовыми выровненными типами. Кроме того, также является хорошей заменой vector<bool>является vector<char>.
Обратный
@Inverse: «Вы также не можете использовать вектор с 16-байтовыми выровненными типами». Говорит кто? Если std::allocator<T>не поддерживает это выравнивание (и я не знаю, почему это не так), то вы всегда можете использовать свой собственный распределитель.
Никол Болас
2
@Inverse: C ++ 11 std::vector::resizeимеет перегрузку, которая не принимает значения (она просто принимает новый размер; любые новые элементы будут создаваться по умолчанию на месте). Кроме того, почему компиляторы не могут правильно выровнять параметры-значения, даже если они объявлены с таким выравниванием?
Никол Болас
1
bitsetдля bool, если вы заранее знаете размер en.cppreference.com/w/cpp/utility/bitset
bendervader
25

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

Васим Табразе
источник
2
@NO_NAME Вау, я рад, что кто-то потрудился процитировать источник.
underscore_d
1

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

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

Мытье утка
источник