hash_map Class

Статья
03/27/2013

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

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

template <
   class Key, 
   class Type, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<pair <const Key, Type> > 
>
class hash_map

Параметры

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

Заметки

Hash_map:

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

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

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

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

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

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

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

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

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

Конструкторы

hash_map

Создает hash_map, пусты или все или часть, являющийся копией другого hash_map.

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

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

Функции элементов

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

Операторы

operator[]	Вставляет элемент в hash_map с указанным значением ключа.
hash_map::operator=	Заменяет элементы hash_map копией другого hash_map.