Как работает unordered map

Классы unordered_map и unordered_multimap: ассоциативные массивы

Класс unordered_map реализует ассоциативный массив, в котором каждому ключу соответствует одно значение. Чтобы получить доступ к элементу, необходимо указать ключ, который использовался при сохранении элемента. В отличии от класса map для быстрого поиска элементов используется хеш-таблица, значения которой состоят из целых чисел (тип size_t ). Класс unordered_multimap реализует ассоциативный массив, в котором одному ключу могут соответствовать несколько значений. Работа с классами производится аналогичным образом, поэтому в этом разделе мы рассмотрим только возможности класса unordered_map .

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

Класс hash: хеш

Для быстрого поиска элементов в классах unordered_map и unordered_multimap используется хеш-таблица, значения которой состоят из целых чисел (тип size_t ). Получить эти значения для основных типов позволяет класс hash . Прежде чем использовать класс, необходимо в начало программы добавить инструкцию:

При объявлении переменной после названия класса внутри угловых скобок указывается элементарный тип данных или тип указателя. Чтобы получить хеш следует передать значение внутри круглых скобок. Для одного и того же значения хеш всегда будет одинаковым:

В других заголовочных файлах существуют реализации для классов string , wstring , u16string , u32string , vector<bool> , bitset , unique_ptr , shared_ptr и др. Пример получения хеша для строки:

Создание объекта

Объявление класса unordered_map :

Основные псевдонимы для типов:

Создать экземпляр класса unordered_map можно следующими способами (полный список конструкторов смотрите в документации):

• объявить переменную без инициализации. Для этого перед названием переменной указывается название класса, а после названия внутри угловых скобок через запятую задаются типы данных ключа и значения. В этом случае словарь не содержит элементов. Пример объявления без инициализации:

Внутри угловых скобок после типов данных ключа и значения можно дополнительно указать функцию для получения хеша и функцию сравнения для ключа:

• указать объект класса unordered_map внутри круглых скобок или после оператора = (доступны конструкторы копирования и перемещения):

• указать диапазон внутри контейнера с помощью итераторов. В первом параметре передается итератор, указывающий на начало диапазона, а во втором параметре — итератор, указывающий на конец диапазона. Пример:

• указать список инициализации, состоящий из объектов класса pair :

Вместо объектов класса pair можно указать ключи и значения через запятую внутри фигурных скобок:

Над двумя объектами класса unordered_map определены операции == и != . Кроме того, один объект можно присвоить другому объекту. В этом случае выполняется поэлементное копирование (оператор копирования) или перемещение элементов (оператор перемещения). Пример:

Доступно также присваивание элементов из списка инициализации:

Вставка элементов

Вставить элемент можно указав ключ внутри квадратных скобок. Значение элемента задается после оператора присваивания. Если ключ уже существует, то вместо вставки элемента производится изменение значения. Пример:

Вставить элементы позволяют следующие методы:

• insert() — вставляет один или несколько элементов. Прототипы метода:

Первые два прототипа вставляют экземпляр класса pair и возвращают объект того же класса. Через свойство first будет доступен итератор, указывающий на вставленный элемент, а через свойство second — логическое значение true , если элемент вставлен, и false — в противном случае. Обратите внимание на то, что вставить можно только элемент, ключ которого не содержится в словаре. Пример:

Обратите внимание на то, что метод insert() в классе unordered_multimap возвращает итератор, а не объект класса pair . Прототипы метода в классе unordered_multimap :

Можно вставить элементы, имеющие одинаковый ключ:

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

Пятый прототип вставляет элементы из диапазона, ограниченного итераторами first и last :

Шестой прототип вставляет элементы из списка инициализации:

• emplace() — создает элемент и вставляет его в словарь. Метод возвращает объект класса pair . Через свойство first будет доступен итератор, указывающий на вставленный элемент, а через свойство second — логическое значение true , если элемент вставлен, и false — в противном случае. Обратите внимание на то, что вставить можно только элемент, ключ которого не содержится в словаре. Прототип метода:

Обратите внимание на то, что метод emplace() в классе unordered_multimap возвращает итератор, а не объект класса pair . Прототип метода в классе unordered_multimap :

Можно вставить элементы, имеющие одинаковый ключ:

• emplace_hint() — аналогичен методу emplace() , но дополнительно позволяет подсказать позицию вставки с помощью итератора. Метод возвращает итератор на вставленный элемент или на существующий элемент (вставить элемент с одинаковым ключом нельзя). Прототип метода:

• swap() — меняет элементы двух контейнеров местами. Прототип метода:

Вместо метода swap() можно воспользоваться одноименной функцией:

Определение количества элементов

Для определения количества элементов предназначены следующие методы:

• size() — возвращает количество элементов в словаре. Прототип метода:

• empty() — возвращает значение true , если словарь не содержит элементов, и false — в противном случае. Прототип метода:

