Класс unordered_multimap

Статья
06/09/2015

Этот шаблонный класс описывает объект, управляющий последовательностью элементов типа std::pair<const Key, Ty> переменной длины. Последовательность слабо упорядочена хэш-функцией, которая разделяет последовательность в упорядоченный набор подпоследовательностей, называемых блоками. В каждом блоке функция сравнения определяет, упорядочена ли каждая пара элементов соответствующим образом. Каждый элемент содержит два объекта: ключ и значение сортировки. Последовательность представляется в виде, позволяющем выполнять поиск, вставку и удаление произвольного элемента несколькими операциями, которые могут не зависеть от числа элементов в последовательности (постоянное время), по крайней мере, когда все блоки имеют примерно одинаковую длину. В худшем случае, когда все элементы находятся в одном блоке, количество операций пропорционально количеству элементов в последовательности (линейное время). Кроме того, вставка элементов не делает итераторы недействительными, а при удалении элементов недействительными становятся только итераторы, указывающие на удаленный элемент.

template<class Key,
    class Ty,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<Key> >
    class unordered_multimap;

Параметры

Параметр	Описание
Key	Тип ключа.
Ty	Сопоставленный тип.
Hash	Тип объекта хэш-функции.
Pred	Тип объекта функции сравнения на предмет равенства.
Alloc	Класс распределителя.

Члены

Определение типа	Описание
unordered_multimap::allocator_type	Тип распределителя для управления хранилищем.
unordered_multimap::const_iterator	Тип постоянного итератора для управляемой последовательности.
unordered_multimap::const_local_iterator	Тип постоянного итератора блока для управляемой последовательности.
unordered_multimap::const_pointer	Тип постоянного указателя на элемент.
unordered_multimap::const_reference	Тип постоянной ссылки на элемент.
unordered_multimap::difference_type	Тип расстояния со знаком между двумя элементами.
unordered_multimap::hasher	Тип хэш-функции.
unordered_multimap::iterator	Тип итератора для управляемой последовательности.
unordered_multimap::key_equal	Тип функции сравнения.
unordered_multimap::key_type	Тип ключа упорядочения.
unordered_multimap::local_iterator	Тип итератора блока для управляемой последовательности.
unordered_multimap::mapped_type	Тип сопоставленного значения, связанного с каждым ключом.
unordered_multimap::pointer	Тип указателя на элемент.
unordered_multimap::reference	Тип ссылки на элемент.
unordered_multimap::size_type	Тип беззнакового расстояния между двумя элементами.
unordered_multimap::value_type	Тип элемента.

Функция-член	Описание
unordered_multimap::begin	Задает начало управляемой последовательности.
unordered_multimap::bucket	Получает номер блока для значения ключа.
unordered_multimap::bucket_count	Получает количество блоков.
unordered_multimap::bucket_size	Получает размер блока.
unordered_multimap::cbegin	Задает начало управляемой последовательности.
unordered_multimap::cend	Задает конец управляемой последовательности.
unordered_multimap::clear	Удаляет все элементы.
unordered_multimap::count	Определяет количество элементов, соответствующих заданному ключу.
unordered_multimap::emplace	Добавляет элемент, созданный на месте.
unordered_multimap::emplace_hint	Добавляет элемент, созданный на месте, с подсказкой.
unordered_multimap::empty	Проверяет отсутствие элементов.
unordered_multimap::end	Задает конец управляемой последовательности.
unordered_multimap::equal_range	Находит диапазон, соответствующий указанному ключу.
unordered_multimap::erase	Удаляет элементы в указанных позициях.
unordered_multimap::find	Определяет элемент, соответствующий указанному ключу.
unordered_multimap::get_allocator	Возвращает сохраненный объект распределителя.
unordered_multimap::hash_function	Получает сохраненный объект хэш-функции.
unordered_multimap::insert	Добавляет элементы.
unordered_multimap::key_eq	Получает сохраненный объект функции сравнения.
unordered_multimap::load_factor	Подсчитывает среднее число элементов в блоке.
unordered_multimap::max_bucket_count	Получает максимальное количество блоков.
unordered_multimap::max_load_factor	Возвращает или задает максимальное количество элементов в блоке.
unordered_multimap::max_size	Возвращает максимальный размер управляемой последовательности.
unordered_multimap::rehash	Повторно создает хэш-таблицу.
unordered_multimap::size	Подсчитывает количество элементов.
unordered_multimap::swap	Меняет местами содержимое двух контейнеров.
unordered_multimap::unordered_multimap	Создает объект контейнера.

Оператор	Описание
unordered_multimap::operator=	Копирует хэш-таблицу.

Заметки

Объект упорядочивает управляемую им последовательность путем вызова двух сохраненных объектов, объекта функции сравнения типа unordered_multimap::key_equal и объекта хэш-функции типа unordered_multimap::hasher. Доступ к первому сохраненному объекту можно получить, вызвав функцию-член unordered_multimap::key_eq(); доступ ко второму сохраненному объекту выполняется путем вызова функции-члена unordered_multimap::hash_function(). В частности, для всех значений X и Y типа Key вызов key_eq()(X, Y) возвращает значение true, только если два значения аргументов имеют соответствующий порядок; вызов hash_function()(keyval) создает распределение значений типа size_t. В отличие от шаблонного класса Класс unordered_map объект шаблонного класса unordered_multimap не гарантирует, что key_eq()(X, Y) всегда имеет значение false для любых двух элементов управляемой последовательности. (Ключи не обязательно должны быть уникальными.)

Объект также хранит максимальный коэффициент нагрузки, который определяет максимальное желаемое среднее количество элементов в блоке. Если вставка элемента вызывает превышение значением unordered_multimap::load_factor() максимального коэффициента нагрузки, контейнер увеличивает количество блоков и перестраивает хэш-таблицу по мере необходимости.

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

Объект выделяет и освобождает хранилище для управляемой им последовательности с помощью сохраненного объекта распределителя типа unordered_multimap::allocator_type. Такой объект распределителя должен иметь такой же внешний интерфейс, как объект шаблонного класса allocator. Обратите внимание, что сохраненный объект распределителя не копируется, когда назначается объект контейнера.