hash_set Class

Статья
03/27/2013

Примечание
Этот API устарел.Альтернативы unordered_set Class.

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 упорядочивает последовательность, он контролирует путем вызова хранимой Traits хэш объект типа value_compare.Этот, сохраненный объект можно получить доступ путем вызова функции-члена key_comp.Такой объект функции должен вести себя так же, как и объект класса hash_compare<Key, less<Key> >. В частности, для всех значений _Key ключа, принадлежащая к типу, признак вызова (_Key ) создает распределение значений size_t типа.

Как правило, элементы должны быть просто меньше, чем эквивалентный установить этот порядок. таким образом, что заданный какие-либо 2 элемента он может быть определен этому, что они эквивалентны (в том смысле, что ни одно из значений не меньше другого) или что один меньше другого.Это приводит к тому, что упорядочение между элементами неравнозначными.На более технической заметку, функция сравнения является строгий порядок предикат, накладывают слабых в стандартном математические смысле.Binary предикат f(x,y) объект функции, имеется 2 объекта аргумента x и y, а возвращаемое значение из true или 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 <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 ключа сортировки, чтобы указать относительный порядок элементов в hash_set2.
key_type	Тип, описывающий объект, хранящийся как элемент hash_set в его емкости как ключ сортировки.
указатели	Тип, который предоставляет указатель элемент в hash_set.
Ссылка	Тип, который предоставляет ссылку на элемент, хранящийся в hash_set.
reverse_iterator	Тип, предоставляющий двунаправленный итератор, который может считывать или изменяет элемент в обращенном hash_set.
size_type	Тип целого числа без знака, которое может представлять число элементов в hash_set.
value_compare	Тип, предоставляющий 2 объекта функции является предикат класса сравнивает который может сравнить значения элементов hash_set 2 для определения их относительного порядка и унарный предикат этот хэш элементы.
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.
insert	Вставляет элемент или диапазон элементов в 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.
upper_bound	Возвращает итератор к первому элементу в hash_set, с ключом, равно или больше, чем заданный ключ.
value_comp	Извлекает копию признаков хэш объект используемый для хэша и упорядочение значений ключей элементов в hash_set.