• max_size() — возвращает максимальное количество элементов, которое теоретически может содержаться в словаре. Прототип метода:

Удаление элементов

Для удаления элементов предназначены следующие методы:

• erase() — удаляет один элемент или элементы из диапазона. Прототипы метода:

Первый прототип удаляет элемент с указанным ключом и возвращает количество удаленных элементов:

Второй прототип удаляет элемент на который указывает итератор:

Третий прототип удаляет элементы из диапазона, ограниченного итераторами first и last . Удалим все элементы:

• clear() — удаляет все элементы. Прототип метода:

Доступ к элементам

К любому элементу словаря можно обратиться как к элементу массива. Достаточно указать его ключ внутри квадратных скобок. Можно как получить значение, так и изменить его. Если производится присваивание значения по ключу и ключа не существует, то производится вставка элемента. Если элемент уже существует, то его значение изменяется на новое. Если производится получение значения по ключу и ключа не существует, то элемент вставляется со значением по умолчанию для типа, а затем это значение возвращается. Пример:

Для доступа к элементам предназначены следующие методы:

• at() — возвращает ссылку на элемент, ключ которого соответствует значению k . Метод позволяет как получить значение, так и изменить его. Если ключ не существует, то генерируется исключение out_of_range . Прототипы метода:

• count() — возвращает количество элементов, у которых ключ соответствуют значению k . Прототип метода:

• find() — возвращает итератор, установленный на элемент, ключ которого соответствует значению k . Если элемент не найден, то метод возвращает итератор, указывающий на позицию после последнего элемента. Прототипы метода:

• equal_range() — возвращает экземпляр класса pair . Через свойство first будет доступен итератор, ссылающийся на первый элемент с указанным ключом, а через свойство second — итератор, ссылающийся на позицию после последнего элемента с указанным ключом. Если ключ отсутствует в словаре, то оба итератора будут ссылаться на значение, возвращаемое методом end() . Прототипы метода:

• begin() , end() , cbegin() и cend() — возвращают итераторы (см. разд. 16.1.1). Обратите внимание: обратные итераторы не поддерживаются. Перебор возможен только в прямом порядке. Выведем ключ и значение первого элемента:

Обратите внимание: итераторы не поддерживают операторы + , — и — . Для перемещения итератора нужно использовать оператор ++ или функцию advance() . Пример доступа к третьему элементу словаря:

Вместо методов begin() и end() можно воспользоваться одноименными функциями. Выведем ключ и значение первого элемента:

Перебор элементов

Перебрать все элементы можно с помощью цикла for each , итераторов и алгоритма for_each() . Обратите внимание: перебор элементов возможен только в прямом направлении, кроме того, порядок следования элементов может быть произвольным. Пример использования цикла for each (внутри тела цикла можно изменить значение элемента, но ключ изменить нельзя):

Пример перебора элементов с помощью итераторов и цикла for :

Пример перебора элементов с помощью итераторов и цикла while :

С помощью алгоритма for_each() умножим значение каждого элемента на 2 , а затем выведем все ключи и значения в окно консоли:

Учебник C++ (Qt Creator и MinGW) в формате PDF

Помощь сайту

ПАО Сбербанк:
Счет: 40817810855006152256
Реквизиты банка:
Наименование: СЕВЕРО-ЗАПАДНЫЙ БАНК ПАО СБЕРБАНК
Корреспондентский счет: 30101810500000000653
БИК: 044030653
КПП: 784243001
ОКПО: 09171401
ОКОНХ: 96130
Скриншот реквизитов

C++ Unordered Map Under the Hood

The std::unordered_map in C++ standard library is a really powerful data structure offering insertion, deletion, and lookup in O(1) amortized time. std::unordered_map is implemented as a hashmap or hashtable which are the same thing. This article is going to describe how the C++ standard library implements the unordered_map , how it achieves those time complexities, and when to use it.

Member Variables

std::unordered_map is an array of linked lists of pairs. They’re pairs because they store a key value pair which are both integers in our case. bucket_size is the size of the array. total_elements is the current number of key value pairs. The max_load_factor is the max ratio of total_elements to bucket_size. If it exceeds this, the hash table is rehashed. Below is a picture representing buckets

Keys are hashed to an index in the array, aka a bucket. In each bucket is the head of a linked list. For example, John Smith and Lisa Smith happen to hash to the same bucket, 152. Thus, they both get added to the linked list for bucket 152. When keys map to the same bucket, this is called a collision.

Functions

hash takes in a key, uses a strong hash function, which could be custom, then mods it by the bucket_size to get the bucket index. It’s very important to use a good strongHashingFunction that can evenly and randomly distribute its outputs. If not, you will have more collisions which could degrade the time complexity significantly.

find will search for the key and return a list iterator to it if it exists.

