Как я могу эффективно выбрать контейнер стандартной библиотеки в C ++ 11?
135
Есть хорошо известное изображение (шпаргалка) под названием «Выбор контейнера C ++». Это блок-схема, чтобы выбрать лучший контейнер для желаемого использования.
В 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, иначе - нет.
Пример:
Предположим, что у меня есть несколько человек с уникальным идентификатором, связанным с ними, и я хотел бы получить данные о человеке из его идентификатора как можно проще.
Я хочу findфункцию, таким образом, ассоциативный контейнер
1.1. Я не мог заботиться о заказе, поэтому unordered_контейнер
1.2. Мой ключ (ID) отделен от значения, с которым он связан, таким образом,map
1.3. Идентификатор уникален, поэтому дубликат не должен закрадываться.
Если элементы должны быть стабильны в памяти (то есть они не должны перемещаться при изменении самого контейнера), используйте некоторые list
В противном случае перейдите к вопросу 3.
Вопрос 2.1: который ?
Поселение для list; a forward_listполезен только для уменьшения занимаемой памяти.
Вопрос 3: Динамический размер ?
Если у контейнера есть известный размер (во время компиляции), и этот размер не будет изменен в течение программы, и элементы являются конструируемыми по умолчанию, или вы можете предоставить полный список инициализации (используя { ... }синтаксис), тогда используйте array, Он заменяет традиционный C-массив, но с удобными функциями.
В противном случае перейдите к вопросу 4.
Вопрос 4: двусторонний ?
Если вы хотите иметь возможность удалять предметы как спереди, так и сзади, тогда используйте a deque, в противном случае используйте a vector.
Вы заметите, что по умолчанию, если вам не нужен ассоциативный контейнер, ваш выбор будет a vector. Оказывается, это также рекомендация Саттера и Страуструпа .
+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. Таким образом, фактический размер может варьироваться, и вы получаете только одно выделение памяти (если вы не увеличите емкость).
Ну, мне тоже очень нравится ваш ответ :) 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имеет перегрузку, которая не принимает значения (она просто принимает новый размер; любые новые элементы будут создаваться по умолчанию на месте). Кроме того, почему компиляторы не могут правильно выровнять параметры-значения, даже если они объявлены с таким выравниванием?
@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::vectorNo: std::arrayNo: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::vectorNo: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_multimapNo: std::unordered_mapNo:Are elements read then removed in a certain order?Yes:Order is:Ordered by element: std::priority_queueFirst in First out: std::queueFirst in Last out: std::stackOther: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) Большому количеству элементов нужны собственные алгоритмы, а не разные контейнеры.
Ответы:
Не то, чтобы я знал, однако это может быть сделано в тексте, я думаю. Кроме того, график немного смещен, потому что
list
он не такой хороший контейнер в целом и не является таковымforward_list
. Оба списка являются очень специализированными контейнерами для нишевых приложений.Чтобы построить такую диаграмму, вам просто нужно два простых правила:
Вначале беспокоиться о производительности обычно бесполезно. Соображения, касающиеся больших О, действительно начинают действовать, когда вы начинаете обрабатывать несколько тысяч (или более) предметов.
Есть две большие категории контейнеров:
find
операцияа затем вы можете создать несколько адаптеров на них:
stack
,queue
,priority_queue
. Я оставлю здесь адаптеры, они достаточно специализированы, чтобы их можно было узнать.Вопрос 1: Ассоциативный ?
Вопрос 1.1: Заказал ?
unordered_
контейнер, в противном случае используйте его традиционный заказанный аналог.Вопрос 1.2: Отдельный ключ ?
map
, в противном случае используйте aset
Вопрос 1.3: Дубликаты ?
multi
, иначе - нет.Пример:
Предположим, что у меня есть несколько человек с уникальным идентификатором, связанным с ними, и я хотел бы получить данные о человеке из его идентификатора как можно проще.
Я хочу
find
функцию, таким образом, ассоциативный контейнер1.1. Я не мог заботиться о заказе, поэтому
unordered_
контейнер1.2. Мой ключ (ID) отделен от значения, с которым он связан, таким образом,
map
1.3. Идентификатор уникален, поэтому дубликат не должен закрадываться.
Окончательный ответ:
std::unordered_map<ID, PersonData>
.Вопрос 2: память стабильна ?
list
Вопрос 2.1: который ?
list
; aforward_list
полезен только для уменьшения занимаемой памяти.Вопрос 3: Динамический размер ?
{ ... }
синтаксис), тогда используйтеarray
, Он заменяет традиционный C-массив, но с удобными функциями.Вопрос 4: двусторонний ?
deque
, в противном случае используйте avector
.Вы заметите, что по умолчанию, если вам не нужен ассоциативный контейнер, ваш выбор будет a
vector
. Оказывается, это также рекомендация Саттера и Страуструпа .источник
array
не требует конструируемого типа по умолчанию; 2) выборmulti
s не столько о разрешении дубликатов, сколько о сохранении их значения (вы можете поместить дубликаты в не-multi
контейнеры, просто бывает, что хранится только один).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
было ли это свойство тоже?deque
элементы стабильны, только если вы нажмете / поп с любого конца; если вы начнете вставлять / стирать в середине, то до N / 2 элементов будут перетасовываться, чтобы заполнить созданный промежуток.Мне нравится ответ Матье, но я собираюсь пересказать блок-схему как это:
Когда НЕ использовать 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
поведение из контейнераbool
s, вы не получите егоstd::vector<bool>
. Так что вам придется сделать должным сstd::deque<bool>
.Поиск
Если вам нужно найти элементы в контейнере, а поисковый тег не может быть просто индексом, то вам, возможно, придется отказаться
std::vector
в пользуset
иmap
. Обратите внимание на ключевое слово « может »; Сортировкаstd::vector
иногда является разумной альтернативой. Или Boost.Containerflat_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
. Таким образом, фактический размер может варьироваться, и вы получаете только одно выделение памяти (если вы не увеличите емкость).источник
std::sort
, есть еще и то,std::inplace_merge
что интересно легко размещать новые элементы (а не вызовstd::lower_bound
+std::vector::insert
). Приятно узнатьflat_set
иflat_map
!vector<bool>
являетсяvector<char>
.std::allocator<T>
не поддерживает это выравнивание (и я не знаю, почему это не так), то вы всегда можете использовать свой собственный распределитель.std::vector::resize
имеет перегрузку, которая не принимает значения (она просто принимает новый размер; любые новые элементы будут создаваться по умолчанию на месте). Кроме того, почему компиляторы не могут правильно выровнять параметры-значения, даже если они объявлены с таким выравниванием?bitset
для bool, если вы заранее знаете размер en.cppreference.com/w/cpp/utility/bitsetВот версия C ++ 11 вышеупомянутой блок-схемы. [первоначально опубликовано без указания авторства, Микаэль Перссон ]
источник
Вот быстрое вращение, хотя это, вероятно, нуждается в работе
Вы можете заметить , что это отличается дико от C ++ 03 версии, в первую очередь в связи с тем , что я действительно не люблю связанные узлы. Связанные узлы-контейнеры обычно могут работать быстрее, чем несвязанные контейнеры, за исключением нескольких редких ситуаций. Если вы не знаете, что это за ситуации, и не имеете доступа к boost, не используйте контейнеры связанных узлов. (std :: list, std :: slist, std :: map, std :: multimap, std :: set, std :: multiset). Этот список фокусируется в основном на небольших и средних контейнерах, потому что (A) это 99,99% от того, с чем мы имеем дело в коде, и (B) Большому количеству элементов нужны собственные алгоритмы, а не разные контейнеры.
источник