Класс hash_map

Статья
06/09/2015

Примечание

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

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

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

Параметры

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

Заметки

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

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

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

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

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

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

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

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

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

В Visual C++ .NET 2003 C, элементы файла заголовка <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 ключа сортировки для определения относительный порядок 2 элементов в hash_map.
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.
Вставка	Вставляет элемент или набор элементов в 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 s.
upper_bound	Возвращает итератор на первый элемент в hash_map, со значением ключа, более чем одно из указанного ключа.
value_comp	Извлекает копию объекта сравнения, используемого в значения элемента, в hash_map.

Операторы

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