Вопрос по c++11, c++, c++-faq – Как эффективно выбрать контейнер стандартной библиотеки в C ++ 11?

127

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

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

Это предыдущий: eC++ Container choice

@ WeaselFox: это уже частьC++-Faq здесь на ТАК. Alok Save
В C ++ 11 появился только один новый истинный тип контейнера: контейнеры unordered_X. Их включение только значительно запутало бы таблицу, поскольку при принятии решения о целесообразности использования хэш-таблицы необходимо учитывать ряд факторов. Nicol Bolas
Джеймс прав, есть больше случаев использовать вектор, чем показано в таблице. Преимущество локальности данных во многих случаях превосходит неэффективность некоторых операций (более скоро C ++ 11). Я не нахожу электронную диаграмму настолько полезной даже для c ++ 03 David Rodríguez - dribeas
Никогда не видел этого раньше. Спасибо! WeaselFox
Это мило, но я думаю, что чтение любого распространенного учебника по структурам данных оставит вас в состоянии, при котором вы не только сможете заново изобрести эту блок-схему за несколько минут, но и узнаете намного больше полезных вещей, которые эта блокнот замалчивает. Andrew Tomazos

Ваш Ответ

4   ответа
23

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

@NO_NAME Вау, я радsomebody надоело ссылаться на источник.
Вот автор этого изображения:stackoverflow.com/a/22671607/3052438
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

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

91

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

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

Choose for semantics first When several choices are available, go for the simplest

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

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

Associative containers: they have a find operation Simple Sequence containers

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

Вопрос 1:Associative ?

If you need to easily search by one key, then you need an associative container If you need to have the elements sorted, then you need an ordered associative container Otherwise, jump to the question 2.

Вопрос 1.1:Ordered ?

If you do not need a specific order, use an unordered_ container, otherwise use its traditional ordered counterpart.

Вопрос 1.2:Separate Key ?

If the key is separate from the value, use a map, otherwise use a set

Вопрос 1.3:Duplicates ?

If you want to keep duplicates, use a multi, otherwise do not.

Пример:

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

I want a find function, thus an associative container

1.1. I couldn't care less about order, thus an unordered_ container

1.2. My key (ID) is separate from the value it is associated with, thus a map

1.3. The ID is unique, thus no duplicate should creep in.

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

Вопрос 2:Memory stable ?

If the elements should be stable in memory (ie, they should not move around when the container itself is modified), then use some list Otherwise, jump to question 3.

Вопрос 2.1:Which ?

Settle for a list; a forward_list is only useful for lesser memory footprint.

Вопрос 3:Dynamically sized ?

If the container has a known size (at compilation time), and this size will not be altered during the course of the program, and the elements are default constructible or you can provide a full initialization list (using the { ... } syntax), then use an array. It replaces the traditional C-array, but with convenient functions. Otherwise, jump to question 4.

Вопрос 4:Double-ended ?

If you wish to be able to remove items from both the front and back, then use a deque, otherwise use a vector.

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

+1, но с некоторыми заметками: 1)array не требует конструируемого типа по умолчанию; 2) выбираемmultis не столько о дубликатах,allowed но больше о томkeeping они имеют значение (вы можете поместить дубликаты вmulti контейнеры, бывает так, что хранится только один).
Пример немного не соответствует. 1) мы можем "найти" (не функция-член, «алгоритм»> один) в неассоциативном контейнере, 1.1), если нам нужно найти «эффективно», а unordered_ будет O (1), а не O (log n) , BlakBat
Я действительно должен привыкнуть к этому лямбда-синтаксису ... BlakBat
@ R.MartinhoFernandes: Спасибо, отредактировано в.
@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), это не влияет на семантику; Я удалю «эффективно» из примера и замените его на «легко».
47

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

When to NOT use std::vector

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

Constructors

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

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

Needs Bools

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

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

Searching

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

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

Use a map when the search tag is not the same thing as the item you're looking for itself. Otherwise use a set. Use unordered when you have a lot of items in the container and search performance absolutely needs to be O(1), rather than O(logn). Use multi if you need multiple items to have the same search tag. Ordering

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

Или вы можете использовать отсортированныйstd::vector, но вы должны сохранить его отсортированным.

Stability

Когда итераторы и ссылки становятся недействительными, иногда возникает проблема. Если вам нужен список элементов, такой, что у вас есть итераторы / указатели на эти элементы в других местах, тоstd::vectorподход к признанию недействительным может не подходить. Любая операция вставки может вызвать недействительность в зависимости от текущего размера и емкости.

std::list предлагает твердую гарантию: итератор и связанные с ним ссылки / указатели становятся недействительными только тогда, когда сам элемент удаляется из контейнера.std::forward_list есть ли память, если серьезная проблема.

Если это слишком сильная гарантия,std::deque предлагает более слабую, но полезную гарантию. Инвалидация является результатом вставок в середине, но вставки в голову или хвост вызывают только недействительностьiterators, а не указатели / ссылки на элементы в контейнере.

Insertion Performance

std::vector только обеспечивает дешевую вставку в конце (и даже тогда, это становится дорогим, если вы дунете емкость).

std::list это дорого с точки зрения производительности (каждый вновь вставленный элемент стоит выделения памяти), но этоconsistent, Он также предлагает иногда незаменимую возможность перетасовывать предметы практически без потерь производительности, а также обмениваться предметами с другимиstd::list контейнеры одного типа без потери производительности. Если вам нужно перемешать вещи вокругa lotиспользоватьstd::list.

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

Следует отметить, что благодаря семантике перемещенияstd::vector производительность вставки может быть не такой плохой, как раньше. В некоторых реализациях реализована форма копирования элементов на основе семантики перемещения (так называемая «swaptimization»), но теперь, когда перемещение является частью языка, оно предписано стандартом.

No Dynamic Allocations

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

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

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

Похожие вопросы