Стенли Липпман - Язык программирования C++. Пятое издание

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

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

size_t hasher(const Sales_data &sd) {

return hash()(sd.isbn());

}

bool eqOp(const Sales_data &lhs, const Sales_data &rhs) {

return lhs.isbn() == rhs.isbn();

}

Чтобы создать хеш-код для переменной-члена ISBN, функция hasher()использует объект библиотечного типа hashдля типа string. Точно так же функция eqOp()сравнивает два объекта класса Sales_data, сравнивая их ISBN.

Эти функции можно также использовать для определения контейнера unordered_multisetследующим образом:

using SD_multiset = unordered_multiset

decltype(hasher)*, decltype(eqOp)*>;

// аргументы - размер ячейки, указатель на оператор равенства и

// хеш-функцию

SD_multiset bookstore(42, hasher, eqOp);

Чтобы упростить объявление bookstore, определим сначала псевдоним типа (см. раздел 2.5.1) для контейнера unordered_multiset, у хеша и оператора равенства которого есть те же типы, что и у функций hasher()и eqOp(). Используя этот тип, определим bookstore, передав указатели на функции, которые он должен использовать.

Если у класса есть собственный оператор ==, можно переопределить только хеш-функцию:

// использовать FooHash для создания хеш-кода;

// у Foo должен быть оператор ==

unordered_set fooSet(10, FooHash);

Упражнение 11.37. Каковы преимущества неупорядоченного контейнера по сравнению с упорядоченной версией этого контейнера? Каковы преимущества упорядоченной версии?

Упражнение 11.38. Перепишите программы подсчета слов (см. раздел 11.1) и преобразования слов (см. раздел 11.3.6) так, чтобы использовать контейнер unordered_map.

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

Существует восемь ассоциативных контейнеров со следующими свойствами.

• Карта хранит пары ключ-значение; набор хранит только ключи.

• Есть контейнеры с уникальными ключами и с не уникальными.

• Ключи могут храниться упорядоченными или нет.

Упорядоченные контейнеры используют функцию сравнения для упорядочивания элементов по ключу. По умолчанию для сравнения используется оператор <типа ключа. Неупорядоченные контейнеры используют для организации своих элементов оператор ==типа ключа и объект типа hash.

Имена контейнеров с не уникальными ключами включают слово multi; а имена контейнеров, использующих хеширование, начинаются словом unordered. Контейнер set— это упорядоченная коллекция, каждый ключ которой уникален; контейнер unordered_multiset— это неупорядоченная коллекция, ключи которой могут повторяться.

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

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

Ассоциативный контейнер(associative container). Тип, содержащий коллекцию объектов и обеспечивающий эффективный поиск по ключу.

Ассоциативный массив(associative array). Массив, элементы которого проиндексированы по ключу, а не по позиции. Таким образом, массив сопоставляет (ассоциирует) ключ со значением.

Контейнер map(карта). Ассоциативный контейнер, аналогичный ассоциативному массиву. Подобно типу vector, тип mapявляется шаблоном класса. Но при создании карты необходимо указать два типа: тип ключа и тип связанного с ним значения. В контейнере mapключи уникальны, они не повторяются. Каждый ключ связан с определенным значением. Обращение к значению итератора карты возвращает объект типа pair, который содержит константный ключ и связанное (ассоциированное) с ним значение.

Контейнер multimap. Ассоциативный контейнер, подобный контейнеру map, но способный содержать одинаковые ключи.

Контейнер multiset. Ассоциативный контейнер, который содержит только ключи. В отличие от набора, способен содержать одинаковые ключи.

Контейнер set(набор). Ассоциативный контейнер, который содержит только ключи. Ключи в контейнере setне могут совпадать.

Контейнер unordered_map. Контейнер, элементы которого являются парами ключ-значение. Допустим только один элемент на ключ.

Контейнер unordered_multimap. Контейнер, элементы которого являются парами ключ-значение. Допустимо несколько элементов на ключ.

Контейнер unordered_multiset. Контейнер, хранящий ключи. Допустимо несколько элементов на ключ.

Контейнер unordered_set. Контейнер, хранящий ключи. Допустим только один элемент на ключ.

Неупорядоченный контейнер(unordered container). Ассоциативные контейнеры, использующие хеширование, а не сравнение ключей для хранения и доступа к элементам. Эффективность этих контейнеров зависит от качества хеш-функции.

Оператор *. Оператор обращения к значению, примененный к итератору контейнера map, set, multimapили multiset, возвращает объект типа value_type. Обратите внимание на то, что типом value_typeконтейнера mapи multimapявляется пара (pair).

Оператор []. Оператор индексирования, примененный к контейнеру map, получает индекс, типом которого должен быть key_type(или тип, допускающий преобразование в него). Возвращает значение типа mapped_type.

Строгое сравнение(strict weak ordering). Отношения между ключами ассоциативного контейнера. При строгом сравнении можно сравнить два любых значения и выяснить, которое из них меньше. Если ни одно из значений не меньше другого, они считаются равными.