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

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

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

История

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

В хэш_ * шаблоны классов были предложены в Технический отчет C ++ 1 (C ++ TR1) и были приняты под именами неупорядоченный_*.^[3] Позже они были включены в C ++ 11 пересмотр стандарта C ++.^[4] Реализация также доступна в Библиотеки Boost C ++ в качестве <boost/unordered_map.hpp>.^[5]

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

Контейнеры определены в заголовках, названных по именам контейнеров, например, unordered_set определено в заголовке <unordered_set>. Все контейнеры соответствуют требованиям Контейнер концепция, что означает, что у них есть начинать(), конец(), размер(), max_size (), пустой(), и замена() методы.

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

#включают <iostream>#включают <string>#включают <unordered_map> int главный(){    стандартное::unordered_map<стандартное::нить, int> месяцы;    месяцы["январь"] = 31;    месяцы["февраль"] = 28;    месяцы["марш"] = 31;    месяцы["апреля"] = 30;    месяцы["май"] = 31;    месяцы["июнь"] = 30;    месяцы["июль"] = 31;    месяцы["август"] = 31;    месяцы["сентябрь"] = 30;    месяцы["октябрь"] = 31;    месяцы["ноябрь"] = 30;    месяцы["Декабрь"] = 31;    стандартное::cout << "сентябрь ->" << месяцы["сентябрь"] << стандартное::конец;    стандартное::cout << "апрель ->" << месяцы["апреля"] << стандартное::конец;    стандартное::cout << "декабрь ->" << месяцы["Декабрь"] << стандартное::конец;    стандартное::cout << "февраль ->" << месяцы["февраль"] << стандартное::конец;    возвращаться 0;}

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

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

#включают <unordered_map> структура Икс{int я,j,k;};структура hash_X{  size_t оператор()(const Икс &Икс) const{    возвращаться стандартное::хэш<int>()(Икс.я) ^ стандартное::хэш<int>()(Икс.j) ^ стандартное::хэш<int>()(Икс.k);  }};

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

 стандартное::unordered_map<Икс,int,hash_X> my_map;

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

пространство имен стандартное {    шаблон <>        учебный класс хэш<Икс>{        общественный :        size_t оператор()(const Икс &Икс ) const{            возвращаться хэш<int>()(Икс.я) ^ хэш<int>()(Икс.j) ^ хэш<int>()(Икс.k);        }    };}//... стандартное::unordered_map<Икс,int> my_map;

Рекомендации