Класс hash_set

Статья
06/09/2015

Примечание

Этот API устарел.Альтернативой является Класс unordered_set.

Hash_set расширение класса контейнера стандартной библиотеки шаблонов (STL) и используется для хранения и быстрого считывания данных из коллекции, в которой содержатся значения элементов, который является уникальным и служат в качестве значения ключа.

template <
   class Key, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<Key> 
>
class hash_set

Параметры

Key
Тип данных элементов, сохраняемых в hash_set.
Traits
Тип, содержащий 2 объекта функции, один из класса, который сравнивает бинарный предикат способна для сравнения значения 2 элемента в качестве ключей сортировки для определения относительный порядок и хэш-функция, значения ключа унарные сопоставления предиката элементов в целые числа без знака типа size_t. Этот аргумент является необязательным и hash_compare*<Key,* less*<Key>>*— значение по умолчанию.
Allocator
Тип, представляющий сохраненный объект распределителя, инкапсулирующий информацию о выделении hash_set и освобождение памяти. Этот аргумент является необязательным и значение по умолчанию allocator*<Key>.*

Заметки

Hash_set выглядит следующим образом:

Ассоциативный контейнер, который контейнер переменного размера, который поддерживает эффективное получение значений на основе элемента связанного значения ключа. Кроме того, это простой ассоциативный контейнер, поскольку его значения элемента его значений ключа.
Reversible, поскольку он предоставляет двунаправленный итератор для получения его элементы.
Хэшированный, поскольку элементы группированы в блоки на основе значения свойства хэш-функции примененного к значениям ключа элементов.
Уникально в том смысле, что каждое из его элементов должен иметь уникальный ключ. Поскольку hash_set также простой ассоциативный контейнер, элементы также уникальны.
Класс шаблона, поскольку функция он предоставляет универсален и поэтому не зависят от конкретного типа данных, содержащихся в виде элементов или ключи. Типы данных, используемые для элементов и ключей, вместо этого определяются как параметры в шаблоне класса вместе с функцией и распределителем сравнения.

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

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

Hash_set должно быть ассоциативным контейнером варианта при условия сопоставляет значения с внешним ключам удовлетворяются приложением. Элементы hash_set уникальным и служат в качестве свои ключи сортировки. Модель для этого типа структуры упорядоченный список, сообщает, ключевые слова, в которых ключевые слова могут происходить только один раз. Если несколько вхождений слов были разрешены, hash_multiset была бы соответствующей структуре контейнера. Если значения должны быть вложенным в список ключевых слов уникального ключа, hash_map была бы соответствующей структурой, содержащие эти данные. Если вместо этого ключи не является уникальным, то hash_multimap будет контейнером варианта.

Hash_set сортирует последовательность его элементы управления путем вызова, сохраненный объект Признаки хэш типа value_compare. Этот сохраненный объект может быть получен доступ, вызвав функцию-член key_comp. Такой объект функции должен работать так же, как объект hash_compareKey< класса , lessKey<>>. В частности, для всех значений _Key ключа типа, характеристика вызова (_Key ) создает распределение значений size_t типа.

Как правило, элементы должны быть просто меньше соответствующий установить этот порядок. таким образом, чтобы данные, все 2 элемента он мог быть определен того, что они эквивалентны (в том смысле, что ни одно меньше другой) или, чтобы один меньше другой. Это приводит к тому, что порядок неравнозначными между элементами. На более технического примечания, функция сравнения бинарный предикат, который вызывает строгого слабое упорядочение в стандартном математически смысле. Бинарный предикат f(x,y) объект функции с 2 объекта аргумента x и y и возвращаемое значение из истинного или false. Упорядочение вызванная на hash_set строгие слабые приказывающ бинарный irreflexive, если предикат антисимметрический и транзитивн и если эквивалентность транзитивна, где 2 объекта x и y, чтобы быть соответствующие, когда f(x,y) и f(y,x) равны False. Если более строгое условие равенства между ключами заменяет любую из эквивалентности, порядок будет итогом (в том смысле, что все элементы упорядочены по отношению к друг друга) и соответствующие ключи, которые будут indiscernible друг от друга.

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

Итератор, предоставляемого классом hash_set двунаправленный итератор, но функции INSERT и hash_set члена класса имеют версии, которые принимают в качестве параметров шаблона более предоставляет итератор ввода, которого требования к функции минимальне от тех гарантированные классом двунаправленных итераторов. Другая форма итератора семейство уточнениями понятий, связанных в их функции. Каждое понятие итератора имеет собственный набор требований и алгоритмы, которые работают с ними ограничение включение файла их условий с требованиями, предоставляемым этим типом итератора. Оно может быть высказыван предполагать, что итератору ввода может быть разыменован для обращения к определенному объекту и он может быть инкрементирован следующему итератору в последовательности. Это минимальный набор функциональных возможностей, но достаточно, чтобы иметь возможность контактировать учитывается о диапазоне итераторов [_First, _Last) в контексте функций членов класса.

