По какому принципу образуется порядок элементов в unordered_map?
Само название структуры подразумевает, что элементы в ней не отсортированы, но если перезапускать все время программу и выводить циклом элементы, то они всегда будут в одном порядке. Например вот код из этой книги
struct coord < int x; int y; >; bool operator==(const coord &l, const coord &r) < return l.x == r.x && l.y == r.y; >namespace std < template <>struct hash < using argument_type = coord; using result_type = size_t; result_type operator()(const argument_type &c) const < return static_cast(c.x) + static_cast(c.y); > >; > int main() < std::unordered_mapm , 1>, , 2>, , 3>>; for (const auto & [key, value] : m) < std::cout "; > std::cout
Хэш формируется из сложения x и y , поэтому я думал, что по итоговому хэшу и будет выстроен порядок, но оказалось, что это так не работает. Порядок вывода всегда такой:
Как это работает?
Отслеживать
задан 11 июл 2021 в 16:53
195 9 9 бронзовых знаков
Это не сортировка, но порядок связан с хеш-значением. Причем опять же — это не значит, что элементы отсортированы по хешу.
11 июл 2021 в 16:56
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Для того, что бы ответить на вышеуказанный вопрос, для начала нужно понять, а как собственно устроен unordered_map изнутри. Есть два способа реализации, но самый простой и легкий из них — метод цепочек. Вроде он и применяется в стандартной библиотеке.
Сами данные хранятся в векторе списков. То есть так
class my_umap < std::vector>> m_data; >; когда нужно вставить элемент, то от индекса рассчитывается хеш (в нашем случае функция хеша должна уметь преобразовывать тип ключа в некое число в диапазоне 0..m_data.size()-1 . Обычно, хеш функция просто возвращает обычный int , а потом используется деление по модулю с помощью % . По полученному числу находится элемент вектора, в который в список и добавляется необходимый элемент (да, предварительно, проверяется, а нет ли такого элемента ещё).
Функция итерации по мапе обычно делается по простому — проходимся по всем элементам массива (вектора) и выводим элементы списка (опять же, в естественном порядке).
Теперь стает понятно, что при выводе элементов порядок будет определятся хеш функцией и тем, как элементы были вставлены в пределах одного и того же значения хеш функции.
Хеш функции обычно такие, что одному и тому же значению входного значения соответствует одно и тоже выходное значение (иначе это все работать не будет). Но с другой стороны, хеш функция старается максимально равномерно «размазать» значения хеша. Поэтому, если два значения (например, два int ) упорядочены по возрастанию, то значения хеш функции (идеальной конечно) будет упорядочены с вероятностью 50 на 50 (да, они могут совпасть, поэтому, наверно на самом деле это будет 49-49-2 или что то другое, похожее).
Чем же определяется хеш? его может явно задать программист, а может использоваться реализация от компилятора. Важно то, что с большущей вероятностью (если код не менялся), она не поменяется, а значит, значения хеша, которые определяют элемент вектора, будут те же.
Рекомендую попробовать написать свою реализацию unordered_map (того, что я написал выше уже достаточно для этого) и все вопросы пропадут сами собой.
Некоторые языки (например, golang) любят рандомизировать немного хеш функцию от запуска к запуску (для мнимой безопасности), тем самым доставляя кучу приятных впечатлений для молодых программистов.
Есть ещё одна реализация unordered_map — открытая адресация, но он немного сложнее, как по мне в реализции.
Вглубь std::unordered_map: магические числа
Все любители кодокопания заканчивают либо хорошо, либо плохо. Мне повезло. Поэтому я решила написать свою первую статью на Хабре.
Как всё начиналось
Мой друг игрался со вставкой в unordered_map и заметил странную закономерность в изменении параметра bucket_count с ростом числа элементов в таблице.
Unordered map в C++ представляет собой хэш-таблицу. Хэш-таблица даёт околоконстантное время операций за счёт того, что каждый элемент хранится по своему уникальному индексу, вычисляемому через хэш-функцию. При вычислении индекса значение хэш-функции (коротко — хэш) масштабируется на размер таблицы, поэтому он не должен меняться при выполнении операций. Совпадение индексов называется коллизией. Есть несколько стратегий обработки коллизий. В std::unordered_map используется bucket hashing.
Заключается она в том, что элементы с одинаковым хэшем кладутся в соответствующий этому хэшу сегмент (bucket). При возрастании числа коллизий скорость операций с таблицей падает, поэтому необходимо производить рехэширование (rehashing) — увеличивать число сегментов и пересчитывать все хэши элементов, соответственно перевыделять память для таблицы и вставлять их заново. Это дорогостоящая по времени и памяти операция, поэтому приходится искать компромисс между числом коллизий и частотой рехэширования.
Эксперимент показал, что рехэширование происходит при вставке соответственно 14го, 30го, 60го, 128го, 258го, 542го, 1110го, 2358го и так далее. Это дал следующий код:
#include #include int main () < std::unordered_map umap; // заполняем таблицу 2000 элементами - парами чисел for (int i = 0; i < 2000; i++) < // выводим число элементов и число сегментов на каждой итерации std::cout ); > > Получается, размеры таблицы образуют последовательность 13, 29, 59, 127, 257, 541, 1109, 2357, . Но откуда берутся эти числа?
(Здесь сразу стоит оговориться, что кто знает, тому очевидно. Интерес представляет внутренняя структура того, как это реализовано.)
Начинаем копать
Первая часть изысканий делается через встроенную в IDE возможность перехода к определениям функций. insert нам даёт:
Отлично. Мы обнаружили, что unordered_map ссылается на _M_h. Следующие пара шагов нам дают:
Это шаблон базового типа unordered_map. Там есть параметр, кончающийся на rehash_policy. Звучит как то, что нас интересует! Видно, что параметр определён в std::_detail. Объявим
std::__detail::_Prime_rehash_policy p;Перейдём к определению (используя «Go to definition»). Оно в файле под именем hashtable_policy.h. Лишний раз подтверждает связь хэш-таблицы и unordered_map.
Теперь мы знаем, какие функции дают наши «магические числа». К сожалению, определений в этом файле не нашлось.
Долгожданная реализация
Гугл выдаёт следующее: хэдер с аналогичным названием, но из TR1 (проект-расширение C++ между C++03 и C++11, ставший частью последнего): https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.2/hashtable__policy_8h-source.html
Рассмотрим функцию need_rehash, которая определяет новое количество сегментов (а закон его расчёта мы и ищём):
Наш случай — когда функция возвращает true (произойдёт rehashing). Параметр _M_growth_factor, он же _S_growth_factor в новой версии, по дефолту равен 2 (находится поиском по файлу), т.е. размер предварительно удваивается. _M_max_load_factor в дефолтном конструкторе равен 1. Шаблонный класс unordered_map использует именно дефолтные параметры, проверяется это эмпирически с помощью дебаггера.
Двоичный поиск по некоторому массиву _Primes<>::__primes нам даёт первое простое, большее удвоенного размера массива + числа вставленных элементов (1), и устанавливает в него параметр _M_next_resize, определяющий новое число сегментов.
Для первых 6 членов ряда всё ок: (13+1)*2 = 28 -> 29, аналогично 59 и 127. Но (257+1)*2+1 = 517, ближайшее простое — 521, а у нас — 541. Аналогично 1109 и 2357 не соответствуют расчётам.
На этом моменте я конкретно задумалась, но к счастью, моё внимание привлёк огромный массив чисел в начале файла. Это и есть тот самый _Primes<>::__primes:
Согласно этому массиву, всё работает верно (это легко проверить). Ура. Мы нашли разгадку.
Заключение
Мы получили, что искомая последовательность формируется по принципу «ближайшее простое, большее 2(n+1), где n — предыдущий член последовательности». С оговоркой на то, что простые числа берутся из некоторого заданного массива. Почему он именно такой — неизвестно. Предположу, что часть простых пропущена из соображений памяти.
Также, невыясненным остался вопрос, почему при вставке одного элемента число сегментов возрастает сразу до 13. Может быть, вы знаете?
Жду замечаний и предложений в комментариях 🙂
P.S. Судя по тому, что новая библиотека работает как код из tr1, tr1 действительно был внесён в новый стандарт.
Как работает unordered map
awoo → Educational Codeforces Round 165 [рейтинговый для Div. 2]
sdyakonov → Make proofs
rui_er → Codeforces Round 942 (Div. 1, Div. 2)
atcoder_official → AtCoder Beginner Contest 351 Announcement
violentdoc → Who is rainboy?
vovuh → Разбор Codeforces Round #640 (Div. 4)
ooaa → Codeforces Round #922 (Div. 2) Разбор
akzytr → Pleasant pairs -> O(n log n)
ICPCNews → The 2023 ICPC World Finals Luxor
jdurie → Codeforces Round #941 (Div. 1, Div. 2) Editorial
D0OMoP → Hidden Edge cases
Termodinamico → We say thank you to MikeMirzayanov
BluoCaroot → problem with testlib.h readDouble
Kolyanchick → До скорых встреч
FedeNQ → Teams going to ICPC WF 2022 (Egypt 2023) — WIP List
FedeNQ → Teams going to ICPC WF 2023 (Egypt 2023, 2nd final) — WIP List
EnDeRBeaT → [Tool] Graph Debugger
h ehezhou → 2024-The 6th Turing Cup Tournament
PolymathFaisal → How to use Codeforces as a new Bie?
Le_Gusto → Specialist rank celebration!
Cauchico → Helvetic Coding Contest 2024 — Online Mirror
qmk → [Explanation] dsu on trees (small to large)
Deniz-cpp → Я активен на Codeforces уже 100 дней подряд!
ppavic → Croatian Olympiad in Informatics (COI) 2024
SuperJ6 → Ad-Hoc is Not Real
Блог пользователя tamir
Автор tamir, 10 лет назад ,
Привет! Объясните структуры данных unordered_map,unordered set(с примерами) и какую роль данные структуры данных играют в олимпиадном программировании. Я читал про них в сети, но большинство материала на английском языке. Я понял, что unordered_map не сортирует данные по ключу(как map) и доступ осуществляется быстрее чем в map из-за непонятных buckets (хэширования ключа?). С unorder_set тоже самое насчет доступа и неотсортированности. Спасибо за внимание!
unordered_map, unordered_set, структруры данных
Комментарии (6)
10 лет назад , # |
Я тоже такое видел, но забыл спросить
10 лет назад , # |
10 лет назад , # ^ |
Здесь я был уже — не очень понятно(
10 лет назад , # |
Это хеш-таблицы. Ключи по умолчанию хешируются функтором std::hash . Можно притворяться, что каждый доступ к элементу по ключу стоит столько же, сколько один вызов хеш-функции плюс O(1). Есть unordered_map , unordered_multimap , unordered_set и unordered_multiset , и разница между ними такая же, как между map , multimap , set и multiset . Разница же между первым набором и вторым набором, как уже замечено, в том, что это — хеш-таблицы с операциями за практически константное время и отсутствием сортировки, а то — сбалансированные бинарные деревья поиска (на практике — конкретно красно-чёрные деревья) с операциями за гарантированное логарифмическое время и автоматической сортировкой.
10 лет назад , # ^ |
А можете объяснить как работает std::hash
10 лет назад , # ^ |
← Rev. 3 → 
+3 
hash, в случае строк я предполагаю, использует полиномиальное хеширование. Коллизии встречаются довольно редко, но даже если и случаются, обрабатываются правильно и на асимптотику почти никак не влияют. При желании почитай в википедии (желательно английской) про хеш-таблицы, там все хорошо описано. В олимпиадных задачах, на самом деле хеши применяются редко (как правило только в задачах на строки) и обычно пишутся самостоятельно. Например, std::hash (если я ничего не путаю) не поддерживает хеши на префиксах, и соответственно на подотрезках. Так что, я бы не стал на std::hash полагаться UPD. А еще и там много коллизий, как оказалось. Я был неправ тогда
Класс unordered_map
Шаблон класса описывает объект, который управляет последовательностью элементов типа std::pair с переменной длиной. Последовательность слабо упорядочена хэш-функцией, которая разделяет последовательность в упорядоченный набор подпоследовательностей, называемых блоками. В каждом контейнере функция сравнения определяет, имеет ли любая пара элементов эквивалентное упорядочение. Каждый элемент содержит два объекта: ключ и значение сортировки. Последовательность представлена таким образом, чтобы разрешить поиск, вставку и удаление произвольного элемента с операциями, которые могут быть не зависят от количества элементов последовательности (постоянное время), по крайней мере если все контейнеры имеют примерно одинаковую длину. В худшем случае, когда все элементы находятся в одном блоке, количество операций пропорционально количеству элементов в последовательности (линейное время). Кроме того, при вставке элемента не выполняется итератор, а удаление элемента делает недопустимым только те итераторы, которые указывают на удаленный элемент.
Синтаксис
template , class Pred = std::equal_to, class Alloc = std::allocator>> class unordered_map; Параметры
Ty
Сопоставленный тип.
Hash
Тип объекта хэш-функции.
Pred
Тип объекта функции сравнения на предмет равенства.
Alloc
Класс распределителя.
Участники
| Определение типа | Description |
|---|---|
| allocator_type | Тип распределителя для управления хранилищем. |
| const_iterator | Тип постоянного итератора для управляемой последовательности. |
| const_local_iterator | Тип постоянного итератора блока для управляемой последовательности. |
| const_pointer | Тип постоянного указателя на элемент. |
| const_reference | Тип постоянной ссылки на элемент. |
| difference_type | Тип расстояния со знаком между двумя элементами. |
| hasher | Тип хэш-функции. |
| iterator | Тип итератора для управляемой последовательности. |
| key_equal | Тип функции сравнения. |
| key_type | Тип ключа упорядочения. |
| local_iterator | Тип итератора блока для управляемой последовательности. |
| mapped_type | Тип сопоставленного значения, связанного с каждым ключом. |
| pointer | Тип указателя на элемент. |
| reference | Тип ссылки на элемент. |
| size_type | Тип беззнакового расстояния между двумя элементами. |
| value_type | Тип элемента. |
| Функция-член | Description |
|---|---|
| at | Поиск элемента с заданным ключом. |
| begin | Задает начало управляемой последовательности. |
| bucket | Получает номер блока для значения ключа. |
| bucket_count | Получает количество блоков. |
| bucket_size | Получает размер блока. |
| cbegin | Задает начало управляемой последовательности. |
| cend | Задает конец управляемой последовательности. |
| clear | Удаляет все элементы. |
| count | Определяет количество элементов, соответствующих заданному ключу. |
| contains C++20 | Проверьте, есть ли элемент с указанным ключом в элементе unordered_map . |
| emplace | Добавляет элемент, созданный на месте. |
| emplace_hint | Добавляет элемент, созданный на месте, с подсказкой. |
| empty | Проверяет отсутствие элементов. |
| end | Задает конец управляемой последовательности. |
| equal_range | Находит диапазон, соответствующий указанному ключу. |
| erase | Удаляет элементы в указанных позициях. |
| find | Определяет элемент, соответствующий указанному ключу. |
| get_allocator | Возвращает сохраненный объект распределителя. |
| hash_function | Получает сохраненный объект хэш-функции. |
| insert | Добавляет элементы. |
| key_eq | Получает сохраненный объект функции сравнения. |
| load_factor | Подсчитывает среднее число элементов в блоке. |
| max_bucket_count | Получает максимальное количество блоков. |
| max_load_factor | Возвращает или задает максимальное количество элементов в блоке. |
| max_size | Возвращает максимальный размер управляемой последовательности. |
| rehash | Повторно создает хэш-таблицу. |
| size | Подсчитывает количество элементов. |
| swap | Меняет местами содержимое двух контейнеров. |
| unordered_map | Создает объект контейнера. |
| Operator | Description |
|---|---|
| unordered_map::operator[] | Находит или вставляет элемент с указанным ключом. |
| unordered_map::operator= | Копирует хэш-таблицу. |
Замечания
Объект упорядочивает последовательность, которая управляется путем вызова двух хранимых объектов, объекта функции сравнения типа unordered_map::key_equal и объекта хэш-функции типа unordered_map::hasher . Вы обращаетесь к первому сохраненного объекта, вызывая функцию-член unordered_map::key_eq () ; и обращаетесь ко второму хранящейся объекту, вызывая функцию-член unordered_map::hash_function () . В частности, для всех значений X и Y типа Key вызов key_eq()(X, Y) возвращает значение true, только если два значения аргументов имеют соответствующий порядок; вызов hash_function()(keyval) создает распределение значений типа size_t . В отличие от класса шаблона unordered_multimap класса, объект типа unordered_map гарантирует, что key_eq()(X, Y) всегда имеет значение false для всех двух элементов управляемой последовательности. (Ключи уникальны).
Объект также хранит максимальный коэффициент нагрузки, который определяет максимальное желаемое среднее количество элементов в блоке. Если вставка элемента приводит unordered_map::load_factor () к превышению максимального коэффициента нагрузки, контейнер увеличивает количество контейнеров и перестраивает хэш-таблицу по мере необходимости.
Фактический порядок элементов в управляемой последовательности зависит от хэш-функции, функции сравнения, порядка вставки, максимального коэффициента нагрузки и текущего числа блоков. Вы не можете в целом предсказать порядок элементов в управляемой последовательности. Однако всегда можно сохранять уверенность, что любое подмножество элементов, имеющих соответствующий порядок, будет расположено по соседству в управляемой последовательности.
Объект выделяет и освобождает хранилище для последовательности, который он управляет с помощью сохраненного объекта распределителя типа unordered_map::allocator_type . Такой объект распределителя должен иметь тот же внешний интерфейс, что и объект типа allocator . Сохраненный объект распределителя не копируется при назначении объекта контейнера.
Требования
Заголовок.
Пространство имен: std
unordered_map::allocator_type
Тип распределителя для управления хранилищем.
typedef Alloc allocator_type; Замечания
Этот тип является синонимом для параметра шаблона Alloc .
Пример
// std__unordered_map__unordered_map_allocator_type.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; typedef std::allocator > Myalloc; int main()
al == std::allocator() is true unordered_map::at
Находит элемент в unordered_map с указанным значением ключа.
Ty& at(const Key& key); const Ty& at(const Key& key) const; Параметры
key
Значение ключа, которое необходимо найти.
Возвращаемое значение
Ссылка на значение данных найденного элемента.
Замечания
Если значение ключа аргумента не найдено, функция создает объект класса out_of_range .
Пример
// unordered_map_at.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // find and show elements std::cout
unordered_map::begin
Задает начало управляемой последовательности или сегмента.
iterator begin(); const_iterator begin() const; local_iterator begin(size_type nbucket); const_local_iterator begin(size_type nbucket) const; Параметры
nbucket
Номер сегмента.
Замечания
Первые две функции-члены возвращают прямой итератор, указывающий на первый элемент последовательности (или на место сразу за концом пустой последовательности). Последние две функции-члены возвращают прямой итератор, указывающий на первый элемент сегмента nbucket (или на место сразу за концом пустого сегмента).
Пример
// std__unordered_map__unordered_map_begin.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second first second first second first second
[c, 3] [b, 2] [a, 1] [c, 3] [b, 2] [a, 1] unordered_map::bucket
Получает номер блока для значения ключа.
size_type bucket(const Key& keyval) const; Параметры
keyval
Значение ключа для сопоставления.
Замечания
Функция-член возвращает номер контейнера, который в настоящий момент соответствует значению ключа keyval .
Пример
// std__unordered_map__unordered_map_bucket.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] bucket('a') == 7 bucket_size(7) == 1
unordered_map::bucket_count
Получает количество блоков.
size_type bucket_count() const;
Замечания
Функция-член возвращает текущее число блоков.
Пример
// std__unordered_map__unordered_map_bucket_count.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3][b, 2][a, 1] bucket_count() == 8 load_factor() == 0.375 max_bucket_count() == 8 max_load_factor() == 4 bucket_count() == 8 load_factor() == 0.375 max_bucket_count() == 8 max_load_factor() == 0.1 bucket_count() == 128 load_factor() == 0.0234375 max_bucket_count() == 128 max_load_factor() == 0.1
unordered_map::bucket_size
Получает размер сегмента.
size_type bucket_size(size_type nbucket) const;
Параметры
nbucket
Номер сегмента.
Замечания
Функции-члены возвращают размер номера nbucket контейнера.
Пример
// std__unordered_map__unordered_map_bucket_size.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] bucket('a') == 7 bucket_size(7) == 1
unordered_map::cbegin
Возвращает итератор const , направленный на первый элемент в диапазоне.
const_iterator cbegin() const;
Возвращаемое значение
Итератор прямого доступа const , который указывает на первый элемент диапазона или расположение прямо за концом пустого диапазона ( cbegin() == cend() для пустого диапазона).
Замечания
При возвращаемом значении cbegin элементы в диапазоне не могут быть изменены.
Эту функцию-член можно использовать вместо функции-члена begin() , чтобы гарантировать, что возвращаемое значение будет const_iterator . Как правило, он используется с ключевое слово вычета auto типов, как показано в следующем примере. В примере Container следует рассматривать как изменяемый (не- const ) контейнер любого вида, который поддерживает begin() и cbegin() .
auto i1 = Container.begin(); // i1 is Container::iterator auto i2 = Container.cbegin(); // i2 is Container::const_iterator
unordered_map::cend
Возвращает итератор const , который обращается к месту, следующему сразу за последним элементом в диапазоне.
const_iterator cend() const;
Возвращаемое значение
Итератор const прямого доступа, который указывает на позицию сразу за концом диапазона.
Замечания
cend используется для проверки того, прошел ли итератор конец диапазона.
Эту функцию-член можно использовать вместо функции-члена end() , чтобы гарантировать, что возвращаемое значение будет const_iterator . Как правило, он используется с ключевое слово вычета auto типов, как показано в следующем примере. В примере Container следует рассматривать как изменяемый (не- const ) контейнер любого вида, который поддерживает end() и cend() .
auto i1 = Container.end(); // i1 is Container::iterator auto i2 = Container.cend(); // i2 is Container::const_iterator
Возвращаемое cend значение не должно быть разоменовывано.
unordered_map::clear
Удаляет все элементы.
void clear();
Замечания
Вызовы unordered_map::erase(unordered_map::begin(), unordered_map::end()) функции-члены, см unordered_map::erase unordered_map::begin . и unordered_map::end .
Пример
// std__unordered_map__unordered_map_clear.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second << "]"; std::cout << std::endl; // clear the container and reinspect c1.clear(); std::cout << "size == " << c1.size() << std::endl; std::cout << "empty() == " << std::boolalpha << c1.empty() << std::endl; std::cout << std::endl; c1.insert(Mymap::value_type('d', 4)); c1.insert(Mymap::value_type('e', 5)); // display contents " [e 5] [d 4]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] size == 0 empty() == true [e, 5] [d, 4] size == 2 empty() == false
unordered_map::const_iterator
Тип постоянного итератора для управляемой последовательности.
typedef T1 const_iterator;
Замечания
Тип описывает объект, который можно использовать в качестве постоянного прямого итератора для управляемой последовательности. Здесь описано как синоним определенного реализацией типа T1 .
Пример
// std__unordered_map__unordered_map_const_iterator.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1]
unordered_map::const_local_iterator
Тип постоянного итератора блока для управляемой последовательности.
typedef T5 const_local_iterator;
Замечания
Этот тип описывает объект, который можно использовать в качестве постоянного прямого итератора для блока. Здесь описано как синоним определенного реализацией типа T5 .
Пример
// std__unordered_map__unordered_map_const_local_iterator.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second first second
[c, 3] [b, 2] [a, 1] [a, 1]
unordered_map::const_pointer
Тип постоянного указателя на элемент.
typedef Alloc::const_pointer const_pointer;
Замечания
Этот тип описывает объект, который можно использовать в качестве постоянного указателя на элемент управляемой последовательности.
Пример
// std__unordered_map__unordered_map_const_pointer.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::iterator it = c1.begin(); it != c1.end(); ++it) < Mymap::const_pointer p = &*it; std::cout first second std::cout
[c, 3] [b, 2] [a, 1]
unordered_map::const_reference
Тип постоянной ссылки на элемент.
typedef Alloc::const_reference const_reference;
Замечания
Тип описывает объект, который можно использовать в качестве постоянной ссылки на элемент управляемой последовательности.
Пример
// std__unordered_map__unordered_map_const_reference.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::iterator it = c1.begin(); it != c1.end(); ++it) < Mymap::const_reference ref = *it; std::cout std::cout
[c, 3] [b, 2] [a, 1]
unordered_map::contains
Проверяет, есть ли элемент в unordered_map указанном ключе. Представлено в C++20.
bool contains(const Key& key) const; bool contains(const K& key) const;
Параметры
key
Ключевое значение элемента для поиска.
Возвращаемое значение
true Значение , если элемент найден в контейнере; false Иначе.
Замечания
contains() новый в C++20. Чтобы использовать его, укажите или более поздний /std:c++20 параметр компилятора.
template bool contains(const K& key) const только принимает участие в разрешении перегрузки, если key_compare это прозрачно.
Пример
// Requires /std:c++20 or /std:c++latest #include #include int main() < std::unordered_maptheUnorderedMap = , >; std::cout
true false
unordered_map::count
Определяет количество элементов, соответствующих заданному ключу.
size_type count(const Key& keyval) const;
Параметры
keyval
Искомое значение ключа.
Замечания
Функция-член возвращает количество элементов в диапазоне с разделителями unordered_map::equal_range(keyval) .
Пример
// std__unordered_map__unordered_map_count.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] count('A') == 0 count('b') == 1 count('C') == 0
unordered_map::difference_type
Тип расстояния со знаком между двумя элементами.
typedef T3 difference_type;
Замечания
Тип целого числа со знаком описывает объект, который может представлять разницу между адресами любых двух элементов в управляемой последовательности. Здесь описано как синоним определенного реализацией типа T3 .
Пример
// std__unordered_map__unordered_map_difference_type.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] end()-begin() == 3 begin()-end() == -3
unordered_map::emplace
Вставляет созданный элемент на место (операции копирования или перемещения не выполняются) в объекте unordered_map.
template pair emplace( Args&&. args);
Параметры
args
Аргументы, пересылаемые для создания элемента, вставляемого в unordered_map элемент, если он еще не содержит элемент, значение которого эквивалентно упорядочено.
Возвращаемое значение
Объект pair , компонент bool которого возвращает значение true, если была осуществлена вставка, и false, если unordered_map уже содержал элемент, ключ которого имел эквивалентное значение порядка, и компонент итератора которого возвращает адрес нового вставленного элемента или адрес местонахождения элемента, если он уже существовал.
Для доступа к компоненту итератора пары pr , возвращенной этой функцией-членом, используйте pr.first и разыменуйте ее с помощью *(pr.first) . Для доступа к компоненту bool пары pr , возвращенной этой функцией-членом, используйте pr.second .
Замечания
Эта функция не делает недействительными никакие итераторы или ссылки.
Во время вставки, если исключение создается, но не происходит в хэш-функции контейнера, контейнер не изменяется. Если исключение вызывается в хэш-функции, результат не определен.
Пример кода см. в разделе map::emplace .
unordered_map::emplace_hint
Вставляет созданный элемент на место (операции копирования или перемещения не выполняются) с указанием о размещении.
template iterator emplace_hint(const_iterator where, Args&&. args);
Параметры
args
Аргументы, передаваемые для создания элемента, который будет вставлен в объект unordered_map, если объект unordered_map не содержит этого элемента или, в более общем случае, если этот объект еще не содержит элемента, ключ которого упорядочен аналогичным образом.
where
Подсказка о месте начала поиска правильной точки вставки.
Возвращаемое значение
Итератор, указывающий на вновь вставленный элемент.
Если не удалось вставить элемент, так как он уже существует, возвращается итератор на существующий элемент.
Замечания
Эта функция не делает ссылки недействительными.
Во время вставки, если исключение создается, но не происходит в хэш-функции контейнера, контейнер не изменяется. Если исключение вызывается в хэш-функции, результат не определен.
Элемент value_type является парой, поэтому значение элемента будет упорядоченной парой с первым компонентом, равным значению ключа, и второй компонент равен значению данных элемента.
Пример кода см. в разделе map::emplace_hint .
unordered_map::empty
Проверяет отсутствие элементов.
bool empty() const;
Замечания
Эта функция-член возвращает значение true для пустой управляемой последовательности.
Пример
// std__unordered_map__unordered_map_empty.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second << "]"; std::cout << std::endl; // clear the container and reinspect c1.clear(); std::cout << "size == " << c1.size() << std::endl; std::cout << "empty() == " << std::boolalpha << c1.empty() << std::endl; std::cout << std::endl; c1.insert(Mymap::value_type('d', 4)); c1.insert(Mymap::value_type('e', 5)); // display contents " [e 5] [d 4]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] size == 0 empty() == true [e, 5] [d, 4] size == 2 empty() == false
unordered_map::end
Задает конец управляемой последовательности.
iterator end(); const_iterator end() const; local_iterator end(size_type nbucket); const_local_iterator end(size_type nbucket) const;
Параметры
nbucket
Номер сегмента.
Замечания
Первые две функции-члены возвращают прямой итератор, указывающий на место сразу за концом последовательности. Последние две функции-члены возвращают прямой итератор, указывающий на место сразу за концом сегмента nbucket .
unordered_map::equal_range
Находит диапазон, соответствующий указанному ключу.
std::pair equal_range(const Key& keyval); std::pair equal_range(const Key& keyval) const;
Параметры
keyval
Искомое значение ключа.
Замечания
Функция-член возвращает пару итераторов X , таких, что [X.first, X.second) отделяет только те элементы управляемой последовательности, которые имеют эквивалентное упорядочение с keyval . Если таких элементов не существует, оба итератора имеют значение end() .
Пример
// std__unordered_map__unordered_map_equal_range.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second pair1 = c1.equal_range('x'); std::cout first second first second
[c, 3] [b, 2] [a, 1] equal_range('x'): equal_range('b'): [b, 2]
unordered_map::erase
Удаляет элемент или диапазон элементов в объекте unordered_map с заданных позиций или удаляет элементы, соответствующие заданному ключу.
iterator erase(const_iterator Where); iterator erase(const_iterator First, const_iterator Last); size_type erase(const key_type& Key);
Параметры
Where
Положение удаляемого элемента.
First
Положение первого удаляемого элемента.
Last
Позиция после последнего элемента для удаления.
Key
Значение ключа удаляемых элементов.
Возвращаемое значение
Для первых двух функций-членов это двунаправленный итератор, обозначающий первый элемент, остающийся после любых удаленных элементов, или элемент в конце сопоставления, если таких элементов нет.
Для третьей функции-члена возвращает число элементов, которые были удалены из объекта unordered_map.
Замечания
Пример кода см. в разделе map::erase .
unordered_map::find
Определяет элемент, соответствующий указанному ключу.
const_iterator find(const Key& keyval) const;
Параметры
keyval
Искомое значение ключа.
Замечания
Пример
// std__unordered_map__unordered_map_find.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second first second
[c, 3] [b, 2] [a, 1] find('A') == false find('b') == true: [b, 2]
unordered_map::get_allocator
Возвращает сохраненный объект распределителя.
Alloc get_allocator() const;
Замечания
Функция-член возвращает сохраненный объект распределителя.
Пример
// std__unordered_map__unordered_map_get_allocator.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; typedef std::allocator > Myalloc; int main()
al == std::allocator() is true
unordered_map::hash_function
Получает сохраненный объект хэш-функции.
Hash hash_function() const;
Замечания
Функция-член возвращает сохраненный объект хэш-функции.
Пример
// std__unordered_map__unordered_map_hash_function.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main()
hfn('a') == 1630279 hfn('b') == 1647086
unordered_map::hasher
typedef Hash hasher;
Замечания
Этот тип является синонимом для параметра шаблона Hash .
Пример
// std__unordered_map__unordered_map_hasher.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main()
hfn('a') == 1630279 hfn('b') == 1647086
unordered_map::insert
Вставляет элемент или диапазон элементов в unordered_map.
// (1) single element pair insert( const value_type& Val); // (2) single element, perfect forwarded template pair insert( ValTy&& Val); // (3) single element with hint iterator insert( const_iterator Where, const value_type& Val); // (4) single element, perfect forwarded, with hint template iterator insert( const_iterator Where, ValTy&& Val); // (5) range template void insert(InputIterator First, InputIterator Last); // (6) initializer list void insert(initializer_list IList);
Параметры
Val
Значение элемента, вставляемого в unordered_map, если оно уже не содержит элемент, ключ которого эквивалентно упорядочен.
Where
Место начала поиска правильной точки вставки.
ValTy
Параметр шаблона, указывающий тип аргумента, который unordered_map может использовать для создания элемента value_type и идеального перенаправления Val в качестве аргумента.
First
Позиция первого элемента, который следует скопировать.
Last
Позиция непосредственно перед последним элементом, который следует скопировать.
InputIterator
Аргумент функции шаблона, соответствующий требованиям входного итератора , который указывает на элементы типа, который можно использовать для создания value_type объектов.
IList
Объект initializer_list , из которого нужно скопировать элементы.
Возвращаемое значение
Функции-члены с одним элементом (1) и (2) возвращают pair компонент, компонент которого bool является true , если вставка была выполнена, и false если unordered_map элемент уже содержал элемент, ключ которого имел эквивалентное значение в порядке. Компонент итератора пары возвращаемого значения указывает на только что вставленный элемент, если bool компонент имеет true значение, или существующий элемент, если bool компонент является false .
Одноэлементные функции-члены с подсказкой (3) и (4) возвращают итератор, который указывает на позицию, где новый элемент был вставлен, или, если элемент с эквивалентным ключом уже существует, указывает на существующий элемент.
Замечания
Эта функция не делает никакие итераторы, указатели или ссылки недействительными.
Во время вставки только одного элемента, если исключение возникает, но не происходит в хэш-функции контейнера, состояние контейнера не изменяется. Если исключение вызывается в хэш-функции, результат не определен. Если во время вставки нескольких элементов вызывается исключение, контейнер остается в неопределенном, но допустимом состоянии.
Для доступа к компоненту итератора pair pr , возвращаемого одноэлементными функциями-членами, используйте pr.first . Для разыменования итератора в возвращенной паре используйте *pr.first , чтобы получить элемент. Для доступа к компоненту bool используйте pr.second . См. пример кода далее в этой статье.
Контейнер value_type представляет собой типдифакт, который принадлежит контейнеру, а для сопоставления map::value_type — pair . Значение элемента — это упорядоченная пара, в которой первый компонент эквивалентен значению ключа, а второй компонент — значению данных элемента.
Функция-член диапазона (5) вставляет последовательность значений элементов в unordered_map, которая соответствует каждому элементу, адресуемого итератором в диапазоне [First, Last) ; Last поэтому не вставляется. Контейнер функции-члена end() ссылается на позицию сразу после последнего элемента в контейнере. Например, оператор m.insert(v.begin(), v.end()); пытается вставить все элементы v в m . Вставляются только элементы с уникальными значениями в диапазоне. Повторяющиеся значения игнорируются. Чтобы увидеть, какие элементы отклонены, используйте одноэлементные версии insert .
Функция-член списка инициализатора (6) использует initializer_list для копирования элементов в unordered_map.
Для вставки элемента, созданного на месте, то есть операции копирования или перемещения не выполняются, см unordered_map::emplace . и unordered_map::emplace_hint .
Пример кода см. в разделе map::insert .
unordered_map::iterator
Тип итератора для управляемой последовательности.
typedef T0 iterator;
Замечания
Тип описывает объект, который можно использовать в качестве прямого итератора для управляемой последовательности. Здесь описано как синоним определенного реализацией типа T0 .
Пример
// std__unordered_map__unordered_map_iterator.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1]
unordered_map::key_eq
Получает сохраненный объект функции сравнения.
Pred key_eq() const;
Замечания
Функция-член возвращает сохраненный объект функции сравнения.
Пример
// std__unordered_map__unordered_map_key_eq.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main()
cmpfn('a', 'a') == true cmpfn('a', 'b') == false
unordered_map::key_equal
Тип функции сравнения.
typedef Pred key_equal;
Замечания
Этот тип является синонимом для параметра шаблона Pred .
Пример
// std__unordered_map__unordered_map_key_equal.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main()
cmpfn('a', 'a') == true cmpfn('a', 'b') == false
unordered_map::key_type
Тип ключа упорядочения.
typedef Key key_type;
Замечания
Этот тип является синонимом для параметра шаблона Key .
Пример
// std__unordered_map__unordered_map_key_type.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second << "]"; std::cout << std::endl; // add a value and reinspect Mymap::key_type key = 'd'; Mymap::mapped_type mapped = 4; Mymap::value_type val = Mymap::value_type(key, mapped); c1.insert(val); for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] [d, 4] [c, 3] [b, 2] [a, 1]
unordered_map::load_factor
Подсчитывает среднее число элементов в блоке.
float load_factor() const;
Замечания
Функция-член возвращает (float)unordered_map::size() / (float)unordered_map::bucket_count() среднее количество элементов в контейнере, см unordered_map::size . и unordered_map::bucket_count .
Пример
// std__unordered_map__unordered_map_load_factor.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] bucket_count() == 8 load_factor() == 0.375 max_bucket_count() == 8 max_load_factor() == 4 bucket_count() == 8 load_factor() == 0.375 max_bucket_count() == 8 max_load_factor() == 0.1 bucket_count() == 128 load_factor() == 0.0234375 max_bucket_count() == 128 max_load_factor() == 0.1
unordered_map::local_iterator
Тип итератора контейнера.
typedef T4 local_iterator;
Замечания
Этот тип описывает объект, который можно использовать в качестве прямого итератора для контейнера. Здесь описано как синоним определенного реализацией типа T4 .
Пример
// std__unordered_map__unordered_map_local_iterator.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second first second
[c, 3] [b, 2] [a, 1] [a, 1]
unordered_map::mapped_type
Тип сопоставленного значения, связанного с каждым ключом.
typedef Ty mapped_type;
Замечания
Этот тип является синонимом для параметра шаблона Ty .
Пример
// std__unordered_map__unordered_map_mapped_type.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second << "]"; std::cout << std::endl; // add a value and reinspect Mymap::key_type key = 'd'; Mymap::mapped_type mapped = 4; Mymap::value_type val = Mymap::value_type(key, mapped); c1.insert(val); for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] [d, 4] [c, 3] [b, 2] [a, 1]
unordered_map::max_bucket_count
Получает максимальное количество блоков.
size_type max_bucket_count() const;
Замечания
Функция-член возвращает максимальное количество блоков, которое разрешено в настоящее время.
Пример
// std__unordered_map__unordered_map_max_bucket_count.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] bucket_count() == 8 load_factor() == 0.375 max_bucket_count() == 8 max_load_factor() == 4 bucket_count() == 8 load_factor() == 0.375 max_bucket_count() == 8 max_load_factor() == 0.1 bucket_count() == 128 load_factor() == 0.0234375 max_bucket_count() == 128 max_load_factor() == 0.1
unordered_map::max_load_factor
Возвращает или задает максимальное количество элементов в блоке.
float max_load_factor() const; void max_load_factor(float factor);
Параметры
factor
Новый коэффициент максимальной нагрузки.
Замечания
Первая функция-член возвращает сохраненный коэффициент максимальной нагрузки. Вторая функция-член заменяет сохраненный коэффициент максимальной нагрузки factor .
Пример
// std__unordered_map__unordered_map_max_load_factor.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] bucket_count() == 8 load_factor() == 0.375 max_bucket_count() == 8 max_load_factor() == 4 bucket_count() == 8 load_factor() == 0.375 max_bucket_count() == 8 max_load_factor() == 0.1 bucket_count() == 128 load_factor() == 0.0234375 max_bucket_count() == 128 max_load_factor() == 0.1
unordered_map::max_size
Возвращает максимальный размер управляемой последовательности.
size_type max_size() const;
Замечания
Функция-член возвращает длину самой длинной последовательности, которой объект может управлять.
Пример
// std__unordered_map__unordered_map_max_size.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main()
max_size() == 536870911
unordered_map::operator[]
Находит или вставляет элемент с указанным ключом.
Ty& operator[](const Key& keyval); Ty& operator[](Key&& keyval);
Параметры
keyval
Значение ключа, которое необходимо найти или вставить.
Возвращаемое значение
Ссылка на значение данных вставленного элемента.
Замечания
Если значение ключа аргумента не найдено, оно вставляется вместе со значением по умолчанию типа данных.
operator[] можно использовать для вставки элементов в сопоставление m с помощью m[Key] = DataValue; , где DataValue — это значение элемента mapped_type со значением ключа Key .
Функция-член определяет итератор where в качестве возвращаемого unordered_map::insert(unordered_map::value_type(keyval, Ty()) значения. Дополнительные сведения см. в разделах unordered_map::insert и unordered_map::value_type . (Он вставляет элемент с указанным ключом, если такой элемент отсутствует.) Затем он возвращает ссылку (*where).second на .
При использовании operator[] для вставки элементов возвращаемая ссылка не указывает, изменяет ли вставка уже существующий элемент или создает новый. Функции-члены find и insert могут использоваться для определения того, присутствует ли элемент с указанным ключом перед вставкой.
Пример
// std__unordered_map__unordered_map_operator_sub.cpp // compile with: /EHsc #include #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second << "]"; std::cout << std::endl; // try to find and fail std::cout << "c1['A'] == " << c1['A'] << std::endl; // try to find and succeed std::cout << "c1['a'] == " << c1['a'] << std::endl; // redisplay contents for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second c2; std::string str("abc"); std::cout
[c, 3] [b, 2] [a, 1] c1['A'] == 0 c1['a'] == 1 [c, 3] [b, 2] [A, 0] [a, 1] c2[move(str)] == 0 c2["abc"] == 1
unordered_map::operator=
Заменяет элементы этого контейнера unordered_map, используя элементы из другого контейнера unordered_map.
unordered_map& operator=(const unordered_map& right); unordered_map& operator=(unordered_map&& right);
Параметры
right
Контейнер unordered_map, из которого функция оператора назначает содержимое.
Замечания
Первая версия копирует все элементы из right в этот объект unordered_map.
Вторая версия перемещает все элементы из right в этот объект unordered_map.
Все элементы, которые находятся в этом unordered_map перед operator= выполнением, не карта.
Пример
// unordered_map_operator_as.cpp // compile with: /EHsc #include #include int main( ) < using namespace std; unordered_mapv1, v2, v3; unordered_map::iterator iter; v1.insert(pair(1, 10)); cout second second second
unordered_map::pointer
Тип указателя на элемент.
typedef Alloc::pointer pointer;
Замечания
Этот тип описывает объект, который можно использовать в качестве указателя на элемент управляемой последовательности.
Пример
// std__unordered_map__unordered_map_pointer.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::iterator it = c1.begin(); it != c1.end(); ++it) < Mymap::pointer p = &*it; std::cout first second std::cout
[c, 3] [b, 2] [a, 1]
unordered_map::reference
Тип ссылки на элемент.
typedef Alloc::reference reference;
Замечания
Тип описывает объект, который можно использовать в качестве ссылки на элемент управляемой последовательности.
Пример
// std__unordered_map__unordered_map_reference.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::iterator it = c1.begin(); it != c1.end(); ++it) < Mymap::reference ref = *it; std::cout std::cout
[c, 3] [b, 2] [a, 1]
unordered_map::rehash
Повторно создает хэш-таблицу.
void rehash(size_type nbuckets);
Параметры
nbuckets
Требуемое число сегментов.
Замечания
Функция-член устанавливает число сегментов не менее nbuckets и при необходимости перестраивает хэш-таблицу.
Пример
// std__unordered_map__unordered_map_rehash.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] bucket_count() == 8 load_factor() == 0.375 max_load_factor() == 4 bucket_count() == 8 load_factor() == 0.375 max_load_factor() == 0.1 bucket_count() == 128 load_factor() == 0.0234375 max_load_factor() == 0.1
unordered_map::size
Подсчитывает количество элементов.
size_type size() const;
Замечания
Функция-член возвращает длину управляемой последовательности.
Пример
// std__unordered_map__unordered_map_size.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second << "]"; std::cout << std::endl; // clear the container and reinspect c1.clear(); std::cout << "size == " << c1.size() << std::endl; std::cout << "empty() == " << std::boolalpha << c1.empty() << std::endl; std::cout << std::endl; c1.insert(Mymap::value_type('d', 4)); c1.insert(Mymap::value_type('e', 5)); // display contents " [e 5] [d 4]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] size == 0 empty() == true [e, 5] [d, 4] size == 2 empty() == false
unordered_map::size_type
Тип беззнакового расстояния между двумя элементами.
typedef T2 size_type;
Замечания
Целочисленный тип без знака описывает объект, который может представлять длину любой управляемой последовательности. Здесь описано как синоним определенного реализацией типа T2 .
Пример
// std__unordered_map__unordered_map_size_type.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main()
size == 0
unordered_map::swap
Меняет местами содержимое двух контейнеров.
void swap(unordered_map& right);
Параметры
right
Контейнер для замены.
Замечания
Функция-член меняет местами управляемые последовательности между *this и right . Если unordered_map::get_allocator() == right.get_allocator() , см unordered_map::get_allocator ., он делает это в постоянном времени, он создает исключение только в результате копирования сохраненного объекта признаков типа Tr , и он не делает ссылок, указателей или итераторов, которые указывают элементы в двух управляемых последовательностях. В противном случае он выполняет назначения элементов и вызовы конструктора пропорционально количеству элементов в двух управляемых последовательностях.
Пример
// std__unordered_map__unordered_map_swap.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second << "]"; std::cout << std::endl; Mymap c2; c2.insert(Mymap::value_type('d', 4)); c2.insert(Mymap::value_type('e', 5)); c2.insert(Mymap::value_type('f', 6)); c1.swap(c2); // display contents " [f 6] [e 5] [d 4]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second << "]"; std::cout << std::endl; swap(c1, c2); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] [f, 6] [e, 5] [d, 4] [c, 3] [b, 2] [a, 1]
unordered_map::unordered_map
Создает объект контейнера.
unordered_map(const unordered_map& Right); explicit unordered_map( size_type Bucket_count = N0, const Hash& Hash = Hash(), const Comp& Comp = Comp(), const Allocator& Al = Allocator()); unordered_map(unordered_map&& Right); unordered_map(initializer_list IList); unordered_map(initializer_list IList, size_type Bucket_count); unordered_map( initializer_list IList, size_type Bucket_count, const Hash& Hash); unordered_map( initializer_list IList, size_type Bucket_count, const Hash& Hash, KeyEqual& equal); unordered_map( initializer_list IList, size_type Bucket_count, const Hash& Hash, KeyEqual& Equal const Allocator& Al); template unordered_map( InputIterator First, InputIterator Last, size_type Bucket_count = N0, const Hash& Hash = Hash(), const Comp& Comp = Comp(), const Allocator& Al = Alloc());
Параметры
Al
Объект распределителя для сохранения.
Comp
Объект функции сравнения для сохранения.
Hash
Объект хэш-функции для сохранения.
Bucket_count
Минимальное количество блоков.
Right
Контейнер для копирования.
First
Позиция первого элемента, который следует скопировать.
Last
Позиция непосредственно перед последним элементом, который следует скопировать.
IList
Список initializer_list с элементами, которые необходимо скопировать.
Замечания
Первый конструктор определяет копию последовательности, управляемой right . Второй конструктор определяет управляемую пустую последовательность. Третий конструктор добавляет последовательность значений элементов [first, last) . Четвертый конструктор задает копию последовательности путем перемещения right .
Все конструкторы также инициализируют ряд сохраненных значений. Для конструктора копии значения извлекаются из элемента Right . В противном случае:
Минимальное количество сегментов является аргументом Bucket_count , если он присутствует; в противном случае это значение по умолчанию, описанное здесь как значение N0 , определяемое реализацией.
Объект хэш-функции — это аргумент Hash , если он присутствует; в противном случае — Hash() это .
Объект функции сравнения — это аргумент Comp , если он присутствует; в противном случае — Pred() значение .
Объект распределителя — это аргумент Al , если он присутствует; в противном случае — Alloc() это .
Пример
// std__unordered_map__unordered_map_construct.cpp // compile with: /EHsc #include #include #include using namespace std; using Mymap = unordered_map; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (const auto& c : c1) < cout cout (), equal_to(), allocator >()); c2.insert(Mymap::value_type('d', 4)); c2.insert(Mymap::value_type('e', 5)); c2.insert(Mymap::value_type('f', 6)); // display contents " [f 6] [e 5] [d 4]" for (const auto& c : c2) < cout cout << endl; Mymap c3(c1.begin(), c1.end(), 8, hash(), equal_to(), allocator >()); // display contents " [c 3] [b 2] [a 1]" for (const auto& c : c3) < cout cout << endl; Mymap c4(move(c3)); // display contents " [c 3] [b 2] [a 1]" for (const auto& c : c4) < cout cout c5(< < 5, 'g' >, < 6, 'h' >, < 7, 'i' >, < 8, 'j' >>); for (const auto& c : c5) < cout cout c6(< < 5, 'g' >, < 6, 'h' >, < 7, 'i' >, < 8, 'j' >>, 4); for (const auto& c : c1) < cout cout << endl; cout << endl; // Initializer_list plus size and hash unordered_map c7( < < 5, 'g' >, < 6, 'h' >, < 7, 'i' >, < 8, 'j' >>, 4, hash() ); for (const auto& c : c1) < cout cout << endl; // Initializer_list plus size, hash, and key_equal unordered_map c8( < < 5, 'g' >, < 6, 'h' >, < 7, 'i' >, < 8, 'j' >>, 4, hash(), equal_to() ); for (const auto& c : c1) < cout cout << endl; // Initializer_list plus size, hash, key_equal, and allocator unordered_map c9( < < 5, 'g' >, < 6, 'h' >, < 7, 'i' >, < 8, 'j' >>, 4, hash(), equal_to(), allocator >() ); for (const auto& c : c1) < cout cout
[a, 1] [b, 2] [c, 3] [d, 4] [e, 5] [f, 6] [a, 1] [b, 2] [c, 3] [a, 1] [b, 2] [c, 3] [5, g] [6, h] [7, i] [8, j] [a, 1] [b, 2] [c, 3] [a, 1] [b, 2] [c, 3] [a, 1] [b, 2] [c, 3] [a, 1] [b, 2] [c, 3]
unordered_map::value_type
typedef std::pair value_type;
Замечания
Тип описывает элемент управляемой последовательности.
Пример
// std__unordered_map__unordered_map_value_type.cpp // compile with: /EHsc #include #include typedef std::unordered_map Mymap; int main() < Mymap c1; c1.insert(Mymap::value_type('a', 1)); c1.insert(Mymap::value_type('b', 2)); c1.insert(Mymap::value_type('c', 3)); // display contents " [c 3] [b 2] [a 1]" for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second << "]"; std::cout << std::endl; // add a value and reinspect Mymap::key_type key = 'd'; Mymap::mapped_type mapped = 4; Mymap::value_type val = Mymap::value_type(key, mapped); c1.insert(val); for (Mymap::const_iterator it = c1.begin(); it != c1.end(); ++it) std::cout first second
[c, 3] [b, 2] [a, 1] [d, 4] [c, 3] [b, 2] [a, 1]