insert first checks if the key exists already. If so, it modifies that key’s value. Otherwise, it pushes the value back on the linked list. If needed we’ll expand the buckets and rehash everything.

delete finds the key by calling find. It will delete it if found

rehashIfNeeded first checks if the max_load_factor has been exceeded. If so, it will double the size of the array and rehash everything to the new one. The reason we rehash is to decrease the chance of collisions. max_load_factor is set to 1 by default in the standard library implementation. If the total_elements in the map is equal to the bucket_size then there is an average of 1 element per bucket, so collisions could happen but it’s unlikely a lot of them will happen on the same bucket. However, if you have a hashing function that’s time consuming or a lot of elements to copy over, you may want to consider giving the max_load_factor a bit more slack.

Complexity Analysis

find hashes in O(1), then traverses the bucket looking for the key. Assuming that we have a good low factor and a hash functions, the number of collisions or elements in this linked list is constant. In fact, on average, the number of elements in each bucket (collisions) should be less than the max_load_factor . Thus, find is O(1) on average.

delete calls find in O(1) and gets a list::iterator. lists are implemented as doubly linked lists in C++, and deleting a node in a doubly linked list is O(1) operation. Thus, delete is O(1) on average.

insert is a bit more tricky. Most of the time insert calls find in O(1) and does an O(1) modification to the pair, but every so often we have to rehash everything which is an O(n) operation where n is total_elements . So how do we measure a time complexity when its mostly O(1) and rarely O(n)? Do we just say O(n)? No, we used an amortized complexity.

Let’s say bucket_size=99 and max_load_factor=1. So, we insert 99 elements in O(1) time, then the 100th element in O(100) time, then our amortized time complexity is O(2) because (100 for rehashing + 1*every insert)=200 and we got 100 inserts completed. It’s kind of still an average according to the english definition, but it’s a different flavor of average. It’s like overtime, we know we’re going to hit this huge bump in time complexity, but it’s okay because the time complexity was low for so long before and things even out. Thus, insert is amortized O(1) on average.

Неупорядоченная карта в 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 = < < «banana» , «yellow» >,
< «grape» , «green» >, < «fig» , «purple» >, < «strawberry» , «red» >> ;

unordered_map < const char *, const char *> umap2 = < < «cherry» , «red» >, < «lime» , «green» >> ;

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 = < < «banana» , «yellow» >,
< «grape» , «green» >, < «fig» , «purple» >, < «strawberry» , «red» >> ;
unordered_map < const char *, const char *> umap2 = < < «cherry» , «red» >, < «lime» , «green» >> ;

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 = < < «banana» , obj1 >, < «grape» , obj2 >, < «fig» , obj3 >, < «strawberry» , obj4 >, < «lime» , obj5 >> ;

cout << umap. size ( ) << ‘ \n ‘ ;

return 0 ;
>

Определение класса имеет два открытых члена данных и две публичные функции члена. В функции main () создаются экземпляры различных объектов класса. Затем создается неупорядоченная карта, где каждая пара состоит из имени фрукта и объекта из класса. Отображается размер карты. Программа компилируется без предупреждений или сообщений об ошибках.

Применение карты

Массив связывает индекс со значением. Пары ключ / значение существуют во многих жизненных ситуациях, которые можно запрограммировать. Пара ключ / значение фрукт / цвет — лишь один из примеров. Другой пример — имена людей и их возраст. В этом случае пара будет иметь тип pair . Это также может быть пара <строка, число с плавающей запятой>. В последнем случае будет использоваться директива предварительной обработки. Пара ключ / значение по-прежнему может быть именами супружеских пар. В странах, где существует многоженство, у одного мужчины будут разные жены.

Формирование карты

Карта — это не двухмерный массив с двумя столбцами. Карта работает с хеш-функцией. Ключ кодируется хеш-функцией в целое число массива. Именно этот массив содержит значения. Итак, на самом деле существует один массив со значениями, и ключи отображаются на индексы массива, и поэтому между ключами и значениями устанавливаются соответствия. Хеширование — обширная тема, которая не рассматривается в этой статье.

Заключение

Карта, также известная как ассоциативный массив, представляет собой список элементов, где каждый элемент представляет собой пару ключ / значение. Итак, каждый ключ соответствует значению. В C ++ карта реализована как структура данных с функциями-членами и операторами. Упорядоченная карта — это карта, в которой пары элементов упорядочены по ключам. Неупорядоченная карта — это карта, на которой нет порядка.

Технически хеш состоит из пары элементов <type1, type2>. Фактически, пара представляет собой целую структуру данных со своими функциями-членами и операторами. Два параметра шаблона для пары — это те же два параметра шаблона для unordered_map.

Initializer_list для карты — это литерал массива литералов. Каждый внутренний литерал состоит из двух объектов, пары ключ / значение.

