Многопоточные ассоциативные контейнеры в C++. Доклад Яндекса / Хабр
Из доклада старшего разработчика Сергея Мурылёва можно узнать о многопоточном ассоциативном контейнере для стандартной библиотеки, который разрабатывают в рамках WG21. Сергей рассказал о плюсах и минусах популярных решений этой задачи и о пути, выбранном разработчиками.
— Вы, наверное, уже догадались из названия, что сегодняшний доклад будет о том, как мы в рамках Рабочей группы 21 делали свой контейнер, похожий на std::unordered_map, но для многопоточной среды.
Во многих языках программирования — Java, C#, Python — такое уже есть и довольно широко используется. А в нашем горячо любимом, самом быстром и производительном C++ такого не оказалось. Но мы посовещались и решили такую штуку сделать.
Прежде чем добавить что-то в стандарт, надо подумать, как этим станут пользоваться люди. Потом сделать более правильный интерфейс, который будет с большой вероятностью принят комитетом — желательно, без каких-то поправок.
Самый известный и широко используемый вариант — кеширование больших тяжелых вычислений. Есть достаточно известный сервис Memcached, который просто кеширует ответы веб-серверов в памяти. Понятно, что сделать примерно то же самое можно на стороне своего приложения, если у тебя есть конкурентный ассоциативный контейнер. У того и другого подхода есть свои плюсы и минусы. Но если такого контейнера у тебя нет, придется либо делать свой велосипед, либо использовать какой-нибудь Memcached.
Следующим популярным случаем использования является дедупликация событий. Я думаю, многие в этой комнате пишут всякие распределенные системы и знают, что часто для связи между компонентами используются распределенные очереди, типа Apache Kafka и Amazon Kinesis. Они отличаются такой особенностью, что у них одно сообщение одному консьюмеру может приходить по несколько раз. Это называется у них at least once delivery, что означает гарантию доставки как минимум один раз: больше можно, меньше нельзя.
Рассмотрим это с точки зрения реальной жизни. Представим, что у нас есть какой-нибудь бэкенд какого-нибудь чатика или соцсети, где происходит обмен сообщениями. Это может привести к тому, что кто-то написал сообщение и кому-то потом пришло на мобильник несколько раз пуш-уведомление. Понятно, что если такое увидят пользователи, они этому не обрадуются. Утверждается, что эту проблему можно решить при помощи такого замечательного многопоточного контейнера.
Следующий, уже не так часто используемый случай — когда нам надо просто на стороне сервера что-то где-то сохранить, какие-то метаданные для пользователя. Например, мы можем сохранить время, когда пользователь последний раз проходил аутентификацию, чтобы понимать, когда следующий раз у него спрашивать логин и пароль.
Последний вариант на этом слайде — подсчет статистики. Из реальных применений в жизни можно привести пример использования в виртуальной машине от Facebook. Они сделали целую виртуальную машину, чтобы оптимизировать PHP и у себя в этой виртуальной машине они для всех встроенных функций стараются записывать в многопоточную хэш-таблицу аргументы, с которыми они назывались.
Добавить что-то большое и сложное в стандарт — не простая и не быстрая работа. Как правило, если происходит добавление чего-то большого, оно проходит через техническую спецификацию. В данный момент в стандарте идет большое движение по расширению поддержки многопоточности в стандартной библиотеке. И конкретно сейчас туда едет proposal P0260R3 про многопоточные очереди. Этот proposal — про очень похожую на нас структуру данных, и решения в дизайне у нас во многом похожи.
Собственно говоря, одним из основных концепций их дизайна является то, что у них интерфейс отличается от стандартного std::queue. В чем суть? Если посмотреть на стандартную очередь, то, чтобы из нее извлечь элемент, надо сделать две операции. Надо сделать операцию front, чтобы считать, и операцию pop, чтобы удалить. Если мы работаем в условиях многопоточности, то у нас может произойти какая-то операция над очередью между этими двумя вызовами, и может получиться так, что мы считаем один элемент, а удалим уже другой, что кажется концептуально неверным.
Еще у многопоточных очередей есть много разных имплементаций, которые решают несколько разных задач. Самая частая задача, это задача производителей и потребителей, когда у нас есть сколько-то потоков, которые производят какие-то задачи и есть сколько-то потоков, которые берут задачи из очереди и их обрабатывают.
Второй случай, это когда нам надо иметь просто какую-то синхронизованную очередь. В случае с производителями и потребителями у нас получается очередь, которая ограничена сверху и снизу. Если мы пытаемся, условно говоря, извлечь из пустой очереди, то мы переходим в состояние ожидание. И то же самое примерно происходит, если мы пытаемся добавить что-то, что не влезает по размеру в очередь.
Также в этом proposal’e описано, что у нас есть отдельно сделанный интерфейс, который позволяет различить, какая у нас имплементация внутри блокирующая, или lock free.
То, что тут везде в proposal пишется lock free, на самом деле в книжках это пишется, как wait free. Это означает, что у нас алгоритм отрабатывает за фиксированное количество операций. Lock free там означает немного другое, но это не суть.
Посмотрим на типичную схему того, как может выглядеть имплементация нашей хэш-таблицы, если она блокируется. Она у нас разбита на какое-то количество сегментов. Каждый сегмент, как правило, содержит какую-то блокировку, типа Mutex, Spinlock, или чего-нибудь еще более хитрого. И помимо Mutex или Spinlock она еще содержит внутри себя обычную хэш-таблицу, которая как раз таки этим делом защищена.
На данной картинке у нас нарисована хэш-таблица, которая сделана на списках. На самом деле, в нашей референсной имплементации мы написали хэш-таблицу с открытой адресацией из соображений производительности. Соображения производительности, в принципе, такие же, почему std::vector быстрее, чем std::list, потому что vector, условно говоря, хранится последовательно в памяти.
В самом начале, когда мы хотим найти что-то в этой хэш-таблице, мы берем хэш-код от ключа. Можно его взять по модулю и сделать что-то еще с ним такое, чтобы у нас получился номер сегмента, а уже в сегменте мы ищем, как в обычной хэш-таблице, но мы при этом, естественно, берем блокировку.
Основные идеи нашего дизайна. Конечно же, мы тоже сделали интерфейс, который не совпадает с std::unordered_map. Причина такая. У нас, например, в обычном std::unordered_map есть такая замечательная штука, как итераторы. Во-первых, не все имплементации могут их нормально поддержать. А те, которые могут поддержать, как правило, это какие-то lock free имплементации, которые требуют наличия либо garbage collection, либо каких-нибудь умных указателей, которые подчищают за ней память.
Помимо этого там есть еще несколько других типов операций, которые мы выкинули. На самом деле, итераторы, они во многих местах есть. Например, они есть на Java. Но, как правило, как это ни странно, они там никак не синхронизуются. И если вы попытаетесь что-то с ними сделать из разных потоков, то они могут легко перейти в невалидное состояние, и можно в Java получить exception, а если написать такое на плюсах, то это, скорее всего, будет undefined behavior, что еще хуже. И кстати, на тему undefined behavior: по-моему, товарищи из Facebook в своей библиотеке folly, которая выложена в опенсорс на GitHub, именно так и сделали. Просто скопировали интерфейс с Java и получили такие замечательные итераторы.
Еще у нас нет рекламации памяти, то есть если мы что то добавили в контейнер и заняли под это память, то обратно ее мы не отдадим, даже если удалить все. Еще одной предпосылкой к этому решению было то, что у нас внутри хеш таблица с открытой адресацией. Она работает на линейной структуре данных, которая как и vector не отдает обратно память.
Следующий концептуальный момент, это мы никогда ни при каких условиях никому наружу не отдаем ссылки и указатели на внутренние объекты. Это как раз таки было сделано с целью того, чтобы предотвратить необходимость наличия garbage collection, и чтобы не энфорсить умные указатели. Понятно, что если мы храним какие-то достаточно большие объекты, хранить их по значению внутри будет невыгодно. Но, в этом случае, мы их всегда можем обернуть их в какие-то умные указатели по своему выбору. И, если мы хотим, например, делать какую-то синхронизацию на значениях, мы можем их обернуть в какой-нибудь boost::synchronised_value.
Мы посмотрели на то, что какое-то время назад у класса shared_ptr убрали метод, который возвращал количество активных ссылок на этот объект. И пришли к выводу, что нам тоже надо выкинуть несколько функций, а именно, size, count, empty, buckets_count, потому что, как только мы возвращаем это значение из функции, оно сразу перестает быть валидным, потому что его кто-то может в этот же момент поменять.
Еще у нас на одном из прошлых заседаний просили, чтобы мы добавили своего рода режим, чтобы можно было обращаться в однопоточном режиме к нашему контейнеру, как к обычному std::unordered_map. Такая семантика позволяет явно отличить, где у нас происходит работа в многопоточном режиме, а где нет. И избежать каких-то неприятных ситуаций, когда люди берут многопоточный контейнер, ожидают, что у них все будет хорошо, берут итераторы, а потом неожиданно оказывается, что все плохо.
На этом заседании на Гавайях против нас написали целый proposal. 🙂 Нам сказали, что таким вещам не место в стандарте, потому что способов сделать свой многопоточный ассоциативный контейнер существует очень много.
У каждого есть свои плюсы и минусы — и непонятно, как использовать то, что у нас в итоге у нас получится. Как правило, оно используется, когда тебе нужен какой-то экстремальный перформанс. И вроде как наше коробочное решение не подходит, надо оптимизироваться под каждый конкретный случай.
n имплементаций, где n — количество различных фич.
В коде это выглядит примерно так. У нас есть какой-то параметр и какое-то количество предопределенных констант, которые туда можно передавать. Как ни странно, этот proposal отклонили.
Потому что, на самом деле, комитет уже занял позицию, что таким вещам быть, когда многопоточная очередь прошла через SG1. По этому вопросу даже не было голосования. Но на голосование были выставлены два вопроса.
Первый. Много людей захотели, чтобы мы на стороне нашей референсной имплементации поддержали чтение без взятия любых блокировок. Чтобы у нас было полностью не блокирующее чтение. Это, действительно, имеет смысл: как правило, самый популярный юзкейс — кеширование. И нам очень выгодно иметь быстрое чтение.
Второй момент. Все наслушались предыдущего товарища, который говорил про policy based design. У всех возникла идея — а что, давай я свою идею тоже потолкаю! И все проголосовали за то, чтобы policy based design был.
Хотя надо сказать, вся эта история длится достаточно давно, и перед нами этим занимались коллеги из Intel, Арч Робинсон и Антон Малахов. И у них уже было несколько proposals на эту тему. Они как раз таки предлагали добавить lock free-имплементацию на основе алгоритма SeepOrderedList. И у них тоже был policy based design как раз таки с рекламацией памяти.
И этот proposal не понравился Library Evolution Working Group. Его завернули с тем основанием, что у нас просто будет неограниченно расти количество слов в стандарте. Это будет просто невозможно адекватно проревьюить и просто реализовать в коде.
У нас замечаний к самим идеям нет. У нас есть замечания, по большей части, к референсной имплементации. И конечно, у нас есть пара идей, которые можно внести, чтобы было понятнее. Но по сути, мы в следующий раз пойдем примерно с тем же самым proposal. Мы искренне надеемся, что у нас не будет, как с модулями, пять заходов с одним и тем же proposal. Мы искренне верим в себя, и что в следующий заход нас пропустят дальше, и что Library Evolution Working Group все-таки настоит на своем мнении, не даст пропихивать policy based design.
Потому что наш оппонент не останавливается. Он решил доказывать всем, что это надо. Но, как говорится, время покажет. У меня все, спасибо за внимание.
C++названные требования:UnorderedAssociativeContainer Неупорядоченные ассоциативные контейнеры обеспечивают быстрый поиск объектов по ключам.
Неупорядоченные ассоциативные контейнеры – это контейнеры, которые обеспечивают быстрый поиск объектов на основе ключей. В худшем случае сложность линейна, но в среднем намного быстрее для большинства операций.
Неупорядоченные ассоциативные контейнеры параметризуются Key ; Hash , объект хеш -функции, который действует как хеш-функция для Key ; и Pred , BinaryPredicate , оценивающий эквивалентность между Key s. std::unordered_map и std::unordered_multimap также имеют сопоставленный тип T , связанный с Key .
Если два Key равны согласно Pred , Hash должен вернуть одинаковое значение для обоих ключей.
Если оба | (since C++20) |
std::unordered_map и std::unordered_set могут содержать не более одного элемента с заданным ключом, std::unordered_multiset и std::unordered_multimap могут содержать несколько элементов с одним и тем же ключом (которые всегда должны быть рядом при итерациях).
Для std::unordered_set и std::unordered_multiset тип значения совпадает с типом ключа, а iterator и const_iterator являются постоянными итераторами.
Для std::unordered_map и std::unordered_multimap тип значения — std::pair<const Key, T> .
Элементы в неупорядоченном ассоциативном контейнере организованы в ведра,ключи с одним и тем же хэшем окажутся в одном и том же ведре.Количество ведер увеличивается при увеличении размера контейнера,чтобы удержать среднее количество элементов в каждом ведре под определенным значением.
Восстановление делает недействительным итератор и может привести к переупорядочиванию элементов в разных ведрах,но не делает недействительными ссылки на элементы.
Неупорядоченные ассоциативные контейнеры соответствуют требованиям AllocatorAwareContainer . Для std::unordered_map и std::unordered_multimap требования value_type в AllocatorAwareContainer применяются к key_type и mapped_type (но не к value_type ).
Requirements
Legend | |
X | Container type |
a | Объект типа X |
b | const Объект типа X |
a_uniq | Объект в X , когда X поддерживает уникальные ключи |
a_eq | Объект в X , когда X поддерживает несколько эквивалентных ключей |
i, j | LegacyInputIterators, обозначающие допустимый диапазон |
p, q2 | действительный const_iterator к a |
q, q1 | разыменовываемое const_iterator в a обозначая допустимый диапазон |
il | Объект std::initializer_list<X::value_type> |
t | Объект типа X::value_type |
k | Объект типа X::key_type |
hf | const Объект типа X::hasher |
eq | const Объект типа X::key_equal |
n | Значение типа X::size_type |
z | Значение типа float |
| expression | return type | pre/requirements | post/effects | complexity |
|---|---|---|---|---|
X::key_type | Key | compile time | ||
X::mapped_type | T | std::unordered_map Только std::unordered_map и std::unordered_multimap | compile time | |
X::value_type | Key | std::unordered_set и std::unordered_multiset . Стирается в X | compile time | |
X::value_type | std::pair<const Key, T> | std::unordered_map и std::unordered_multimap . Стирается в X | compile time | |
X::hasher | Hash | Hash | compile time | |
X::key_equal | Pred | BinaryPredicate принимает два аргумента типа Key и выражает отношение эквивалентности. | compile time | |
X::local_iterator | LegacyIterator чья категория и тип такие же , как X::iterator | Может быть использован для итераций через одно ведро | compile time | |
X::const_local_iterator | LegacyIterator чья категории и типы такие же , как X::const_iterator | Может быть использован для итераций через одно ведро | compile time | |
X(n,hf,eq) | X | hasher и key_equal CopyConstructible | Создает пустой контейнер как минимум с n сегментами, используя данную хеш-функцию и предикат равенства | линейный по n |
X(n,hf) | X | hasherCopyConstructible, key_equalDefaultConstructible | Создает пустой контейнер как минимум с n сегментами, используя данную хеш-функцию и key_equal() качестве предиката равенства | линейный по n |
X(n) | X | hasher и key_equal DefaultConstructible | Создает пустой контейнер как минимум с n сегментами, используя hasher() качестве хэш-функции и key_equal() качестве предиката равенства | линейный по n |
X() | X | hasher и key_equal DefaultConstructible | Создает пустой контейнер с неопределенным количеством сегментов, используя hasher() качестве хэш-функции и key_equal() качестве предиката равенства | constant |
X(i,j,n,hf,eq) | X | hasher и key_equal CopyConstructible , value_type EmplaceConstructible в X из *i | Создает пустой контейнер с как минимум n сегментами, используя данную хеш-функцию и предикат равенства, и вставляет в него элементы из [i, j). | средний линейный, худший квадратин (на расстоянии между i и j ) |
X(i,j,n,hf) | X | key_equalDefaultConstructible | Как и выше, с eq=key_equal() | see above |
X(i,j,n) | X | hasherDefaultConstructible | Как и выше, с hf=hasher() | see above |
X(i,j) | X | Как и выше,с неопределённым количеством ведер | see above | |
X(il) | X | X(il.begin(),il.end() | see above | |
X(il,n) | X | X(il.begin(),il.end(),n | see above | |
X(il,n,hf) | X | X(il.begin(),il. | see above | |
X(il,n,hf,eq) | X | X(il.begin(),il.end(),n,hf,eq | see above | |
X(b) | X | Копировать конструкторы,также копировать хэш-функцию,предикатный и максимальный коэффициент нагрузки | средний линейный, худший квадратичный (в b.size() ) | |
a = b | X& | Назначение копирования,а также копирование хэш-функции,предиката и максимального коэффициента нагрузки | средний линейный, худший квадратичный (в b.size() ) | |
a = il | X& | value_type CopyAssignable и CopyInsertable в X | a = X(il) | see above |
end(),n,hfНеупорядоченные ассоциативные контейнеры в стандартной библиотеке
unordered_set (C++11) | коллекция уникальных ключей,хешированная ключами (class template) |
unordered_multiset (C++11) | коллекция ключей,хешированная ключами (class template) |
unordered_map (C++11) | коллекция пар ключ-значение,хешированные ключами,ключи уникальны (class template) |
unordered_multimap (C++11) | коллекция пар ключ-значение,хешированная ключами (class template) |
C++
-
C++названные требования:НеформатированныйOutputFunction .
Функция UnformattedOutputFunction-это поток,который выполняет следующее:Следующие функции стандартной библиотеки являются UnformattedOutputFunctions.
-
C++названные требования:УниформаРандоМБитГенератор
Равномерный генератор случайных битов-это функциональный объект,возвращающий беззнаковые целочисленные значения,такие,что каждый из возможных результатов имеет (в идеале)равную вероятность.
-
C++названные требования:ValueSwappable
Два объекта этого типа могут быть разыменованы и результирующие значения поменяны местами с использованием неквалифицированного контекста вызова функции,где оба пользовательских определения std::swap
-
Numerics library
Библиотека C++numerics включает в себя общие математические функции и типы,а также оптимизированные массивы,поддерживающие генерацию случайных чисел.
- 1
- …
- 2680
- 2681
- 2682
- 2683
- 2684
- …
- 4464
- Next
Последовательность против ассоциативных контейнеров в C++
Улучшить статью
Сохранить статью
- Уровень сложности: Средний
- Последнее обновление: 10 ноя, 2022
Улучшить статью
Сохранить статью
Контейнеры последовательности
В стандартной библиотеке шаблонов они относятся к группе шаблона класса контейнера , мы используем их для хранения данных.
Одно общее свойство, как следует из названия, состоит в том, что элементы 9Доступ к 0023 возможен последовательно.
Каждый из следующих контейнеров использует разные алгоритмы хранения данных, поэтому для разных операций они имеют разную скорость. И все элементы в контейнерах должны быть одного типа .
- array = Реализует неизменяемый массив .
например: int arr[10]; // массив фиксированного размера 10. - vector = Он реализует динамический массив с более быстрым произвольным доступом, они весьма полезны, так как в отличие от массивов они могут изменять размер.
пример: vectorv; // вектор типа int - dequeue Используется для реализации двусторонней очереди с более быстрым произвольным доступом
ex: dequeue dq; // удаление из очереди символьного типа - forward_list : реализует односвязный список.
например: forward_list fl; // forward_list типа int. Список - : реализует двойной связанный список .
пример: список л; // списки int
СписокАссоциативные контейнеры
В стандартных библиотеках шаблонов они относятся к группе шаблонов классов, используемых для реализации ассоциативных массивов . Они используются для хранения элементов, но на их элементы наложены некоторые ограничения.
И две важные характеристики этих контейнеров:
- Существует ключ. В случае карты и набора ключ уникален. В случае multimap и multiset допускается несколько значений ключа. В случае карты и мультикарты есть пары ключ-значение. В случае набора есть только ключи.
- Элементы следуют строгому слабому порядку. .
Это следующее, что относится к ассоциативным контейнерам
- map: здесь каждый создаваемый ключ должен быть уникальным.
пример: карта geek_no; // Здесь первый тип данных — это ключ, а второй тип данных — это значение - set: здесь также ключ, который мы создаем, должен быть уникальным, но одно важное отличие от карты заключается в том, что здесь само значение действует как ключ , поэтому это означает, что элементы в наборе уникальны, т. е. не повторяются.
пример: набор с; // само значение действует как ключ. - мультикарта: то же, что и карта, но здесь ключ должен быть , а не , чтобы быть уникальным.
пример: multimap geeks_no; - мультимножество: то же, что и множество, но здесь уникальность элементов не имеет значения , т.е. мы можем иметь один и тот же элемент несколько раз, в отличие от множества.
пример: мультимножественные метки;
е. не повторяются. Последовательность против ассоциативности (по сложности)
В контейнерах последовательности
- Простая вставка занимает постоянное время.
- Фронт имеет постоянное амортизированное время.
- Вставка посередине довольно медленная.
В ассоциативных контейнерах большая часть сложности выражена в логарифмическом выражении
- Добавление элемента равно O(log n)
- Удаление элемента O(log n)
- Поиск элемента O(log n)
- Увеличение или уменьшающий итератор O(1)(амортизированный)
- Вставка посередине выполняется быстрее.
Неупорядоченный ассоциативный контейнер
Обратите внимание, что у каждого ассоциативного контейнера есть неупорядоченный ассоциативный контейнер, который содержит элементы без определенного порядка. Примерами неупорядоченных ассоциативных контейнеров являются unordered_set, unordered_map, unordered_multimap, unordered_multiset.
Далее
Контейнеры в C++ STL (Стандартная библиотека шаблонов)
Статьи по теме
Что нового
Мы используем файлы cookie, чтобы обеспечить вам максимальное удобство просмотра нашего веб-сайта. Используя наш сайт, вы подтверждаете, что вы прочитали и поняли наши Политика в отношении файлов cookie и Политика конфиденциальности
Выбор правильного контейнера: ассоциативные контейнеры
30 августа 2017 г., Phillip Johnston • Последнее обновление 10 июня 2021 г.
Недавно я представил обзор стандартных типов контейнеров C++, а также общие рекомендации по выбору правильного контейнера.
Сегодня мы рассмотрим компромиссы ассоциативных контейнеров STL.
- Обзор
- Выбор между упорядоченными и неупорядоченными ассоциативными контейнерами
- Заказные контейнеры
- Неупорядоченные контейнеры
- Отличие контейнеров
- Дополнительное чтение
Обзор
В целом существует два типа ассоциативных контейнеров:
-
AssociativeContainer, который представляет упорядоченный контейнер , использующий поиск по ключу -
UnorderedAssociativeContainer, который использует хеширование для поиска по ключу
Упорядоченные ассоциативные контейнеры:
-
std::set, реализующий набор уникальных ключей, отсортированных по ключам -
std::map, который реализует набор пар ключ-значение, отсортированных по уникальным ключам -
std::multiset, который реализует набор, допускающий несколько записей для каждого ключа -
std::multimap, который реализует карту, допускающую несколько записей для каждого ключа
Неупорядоченные ассоциативные контейнеры:
-
std::unordered_set, который реализует набор уникальных ключей, хешированных по ключу -
std::unordered_map, который реализует набор пар ключ-значение, хешированных уникальными ключами -
std::unordered_multiset, который реализует неупорядоченный набор, допускающий несколько записей для каждого ключа -
std::unordered_multimap, который реализует неупорядоченную карту, допускающую несколько записей для каждого ключа
Выбор между упорядоченными и неупорядоченными ассоциативными контейнерами
Один из самых больших вопросов, которые у меня возникали, — «когда следует использовать карту по сравнению с unordered_map »? Конечно, в Интернете есть много мнений, и я еще не достиг полной ясности.
Однако я выделил некоторые общие детали и эмпирические правила, чтобы помочь вам выбрать между упорядоченными и неупорядоченными ассоциативными контейнерами.
Если вас волнует только производительность, я сэкономлю вам время: кажется, что unordered_map в целом имеет лучшую производительность.
Упорядоченные контейнеры
Каждый из ассоциативных контейнеров сортирует ключи при вставке, что обеспечивает сложность поиска O(log n).
Упорядоченные ассоциативные контейнеры используют схему размещения на основе узлов. Итераторы для всех элементов стабильны, и в C++17 вы даже можете перемещать элементы с одной карты на другую, не аннулируя их итераторы. Распределение памяти на основе узлов обеспечивает более согласованное время упорядоченных функций контейнера, поскольку им никогда не требуется выделять большие объемы памяти.
Используя упорядоченный контейнер, вы можете реализовать эффективный поиск по диапазонам или перебирать подмножества (например, работать со всеми элементами, где ключ > 100 ).
Если вы хотите использовать определяемый пользователем объект для ключа, вам нужно определить оператор «меньше» или реализовать новую функцию сравнения. Это может быть намного проще, чем реализация функции хеширования для вашего пользовательского типа данных.
Вам следует использовать упорядоченный ассоциативный контейнер, если:
- Вы предпочитаете древовидную структуру
- Вы не хотите тратить память на хранение хэш-таблицы
- Порядок или упорядоченный обход вашего набора данных имеет значение
- Хороший хэш данных ключа невозможен или замедляет работу
- Вы предпочитаете писать оператор сравнения для своего пользовательского типа данных вместо оператора хеширования
- Вам нужна гарантированная производительность (например, встроенные системы)
- Неупорядоченные контейнеры имеют сложность O(n) в наихудшем случае в случаях коллизий
Неупорядоченные контейнеры
Каждый из неупорядоченных ассоциативных контейнеров использует хешированные структуры данных, которые можно искать за амортизированное постоянное время (O(1) амортизировано).
Это означает, что большинство операций занимают постоянное время, хотя коллизии могут увеличить время работы до O(n) в худшем случае.
Неупорядоченные контейнеры требуют дополнительной памяти для хранения хэш-таблицы.
Если вы хотите использовать определяемый пользователем объект для ключа, вам необходимо реализовать определение std::hash для вашего ключа типа T и переопределите оператор == .
Вы должны использовать неупорядоченный ассоциативный контейнер, если:
- У вас есть память для хэш-таблицы
- Может выдерживать периодическую длительную работу
- Иметь хорошую функцию хеширования для уменьшения коллизий
- Вы используете строковые данные в качестве ключа
Различие контейнеров
Большинство различий между различными типами ассоциативных контейнеров связаны с 9Концепции контейнеров 0185 OrderedAssociative и UnorderedAssociative .
Поскольку мы уже рассмотрели эти две основные категории, давайте кратко рассмотрим подтипы: set , multiset , map и multimap . Примечания ниже относятся как к упорядоченным, так и к неупорядоченным ассоциативным контейнерам.
Контейнеры map поддерживают пары ключ-значение. Если вы просто ищете простую реализацию интерполяционной таблицы (или Perl-подобный ассоциативный массив), карта подтипа – это контейнер для вас. Контейнеры map поддерживают уникальные ключи: запись в ключ, который уже существует в структуре, перезапишет сохраненное значение.
Контейнеры set поддерживают ввод только ключей. Подобно карте , set поддерживает только уникальные ключи, хотя запись в уже существующий ключ является напрасной операцией. Набор пригодится для хранения коллекции уникальных вещей, таких как «темы, на которые мы подписаны» или «виды блюд, которые продает наш ресторан».
Если вам нужно сохранить значение с вашим ключом, вам нужен вместо карты .
Контейнеры multimap и multiset работают так же, как map и set , но не требуют уникальности ключей.
Контейнеры multimap полезны для группировки объектов, связанных друг с другом по ключу. Например:
- Почтовый индекс для ключа и люди, проживающие с этим почтовым индексом, в качестве значения .
- Word в качестве ключа и определение(я) в качестве значения
Мультимножество по своей концепции похоже на ключ со связанным целым числом. Вы можете получить количество каждый раз, когда запись появляется в мультинаборе .
В общем, в большинстве случаев вы будете придерживаться карт и наборов типов.
Дополнительная литература
- Обзор контейнеров C++ Часто задаваемые вопросы по ISO C++
- : контейнеры
-
AssociativeContainerКонцепция-
станд:: набор -
станд::карта -
станд::мультисет -
станд::мультимап
-
-
UnorderedAssociativeContainerКонцепция-
станд.
-
