Класс unordered_set

Статья
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_set;

Параметры

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

Члены

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

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

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

Заметки

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

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

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

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