По какому принципу образуется порядок элементов в unordered_map?
Само название структуры подразумевает, что элементы в ней не отсортированы, но если перезапускать все время программу и выводить циклом элементы, то они всегда будут в одном порядке.
Например вот код из этой книги
Хэш формируется из сложения x и y , поэтому я думал, что по итоговому хэшу и будет выстроен порядок, но оказалось, что это так не работает.
Порядок вывода всегда такой:
Как это работает?
Для того, что бы ответить на вышеуказанный вопрос, для начала нужно понять, а как собственно устроен unordered_map изнутри. Есть два способа реализации, но самый простой и легкий из них — метод цепочек. Вроде он и применяется в стандартной библиотеке.
Сами данные хранятся в векторе списков. То есть так
когда нужно вставить элемент, то от индекса рассчитывается хеш (в нашем случае функция хеша должна уметь преобразовывать тип ключа в некое число в диапазоне 0..m_data.size()-1 . Обычно, хеш функция просто возвращает обычный int , а потом используется деление по модулю с помощью % . По полученному числу находится элемент вектора, в который в список и добавляется необходимый элемент (да, предварительно, проверяется, а нет ли такого элемента ещё).
Функция итерации по мапе обычно делается по простому — проходимся по всем элементам массива (вектора) и выводим элементы списка (опять же, в естественном порядке).
Теперь стает понятно, что при выводе элементов порядок будет определятся хеш функцией и тем, как элементы были вставлены в пределах одного и того же значения хеш функции.
Хеш функции обычно такие, что одному и тому же значению входного значения соответствует одно и тоже выходное значение (иначе это все работать не будет). Но с другой стороны, хеш функция старается максимально равномерно "размазать" значения хеша. Поэтому, если два значения (например, два int ) упорядочены по возрастанию, то значения хеш функции (идеальной конечно) будет упорядочены с вероятностью 50 на 50 (да, они могут совпасть, поэтому, наверно на самом деле это будет 49-49-2 или что то другое, похожее).
Чем же определяется хеш? его может явно задать программист, а может использоваться реализация от компилятора. Важно то, что с большущей вероятностью (если код не менялся), она не поменяется, а значит, значения хеша, которые определяют элемент вектора, будут те же.
Рекомендую попробовать написать свою реализацию unordered_map (того, что я написал выше уже достаточно для этого) и все вопросы пропадут сами собой.
Некоторые языки (например, golang) любят рандомизировать немного хеш функцию от запуска к запуску (для мнимой безопасности), тем самым доставляя кучу приятных впечатлений для молодых программистов.
Есть ещё одна реализация unordered_map — открытая адресация, но он немного сложнее, как по мне в реализции.
Какой map быстрее, и есть ли альтернатива Judy
Кадр из Top Gear: USA (серия 2)
В своих самых высоконагруженных сервисах мы в Badoo используем язык C и иногда C++. Зачастую эти сервисы хранят в памяти сотни гигабайт данных и обрабатывают сотни тысяч запросов в секунду. И нам важно использовать не только подходящие алгоритмы и структуры данных, но и производительные их реализации.
Практически с самого начала в качестве реализации ассоциативных массивов мы использовали Judy. У неё есть C-интерфейс и множество преимуществ. Мы даже используем обёртку для PHP, так как в версиях PHP до 7.0 Judy сильно выигрывает по количеству потребляемой памяти по сравнению со встроенными мапами.
Однако время идёт, и с момента последнего релиза Judy прошло немало лет – самое время посмотреть на альтернативы.
Меня зовут Марко, я – системный программист Badoo в команде «Платформа». Мы с коллегами провели небольшое исследование в поисках альтернатив Judy, сделали выводы и решили поделиться ими с вами.
Ассоциативный массив
Если вы знаете, что такое ассоциативный массив, дерево и хеш-таблица, этот раздел можете смело пропускать. Для остальных – небольшое введение в тему.
Ассоциативный массив – это абстрактный тип данных, который позволяет по ключу получать или сохранять значение. Абстрактный он, потому что ничего не говорит о том, как этот тип данных должен быть реализован. И правда, если немного пофантазировать, можно придумать десятки разных реализаций разного уровня адекватности.
Для примера можем взять банальный связный список. На put мы обойдём его весь от начала до конца, чтобы убедиться, что у нас ещё нет такого элемента, а если нет, то добавим его в конец списка; на get – просто обойдём список от начала до конца в поисках нужного элемента. Алгоритмическая сложность поиска и добавления элемента в такой ассоциативный массив – O(n), что не очень хорошо.
Из простых, но чуть более адекватных реализаций можно рассмотреть простой массив, элементы которого мы всегда будем держать отсортированными по ключу. Поиск в таком массиве можно осуществлять бинарным поиском, получив O(log(n)), но вот добавление в него элементов может потребовать копирования больших кусков памяти из-за необходимости освободить место под элемент в строго определённой позиции.
Если же посмотреть на то, как реализуются ассоциативные массивы на практике, то вероятнее всего мы увидим какое-либо дерево или хеш-таблицу.
Хеш-таблица
Хеш-таблица – это структура данных, реализующая ассоциативный массив, устройство которой представляет собой двухэтапный процесс.
На первом этапе наш ключ прогоняется через хеш-функцию. Это функция, которая на вход принимает набор байт (наш ключ), а на выходе обычно даёт какое-то число. Это число на втором этапе мы используем для поиска значения.
Как? Вариантов множество. Первое, что приходит в голову, — использовать это число в качестве индекса в обычном массиве. Массиве, в котором лежат наши значения. Но этот вариант не будет работать как минимум по двум причинам:
Область значений хеш-функции, скорее всего, больше, чем размер массива, который бы нам хотелось хранить выделенным в памяти.
Обе эти проблемы обычно решаются выделением массива ограниченного размера, каждый элемент которого является указателем на другой массив (bucket). Область значений нашей хеш-функции мы затем отображаем на размер первого массива.
Как? Вариантов, опять же, много. Например, взять остаток от деления на размер массива или просто взять нужное количество младших бит числа, если размер массива у нас является степенью двойки (остаток от деления – значительно более медленная операция для процессора по сравнению со сдвигом, так что обычно предпочтение отдаётся именно массивам с размером, являющимся степенью двойки).
Я привёл в пример один из распространённых способов реализации хеш-таблицы, но вообще их великое множество. И в зависимости от выбранного способа борьбы с коллизиями мы получим разную производительность. Если же говорить об алгоритмической сложности для хеш-таблиц, то в среднем у нас будет O(1), а в вырожденных случаях (worst case) может получиться и O(n).
Деревья
С деревьями всё довольно просто. Для реализации ассоциативных массивов используются различные бинарные деревья – такие, как, например, красно-чёрное дерево. В случае если дерево сбалансировано, мы получим O(log n) на операцию.
Некоторые реализации деревьев, такие как google btree, учитывают современную иерархию памяти и хранят ключи пачками для более эффективного использования процессорных кешей.
Деревья позволяют реализовать обход элементов по возрастанию или убыванию ключей, что зачастую является очень важным условием при выборе реализации. Хеш-таблицы этого не умеют.
На что смотрим?
Мир ассоциативных массивов, конечно, не чёрно-белый: у каждой реализации есть как преимущества, так и недостатки.
Разные реализации могут отличаться не только производительностью, но и набором предоставляемых функций. К примеру, какие-то реализации позволяют обходить элементы в порядке возрастания или убывания ключа, а какие-то – нет. И это ограничение связано с внутренней архитектурой, а не прихотями автора.
Да и банальная производительность может сильно отличаться в зависимости от того, каким образом вы используете ассоциативный массив: в основном пишете в него или читаете, читаете ключи в произвольном порядке или последовательно.
Прошли времена, когда О-нотации Кнута было достаточно для сравнения двух алгоритмов. Реальный мир гораздо сложнее. Современное железо, на котором работают наши программы, имеет многоуровневую память, доступ к разным уровням которой сильно отличается, и учёт этого может ускорить алгоритм в разы или на столько же его замедлить.
Немаловажным критерием является и вопрос потребления памяти: какой оверхед у выбранной реализации по сравнению с теоретическим минимумом (размер ключа + размер значения, умноженные на количество элементов) и допустим ли такой оверхед в нашей программе?
Паузы, максимальная задержка (latency) и отзывчивость тоже играют важную роль. Некоторые реализации ассоциативных массивов требуют одномоментного дорогостоящего перестроения своих внутренних структур при добавлении элемента, которому не повезло, а другие – «размазывают» эти задержки во времени.
Участники исследования
Judy (или Judy Array) – структура, придуманная Дугласом Баскинсом, реализующая упорядоченный ассоциативный массив. Реализация написана на C и крайне сложна. Автор попытался учесть современную архитектуру и использовать кеши процессора по максимуму.
Judy представляет из себя дерево, а не хеш-таблицу. И не просто дерево, а так называемое префиксное дерево. Для нас, потребителей, это означает, что, используя Judy, мы получаем сжатие ключей и возможность бежать по элементам в порядке возрастания или убывания ключа.
Judy предоставляет несколько вариаций «ключ/значение»:
| Вариация | Ключ | Значение |
|---|---|---|
| Judy1 | uint64_t | bit |
| JudyL | uint64_t | uint64_t |
| JudySL | null-terminated string | uint64_t |
| JudyHS | array of bytes | uint64_t |
Judy1 удобно использовать для больших разреженных bitmap‘ов. JudyL является базовым типом, который мы в C-сервисах Badoo чаще всего и используем. JudySL, как видно, удобно использовать для строк, а JudyHL – просто для какого-то набора байт.
std::unordered_map
unordered_map реализован на C++ в виде шаблона, так что в качестве ключа и значения может выступать всё что угодно. В случае использования нестандартных типов вам придётся определить функцию для хеширования этих типов.
Это именно хеш-таблица, так что обход ключей по возрастанию или убыванию недоступен.
google::sparse_hash_map
Как видно из названия, sparse hash был разработан в Google и заявляет минимальный оверхед в размере всего два бита на значение. Он также реализован на C++ и сделан в виде шаблона (и это, на мой взгляд, несомненное преимущество реализаций на C++).
Кроме всего прочего, sparse hash умеет сохранять своё состояние на диск и загружаться с него.
google::dense_hash_map
Кроме sparse hash, Google сделала вариант под названием dense hash. Скорость у него (а особенно скорость get‘а) заметно выше, но за это приходится платить большим расходом памяти. Также, из-за того, что внутри у dense_hash_map плоские массивы, периодически требуется дорогое перестроение. Кстати, о таких проблемах и нюансах хеш-таблиц отлично рассказал Константин Осипов в своём докладе на HighLoad++. Рекомендую к изучению.
В случае если количество данных, которые вы храните в ассоциативном массиве невелико и его размер не будет сильно меняться, dense hash должен подойти вам лучше всего.
Аналогично sparse hash dense hash является хеш-таблицей и шаблоном. То есть, повторюсь, никакого прохождения по ключам в порядке возрастания, но при этом возможность использовать любые типы в качестве ключей и значений.
Также аналогично своему собрату sparse_hash_map dense_hash_map умеет сохранять своё состояние на диск.
spp::sparse_hash_map
И, наконец, последний претендент от одного из разработчиков google sparse hash. Автор взял за основу sparse hash и переосмыслил его, добившись минимального оверхеда в один бит на запись.
Всё то же самое: хеш-таблица и шаблон. Реализация на C++.
Претенденты представлены – пришло время проверить, на что они способны.
Ещё два фактора
Но сначала замечу, что на производительность и потребление памяти будут влиять ещё две вещи.
Хеш-функция
Все участники нашего исследования, являющиеся хеш-таблицами, используют хеш-функции.
У хеш-функций довольно много свойств, каждое из которых может быть более или менее важно в зависимости от области. Например, в криптографии важно, чтобы минимальное изменение входящих данных приводило к как можно большему изменению в результате.
Но нас больше всего интересует скорость. Производительность хеш-функций может сильно отличаться, и скорость часто зависит от того количества данных, которое им «скармливается». Когда на вход в хеш-функцию подаётся длинная цепочка байт, может быть целесообразно применение SIMD-инструкций для более эффективного использования возможностей современных процессоров.
В дополнение к стандартной хеш-функции из C++ я посмотрю, как справятся xxhash и t1ha.
Аллокация памяти
Второй фактор, который обязательно повлияет на наши результаты, — аллокатор памяти. От него напрямую зависят и скорость работы, и количество потребляемой памяти. Стандартный аллокатор из libc – это jack of all trades. Он хорош для всего, но ни для чего не идеален.
В качестве альтернативы я рассмотрю jemalloc. Несмотря на то, что в тесте мы не воспользуемся одним из его основных преимуществ – работой с многопоточностью – я ожидаю более быструю работу с этим аллокатором.
Результаты
Ниже представлены результаты теста по рандомному поиску среди десяти миллионов элементов. Два параметра, которые меня больше всего интересуют, – время выполнения теста и максимальная потреблённая память (RSS процесса в пике).
В качестве ключа я использовал 32-битное целое, а в качестве значения – указатель (64 бита). Именно такие размеры ключей и значений мы чаще всего используем.
Я не стал показывать результаты других тестов, которые представлены в репозитории, так как меня больше всего интересовали именно рандомный get и потребляемая память.
Самым быстрым ассоциативным массивом оказался dense hash от Google. Следом идёт spp, и затем – std::unordered_map.
Однако если посмотреть на память, видно, что dense_hash_map потребляет её больше всех других реализаций. Собственно, именно это сказано в документации. Более того, если бы у нас в тесте были конкурирующие чтение и запись, мы бы, скорее всего, столкнулись со stop-the-world-перестроением. Таким образом, в приложениях, где важна отзывчивость и много записей, dense hash использовать нельзя.
Также я посмотрел на альтернативные реализации хеш-функций. Но, как оказалось, стандартная std::hash быстрее.
Коллега случайно заметил, что в случае 32- или 64-битных ключей std::hash по сути просто identity. То есть на входе и выходе – одно и то же число, или, другими словами, функция ничего не делает. хxhash и t1ha же честно считают хеш.
В плане производительности jemalloc полезен. Практически все реализации становятся быстрее.
Однако по потреблению памяти jemalloc не настолько хорош.
Исходный код и железо
Исходный код бенчмарков я выложил на github. При желании вы можете повторить мои тесты или расширить их.
Я же проводил тестирование на своём домашнем десктопе:
- Ubuntu 17.04
- Linux 4.10.0
- Intel® Core(TM) i7-6700K CPU @ 4.00GHz
- 32 GiB DDR4 memory
- GCC 6.3.0
- Флаги компилятора: -std=c++11 -O3 -ffast-math
Краткие выводы и заключительные слова
Наши тесты показали хороший потенциал spp в качестве замены Judy. spp оказался быстрее на рандомных get‘ах, а его оверхед по памяти не слишком велик.
Мы сделали простенькую обёртку над C++ для C и в ближайшее время попробуем spp в одном из своих высоконагруженных сервисов.
Ну, и в качестве совсем философского заключения скажу, что у каждой из рассмотренных нами реализаций есть свои плюсы и минусы и выбирать следует, основываясь на решаемой задаче. Понимание их внутреннего устройства поможет вам сопоставить задачу и решение, и это понимание зачастую отличает простого инженера от продвинутого.
Как работает unordered map
CodingJellyfish → Stuck in purple
PaciukZvichainyi → Google vs Microsoft
low_ → [Rated, Prizes!] DYTECHLAB Cup 2022 Round Announcement [Div.1 + Div.2]
gs15120 → Am I too stupid to be red?
ICPCNews → ICPC 2022 Online Challenge powered by HUAWEI
Akulyat → Codeforces Round #824 — editorial
ibraGYM → FINALLY GREEN, BRUUUH
FBI → Actually,am I the only one who is tired of this?
DPR-pavlin → Moscow pre-finals Workshop 2022: анонс
FedeNQ → Teams going to ICPC WF 2021 (Dhaka 2022) — WIP List
wiiiw → $1500 to participate in the ACM ACPC ? but why ??
SlavicG → How to use Codeforces [GUIDE]
Akulyat → Codeforces Round #824 (Div. 2)
dostseferoglu22 → Green.
Bottom → Ошибка исполнения на тесте 1
Farsh_limit_exceeded → Advices to reach candidate soon ):
Rshittttt → Can Obfuscation fool the system? (Cheating in round #824 problem C)
Hexagons → Survey About Minecraft
un_known27 → Hi neoyg!
Jo3kerR → NITS Hacks 5.0 Inter College Coding Competition (Prizes worth 100K INR)
m aroonrk → AtCoder Regular Contest 149 Announcement
aopo → How to solve this grid problem ?
milind0110 → ICPC Kanpur Regionals 2021 Solution Discussion
Halym2007 → How to become good at dp
rama_pang → Invitation to TOKI Indonesian NOI Open Contest 2022
Блог пользователя Arpa
[Tutorial] Everything about unordered_map
Автор Arpa, история, 7 лет назад ,
UPD: Tricks to make unordered_map faster added.
What is unordered_map ?
It is a data structure like map but it is more than 4 times faster than map .you can use it in C++11 with including #include<unordered_map> .for example:
Lets explain it more.
How it works?
Focus on unordered_set for simplify.You can imagine that it has vector of vector like vector<vector<type> > mp . Every time you insert value V in that, it calculate its hash (I will explain how it works), let hash(V)=K ; it inserts V into mp[K] (formally it calls mp[K].push_back(V) ).When you call mp.count(V) it searchs for V in mp[K] .
map VS unordered_map (and set VS unordered_set )
1- unordered_map is more than 4 times faster
Focus on problem 527E — Data Center Drama, it seems that it is good to use unordered_map instead of map .
My submission with map : 14269000 Time:484 MS.
My submission with unordered_map : 14269381 Time:358 MS.
Another good sample to show how fast is unordered_map is problem 178C3 — Smart Beaver and Resolving Collisions:
My submission with map : 15781810 Time limit exceeded on test 36 .
My submission with unordered_map : 15774685 Accepted (Time:966 MS).
2- unordered_set (and unordered_map ) is not sorted
Please note that set (and map ) is sorted, for example *(s.begin()) is always smallest number in the set; but in unordered_set it isn’t. similarly there isn’t lower_bound and upper_bound in unordered_set (and unordered_map similarly).
Creating hash function for structs
Now, one other problem remains, you can try to compile this code:
You will get Compilation Error! Why? See this page for unordered_map supported types. For unsupported types, you have to create your own hash function for use. For example lets see how we can create a hash function for pair<int,int> .
As you know any int value is between -2^31+1 to 2^31-1.so if we create function that for every pair<int,int> returns distinct value in type size_t (alias of unsigned int ), it will be done. It is pretty easy: x.first^(x.second<<32) is good. but be careful about overflow ;for having good hash function we use hash<long long> .The code is looks like this:
Now you have a unordered_map of pair<int,int> (it isn’t problem what is second member, in example it was int ).Creating hash function for other structs is same.
How to test unordered_map is faster than map ?
You can test that for N=10^6, unordered_set ( unordered_map ) is more than 4 times faster than set ( map ) ;with this code:(compile code with command: g++ file.cpp -std=c++11 -O2)
Note1: Let your hash function H(V) , it is better that H(V) returns distinct value for every distinct V , it makes unordered_map faster; but if you can’t do that it doesn’t problem. The only problem is that unordered_map becomes slower(however it is better than map ).
Note2: Please be careful about your hash function time complexly! it is fun to use this hash function:
UPD I will explain hash<type> in my next post.
UPD It seems that sometimes unordered_map becames so slow.but it can improve with this two lines of code:
With this two lines unordered_map become about 10 times faster. You can replace 1024 with another suitable power of two.(it depends on number of insert s you will do).
unordered_map, unordered_set, c++11
Неупорядоченная карта в C++
Программирование и разработка
Карта, также известная как ассоциативный массив, представляет собой список элементов, где каждый элемент представляет собой пару ключ / значение. Итак, каждый ключ соответствует значению. Для обычной работы разные ключи могут иметь одно и то же значение. Например, ключи могут быть списком фруктов и соответствующими значениями цветов фруктов. В C ++ карта реализована как структура данных с функциями-членами и операторами. Упорядоченная карта — это карта, в которой пары элементов упорядочены по ключам. Неупорядоченная карта — это карта, на которой нет порядка. В этой статье объясняется, как использовать неупорядоченную карту C ++, записанную как unordered_map. Чтобы понять эту статью, вам понадобятся знания указателей C ++. unordered_map является частью стандартной библиотеки C ++.
Класс и объекты
Класс — это набор переменных и функций, которые работают вместе, где переменным не присвоены значения. Когда переменным присваиваются значения, класс становится объектом. Различные значения, присвоенные одному и тому же классу, приводят к разным объектам; то есть разные объекты относятся к одному классу с разными значениями. Считается, что создание объекта из класса создает экземпляр объекта.
Название, unordered_map, это класс. Объект, созданный из класса unordered_map, имеет имя, выбранное программистом.
Функция, принадлежащая классу, необходима для создания экземпляра объекта из класса. В C ++ эта функция имеет то же имя, что и имя класса. Объекты, созданные (экземпляры) из класса, имеют разные имена, данные им программистом.
Создание объекта из класса означает создание объекта; это также означает создание экземпляра.
Программа на C ++, использующая класс unordered_map, начинается со следующих строк в верхней части файла:
#include <iostream>
#include <unordered_map>
using namespace std ;
Первая строка предназначена для ввода / вывода. Вторая строка позволяет программе использовать все возможности класса unordered_map. Третья строка позволяет программе использовать имена в стандартном пространстве имен.
Перегрузка функции
Когда две или более разных сигнатур функций имеют одно и то же имя, это имя считается перегруженным. Когда вызывается одна функция, количество и тип аргументов определяют, какая функция фактически выполняется.
Строительство / Копирование Строительство
Неупорядоченную карту можно построить и присвоить ей следующие значения:
Объявление начинается со специализации шаблона с типами для пар ключ и значение. За ним следует имя, выбранное программистом для карты; затем точка с запятой. Второй сегмент кода показывает, как присвоить значения их ключам.
Построение с помощью Initializer_list
Это можно сделать следующим образом:
Построение путем присвоения Initializer_list
Построение путем копирования другого
Пара <type1, type2> Element
Следующий код показывает, как создать элемент пары и получить к нему доступ:
first и second — зарезервированные слова для двух элементов в паре. Значения в паре все еще можно изменить, используя первое и второе.
Пара называется value_type в теме неупорядоченной карты.
Доступ к элементу unordered_map
mapped_type & operator [] (key_type && k)
Возвращает значение для соответствующего ключа. Пример:
Результат: «зеленый». Таким же образом можно присвоить значения — см. Выше.
unordered_map Емкость
bool empty () const noexcept
Возвращает 1 для истины, если на карте нет пары, и 0 для false, если на ней есть пары. Пример:
unordered_map < const char *, const char *> umap ;
cout << umap. empty ( ) << ‘ \n ‘ ;
Возвращение итераторов и класса неупорядоченной карты
Итератор похож на указатель, но имеет больше функций, чем указатель.
begin () noexcept
Возвращает итератор, указывающий на первую пару объекта карты, как в следующем сегменте кода:
unordered_map < const char *, const char *> umap ;
umap [ «banana» ] = «yellow» ; umap [ «grape» ] = «green» ; umap [ «fig» ] = «purple» ;
unordered_map < const char *, const char *>:: iterator iter = umap. begin ( ) ;
pair < const char *, const char *> pr = * iter ;
cout << pr. first << «, « << pr. second << ‘ \n ‘ ;
На выходе получается: инжир, фиолетовый. Карта неупорядочена.
begin () const noexcept;
Возвращает итератор, указывающий на первый элемент коллекции объектов карты. Когда конструкции объекта предшествует const, выражение «begin () const» выполняется вместо «begin ()». При этом условии нельзя изменить элементы объекта. Например, он используется в следующем коде.
На выходе получается: инжир, фиолетовый. Карта неупорядочена. Обратите внимание, что на этот раз для получения возвращенного итератора был использован const_iterator вместо простого итератора.
end() noexcept
Возвращает итератор, который указывает сразу за последним элементом объекта карты.
end() const noexcept
Возвращает итератор, который указывает сразу за последним элементом объекта карты. Когда построению объекта карты предшествует const, выражение «end () const» выполняется вместо «end ()».
unordered_map Операции
поиск итератора (const key_type & k)
Ищет пару данного ключа на карте. Если он найден, он возвращает итератор. Если не найден, он возвращает итератор, указывающий на конец карты, которая не является парой. В следующем коде показано, как использовать эту функцию-член:
const_iterator find (const key_type & k) const;
Эта версия функции вызывается, если создание неупорядоченной карты начинается с const, что делает все элементы карты доступными только для чтения.
unordered_map Модификаторы
pair <iterator, bool> insert (value_type && obj)
Неупорядоченная карта означает, что пары не расположены в каком-либо порядке. Итак, программа вставляет пару в любое удобное для нее место. Функция возвращает пару <iterator, bool>. Если вставка прошла успешно, bool будет иметь значение 1 для истины, в противном случае — 0 для false. Если вставка прошла успешно, итератор укажет на вновь вставленный элемент. Следующий код иллюстрирует использование:
Результат: 5. Можно вставить более одной пары.
size_type erase(const key_type& k)
Эта функция стирает пару из unordered_map. Следующий фрагмент кода иллюстрирует:
Результатом будет 2.
void swap (unordered_map &)
Две неупорядоченные карты можно поменять местами, как показано в этом сегменте кода:
unordered_map < const char *, const char *> umap1 = ,
, , > ;unordered_map < const char *, const char *> umap2 = , > ;
umap1. swap ( umap2 ) ;
unordered_map < const char *, const char *>:: iterator iter1 = umap1. begin ( ) ;
pair < const char *, const char *> pr1 = * iter1 ;
unordered_map < const char *, const char *>:: iterator iter2 = umap2. begin ( ) ;
pair < const char *, const char *> pr2 = * iter2 ;cout << «First key and size of umap1: « << pr1. first << «, « << umap1. size ( ) << ‘ \n ‘ ;
cout << «First key and size of umap2 « << pr2. first << «, « << umap2. size ( ) << ‘ \n ‘ ;
unordered_map < const char *, const char *> umap1 = ,
, , > ;
unordered_map < const char *, const char *> umap2 = , > ;umap1. swap ( umap2 ) ;
unordered_map < const char *, const char *>:: iterator iter1 = umap1. begin ( ) ;
pair < const char *, const char *> pr1 = * iter1 ;
unordered_map < const char *, const char *>:: iterator iter2 = umap2. begin ( ) ;
pair < const char *, const char *> pr2 = * iter2 ;cout << «First key and size of umap1: « << pr1. first << «, « << umap1. size ( ) << ‘ \n ‘ ;
cout << «First key and size of umap2 « << pr2. first << «, « << umap2. size ( ) << ‘ \n ‘ ;
Первый ключ и размер umap1: lime, 2
Первый ключ и размер клубники umap2, 4
Карта неупорядочена. Обратите внимание, что длина карты при необходимости увеличивается. Типы данных должны быть одинаковыми.
Класс и его экземпляры
Значение относится к типу данных, как созданный объект относится к классу. Построение неупорядоченной карты также может принимать класс как тип данных. Следующая программа иллюстрирует это:
#include <iostream>
#include <unordered_map>
using namespace std ;class TheCla
public :
int num ;
static char ch ;void func ( char cha , const char * str )
cout << «There are « << num << » books worth « << cha << str << » in the store.» << ‘ \n ‘ ;
>
static void fun ( char ch )
if ( ch == ‘a’ )
cout << «Official static member function» << ‘ \n ‘ ;
>
> ;int main ( )
TheCla obj1 ; TheCla obj2 ; TheCla obj3 ; TheCla obj4 ; TheCla obj5 ;unordered_map < const char *, TheCla > umap ;
umap = , , , , > ;cout << umap. size ( ) << ‘ \n ‘ ;
return ;
>
Определение класса имеет два открытых члена данных и две публичные функции члена. В функции main () создаются экземпляры различных объектов класса. Затем создается неупорядоченная карта, где каждая пара состоит из имени фрукта и объекта из класса. Отображается размер карты. Программа компилируется без предупреждений или сообщений об ошибках.
Применение карты
Массив связывает индекс со значением. Пары ключ / значение существуют во многих жизненных ситуациях, которые можно запрограммировать. Пара ключ / значение фрукт / цвет — лишь один из примеров. Другой пример — имена людей и их возраст. В этом случае пара будет иметь тип pair . Это также может быть пара <строка, число с плавающей запятой>. В последнем случае будет использоваться директива предварительной обработки. Пара ключ / значение по-прежнему может быть именами супружеских пар. В странах, где существует многоженство, у одного мужчины будут разные жены.
Формирование карты
Карта — это не двухмерный массив с двумя столбцами. Карта работает с хеш-функцией. Ключ кодируется хеш-функцией в целое число массива. Именно этот массив содержит значения. Итак, на самом деле существует один массив со значениями, и ключи отображаются на индексы массива, и поэтому между ключами и значениями устанавливаются соответствия. Хеширование — обширная тема, которая не рассматривается в этой статье.
Заключение
Карта, также известная как ассоциативный массив, представляет собой список элементов, где каждый элемент представляет собой пару ключ / значение. Итак, каждый ключ соответствует значению. В C ++ карта реализована как структура данных с функциями-членами и операторами. Упорядоченная карта — это карта, в которой пары элементов упорядочены по ключам. Неупорядоченная карта — это карта, на которой нет порядка.
Технически хеш состоит из пары элементов <type1, type2>. Фактически, пара представляет собой целую структуру данных со своими функциями-членами и операторами. Два параметра шаблона для пары — это те же два параметра шаблона для unordered_map.
Initializer_list для карты — это литерал массива литералов. Каждый внутренний литерал состоит из двух объектов, пары ключ / значение.
Функции-члены и операторы для unordered_map можно разделить на следующие категории: создание / копирование unordered_map, емкость unordered_map, итератор unordered_map, операции unordered_map и модификаторы unordered_map.
Неупорядоченная карта используется, когда ключ должен быть сопоставлен со значением.