В Visual C++ .NET 2003 C, элементы файла заголовка <hash_map> и <hash_set> больше не в пространстве имен std, а перемещается в пространство имен stdext. Дополнительные сведения см. в разделе Пространство имен stdext.

конструкторов;

hash_set

Создает hash_set, пусты, или скопировать все или часть другого hash_set.

Определения типов

allocator_type	Тип, представляющий класс allocator для объекта hash_set.
const_iterator	Тип, предоставляющий двунаправленный итератор, который может считывать элемент const в hash_set.
const_pointer	Тип, который содержит указатель элемент const в hash_set.
const_reference	Тип, который предоставляет ссылку на элемент const хранящихся в hash_set для чтения и выполнения операций const.
const_reverse_iterator	Тип, предоставляющий двунаправленный итератор, который может считывать любой элемент const в hash_set.
difference_type	Тип знакового целого числа, который можно использовать для представления число элементов hash_set в диапазоне между элементами указал к итераторам.
итератор	Тип, предоставляющий двунаправленный итератор, который может считывать и изменять любой элемент в hash_set.
key_compare	Тип, который предоставляет объект функции, можно сравнивать 2 ключа сортировки для определения относительный порядок 2 элементов в hash_set.
key_type	Тип, который описывает объект, хранящийся в качестве элемента hash_set его ресурсов в качестве ключа.
указатель	Тип, который содержит указатель элемент в hash_set.
Ссылка	Тип, который предоставляет ссылку на элемент хранящихся в hash_set.
reverse_iterator	Тип, предоставляющий двунаправленный итератор, который может считывать и изменять элемент в обращенном hash_set.
size_type	Тип целого числа без знака, которое может быть представлено число элементов в hash_set.
value_compare	Тип, предоставляющий 2 объекта функции, бинарный предикат класса сравнения, можно сравнивать значения 2 элемента hash_set для определения относительный порядок и унарный предикат, хэширует элементы.
value_type	Тип, который описывает объект, хранящийся в качестве элемента hash_set его ресурсов в качестве значения.

Функции-члены

begin	Возвращает итератор, принимаются первый элемент в hash_set.
hash_set::cbegin	Возвращает итератор const слишком первый элемент в hash_set.
hash_set::cend	Возвращает итератор const, принимаются расположение последующими последний элемент в hash_set.
clear	Удаляет все элементы hash_set.
count	Возвращает количество элементов в hash_set ключ которого соответствует параметр- указанному ключу.
hash_set::crbegin	Возвращает итератор const слишком первый элемент в обращенном hash_set.
hash_set::crend	Возвращает итератор const, принимаются расположение последующими последний элемент в обращенном hash_set.
hash_set::emplace	Вставляет элемент построен на месте в hash_set.
hash_set::emplace_hint	Вставляет элемент построен на месте в hash_set, с подсказками размещения.
empty	Если тесты hash_set пусто.
end	Возвращает итератор, принимаются расположение последующими последний элемент в hash_set.
equal_range	Возвращает пару итераторов соответственно на первый элемент в hash_set с ключом, который больше, чем указанный ключ и на первый элемент в hash_set с ключом, равно или больше значения ключа.
erase	Удаляет элемент или набор элементов в hash_set из заданных позиций или удалять элементы, соответствующие указанному ключу.
find	Возвращает итератор слишком расположение элемента в hash_set, ключ имеет соответствующий указанному ключу.
get_allocator	Возвращает копию объекта allocator, используемого для создания hash_set.
Вставка	Вставляет элемент или набор элементов в hash_set.
key_comp	Извлекает копию объекта сравнения, используемого для ключей, в hash_set.
lower_bound	Возвращает итератор на первый элемент в hash_set с ключом, равно или больше, чем указанный ключ.
max_size	Возвращает максимальную длину hash_set.
rbegin	Возвращает итератор слишком первый элемент в обращенном hash_set.
rend	Возвращает итератор, принимаются расположение последующими последний элемент в обращенном hash_set.
size	Возвращает количество элементов в hash_set.
буфер обмена	Меняет местами элементы 2 hash_set s.
upper_bound	Возвращает итератор на первый элемент в hash_set, ключом, равно или больше, чем указанный ключ.
value_comp	Извлекает копию объекта характеристик хэш, используемого в хэша и значения ключа элемента, в hash_set.