Функции-члены и операторы для unordered_map можно разделить на следующие категории: создание / копирование unordered_map, емкость unordered_map, итератор unordered_map, операции unordered_map и модификаторы unordered_map.

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

Name already in use

cpp-docs / docs / standard-library / unordered-map-class.md

• Go to file T
• Go to line L
• Copy path
• Copy permalink

• Open with Desktop
• View raw
• Copy raw contents Copy raw contents

Copy raw contents

Copy raw contents

The class template describes an object that controls a varying-length sequence of elements of type std::pair<const Key, Ty> . The sequence is weakly ordered by a hash function, which partitions the sequence into an ordered set of subsequences called buckets. Within each bucket, a comparison function determines whether any pair of elements has equivalent ordering. Each element stores two objects, a sort key and a value. The sequence is represented in a way that permits lookup, insertion, and removal of an arbitrary element with operations that can be independent of the number of elements in the sequence (constant time), at least when all buckets are of roughly equal length. In the worst case, when all of the elements are in one bucket, the number of operations is proportional to the number of elements in the sequence (linear time). Moreover, inserting an element invalidates no iterators, and removing an element invalidates only those iterators that point at the removed element.

Hash
The hash function object type.

Pred
The equality comparison function object type.

Alloc
The allocator class.

Type Definition	Description
allocator_type	The type of an allocator for managing storage.
const_iterator	The type of a constant iterator for the controlled sequence.
const_local_iterator	The type of a constant bucket iterator for the controlled sequence.
const_pointer	The type of a constant pointer to an element.
const_reference	The type of a constant reference to an element.
difference_type	The type of a signed distance between two elements.
hasher	The type of the hash function.
iterator	The type of an iterator for the controlled sequence.
key_equal	The type of the comparison function.
key_type	The type of an ordering key.
local_iterator	The type of a bucket iterator for the controlled sequence.
mapped_type	The type of a mapped value associated with each key.
pointer	The type of a pointer to an element.
reference	The type of a reference to an element.
size_type	The type of an unsigned distance between two elements.
value_type	The type of an element.

Member Function	Description
at	Finds an element with the specified key.
begin	Designates the beginning of the controlled sequence.
bucket	Gets the bucket number for a key value.
bucket_count	Gets the number of buckets.
bucket_size	Gets the size of a bucket.
cbegin	Designates the beginning of the controlled sequence.
cend	Designates the end of the controlled sequence.
clear	Removes all elements.
count	Finds the number of elements matching a specified key.
contains C++20	Check if there’s an element with the specified key in the unordered_map .
emplace	Adds an element constructed in place.
emplace_hint	Adds an element constructed in place, with hint.
empty	Tests whether no elements are present.
end	Designates the end of the controlled sequence.
equal_range	Finds range that matches a specified key.
erase	Removes elements at specified positions.
find	Finds an element that matches a specified key.
get_allocator	Gets the stored allocator object.
hash_function	Gets the stored hash function object.
insert	Adds elements.
key_eq	Gets the stored comparison function object.
load_factor	Counts the average elements per bucket.
max_bucket_count	Gets the maximum number of buckets.
max_load_factor	Gets or sets the maximum elements per bucket.
max_size	Gets the maximum size of the controlled sequence.
rehash	Rebuilds the hash table.
size	Counts the number of elements.
swap	Swaps the contents of two containers.
unordered_map	Constructs a container object.

Operator	Description
unordered_map::operator[]	Finds or inserts an element with the specified key.
unordered_map::operator=	Copies a hash table.

The object orders the sequence it controls by calling two stored objects, a comparison function object of type unordered_map::key_equal and a hash function object of type unordered_map::hasher . You access the first stored object by calling the member function unordered_map::key_eq () ; and you access the second stored object by calling the member function unordered_map::hash_function () . Specifically, for all values X and Y of type Key , the call key_eq()(X, Y) returns true only if the two argument values have equivalent ordering; the call hash_function()(keyval) yields a distribution of values of type size_t . Unlike class template unordered_multimap Class, an object of type unordered_map ensures that key_eq()(X, Y) is always false for any two elements of the controlled sequence. (Keys are unique.)

The object also stores a maximum load factor, which specifies the maximum desired average number of elements per bucket. If inserting an element causes unordered_map::load_factor () to exceed the maximum load factor, the container increases the number of buckets and rebuilds the hash table as needed.

The actual order of elements in the controlled sequence depends on the hash function, the comparison function, the order of insertion, the maximum load factor, and the current number of buckets. You can’t in general predict the order of elements in the controlled sequence. You can always be assured, however, that any subset of elements that have equivalent ordering are adjacent in the controlled sequence.

The object allocates and frees storage for the sequence it controls through a stored allocator object of type unordered_map::allocator_type . Such an allocator object must have the same external interface as an object of type allocator . The stored allocator object isn’t copied when the container object is assigned.