Класс unordered_multiset

Статья
06/09/2015

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

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

Параметры

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

Члены

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

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

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

Заметки

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

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

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

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