Неупорядоченные ассоциативные контейнеры (C++)

В языке программирования C++ неупорядоченные ассоциативные контейнеры представляют собой группу шаблонов классов в стандартной библиотеке C++ , которые реализуют варианты хеш-таблиц . Будучи шаблонами , они могут использоваться для хранения произвольных элементов, таких как целые числа или пользовательские классы. В текущей версии стандарта C++ определены следующие контейнеры: unordered_set, unordered_map, unordered_multiset, unordered_multimap. Каждый из этих контейнеров отличается только ограничениями, налагаемыми на их элементы.

Неупорядоченные ассоциативные контейнеры аналогичны ассоциативным контейнерам стандартной библиотеки C++, но имеют другие ограничения. Как следует из названия, элементы в неупорядоченных ассоциативных контейнерах не упорядочены . Это связано с использованием хеширования для хранения объектов. Контейнеры по-прежнему можно перебирать , как обычный ассоциативный контейнер.

История

Первой широко используемой реализацией хеш-таблиц на языке C++ была hash_map, hash_set, hash_multimap, hash_multiset шаблоны классов Silicon Graphics (SGI) стандартной библиотеки шаблонов (STL). Из-за своей полезности они позже были включены в несколько других реализаций стандартной библиотеки C++ (например, в коллекцию компиляторов GNU (GCC) libstdc++). и стандартная библиотека Visual C++ (MSVC).

The hash_* шаблоны классов были предложены в Техническом отчете C++ 1 (C++ TR1) и приняты под именами unordered_*. Позже они были включены в версию C++11 стандарта C++. Реализация также доступна в библиотеках Boost C++ как <boost/unordered_map.hpp>.

Обзор функций

Контейнеры определяются в заголовках, названных по именам контейнеров, например: unordered_set определяется в заголовке <unordered_set>. Все контейнеры удовлетворяют требованиям Container концепции , а это значит, что они имеют begin(), end(), size(), max_size(), empty(), и swap() методы.

	unordered_set ( С++ 11 )	unordered_map (С++11)	unordered_multiset (С++11)	unordered_multimap (С++11)	Описание
	(конструктор)	(конструктор)	(конструктор)	(конструктор)	Создает контейнер из различных источников.
	(деструктор)	(деструктор)	(деструктор)	(деструктор)	Уничтожает набор и содержащиеся в нем элементы
	operator=	operator=	operator=	operator=	Присваивает значения контейнеру
	get_allocator	get_allocator	get_allocator	get_allocator	Возвращает распределитель, используемый для выделения памяти для элементов.
Доступ к элементу	—	at	—	—	Доступ к указанному элементу с проверкой границ.
	—	operator[]	—	—	Доступ к указанному элементу без проверки границ.
Итераторы	begin	begin	begin	begin	Возвращает итератор в начало контейнера
	end	end	end	end	Возвращает итератор до конца контейнера
Емкость	empty	empty	empty	empty	Проверяет, пуст ли контейнер
	size	size	size	size	Возвращает количество элементов в контейнере.
	max_size	max_size	max_size	max_size	Возвращает максимально возможное количество элементов в контейнере
Модификаторы	clear	clear	clear	clear	Очищает содержимое.
	insert	insert	insert	insert	Вставляет элементы.
	emplace	emplace	emplace	emplace	Конструирует элементы на месте ( C++11 )
	emplace_hint	emplace_hint	emplace_hint	emplace_hint	Конструирует элементы на месте, используя подсказку ( C++11 ).
	erase	erase	erase	erase	Стирает элементы.
	swap	swap	swap	swap	Заменяет содержимое другим контейнером.
Искать	count	count	count	count	Возвращает количество элементов, соответствующих определенному ключу.
	find	find	find	find	Находит элемент с определенным ключом.
	equal_range	equal_range	equal_range	equal_range	Возвращает диапазон элементов, соответствующих определенному ключу.
Интерфейс сегмента	...
Хэш-политика	...
наблюдатели	hash_function	hash_function	hash_function	hash_function	Возвращает функцию, используемую для создания хэша ключа.
	key_eq	key_eq	key_eq	key_eq	Возвращает функцию сравнения ключей.

Пример использования

#include <iostream>
#include <string>
#include <unordered_map>
 
int main()
{
    std::unordered_map<std::string, int> months;
    months["january"] = 31;
    months["february"] = 28;
    months["march"] = 31;
    months["april"] = 30;
    months["may"] = 31;
    months["june"] = 30;
    months["july"] = 31;
    months["august"] = 31;
    months["september"] = 30;
    months["october"] = 31;
    months["november"] = 30;
    months["december"] = 31;
    std::cout << "september -> " << months["september"] << std::endl;
    std::cout << "april     -> " << months["april"] << std::endl;
    std::cout << "december  -> " << months["december"] << std::endl;
    std::cout << "february  -> " << months["february"] << std::endl;
    return 0;
}

Пользовательские хэш-функции

Чтобы использовать пользовательские объекты в std::unordered_map, необходимо определить пользовательскую хеш-функцию. Эта функция принимает константную ссылку на пользовательский тип и возвращает size_t.

#include <unordered_map>
 
struct X{int i,j,k;};

struct hash_X{
  size_t operator()(const X &x) const{
    return std::hash<int>()(x.i) ^ std::hash<int>()(x.j) ^ std::hash<int>()(x.k);
  }
};

Пользовательскую функцию можно использовать как есть в std::unordered_map, передав ее в качестве параметра шаблона.

 std::unordered_map<X,int,hash_X> my_map;

Или может быть установлен в качестве хэш-функции по умолчанию, специализируясь на функции std::hash.

namespace std {
    template <>
        class hash<X>{
        public :
        size_t operator()(const X &x ) const{
            return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
        }
    };
}

//...
 std::unordered_map<X,int> my_map;