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

// подсчет слов, но слова не в алфавитном порядке

unordered_map<string, size_t> word_count;

string word;

while (cin >> word)

 ++word_count[word]; // получить и прирастить счетчик слов

for (const auto &w : word_count) // для каждого элемента карты

 // отобразить результаты

 cout << w.first << " occurs " << w.second

      << ((w.second >1) ? " times" : " time") << endl; 

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

containers occurs 1 time

use occurs 1 time

can occurs 1 time

examples occurs 1 time

...

Но вывод вряд ли будет в алфавитном порядке.

Управление ячейками

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

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

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

Таблица 11.8. Функции управления неупорядоченным контейнером

Взаимодействие с ячейками с.bucket_count() Количество используемых ячеек c.max_bucket_count() Наибольшее количество ячеек, которое может содержать данный контейнер c.bucket_size(n) Количество элементов в ячейке n c.bucket(k) Ячейка, в которой следует искать элементы с ключом k Перебор ячеек local_iterator Тип итератора, способный обращаться к элементам в ячейке const_local_iterator Константная версия итератора ячейки c.begin(n), c.end(n) Итераторы на первый и следующий после последнего элементы ячейки n c.cbegin(n), c.cend(n) Возвращают итератор const_local_iterator Политика хеша c.load_factor() Среднее количество элементов на ячейку. Возвращает тип float c.max_load_factor() Средний размер ячейки, который пытается поддерживать контейнер c. Контейнер с добавляет ячейки, чтобы сохранить соотношение load_factor <= max_load_factor. Возвращает тип float c.rehash(n) Реорганизует хранилище так, чтобы bucket_count >= n и bucket_count > size/max_load_factor c.reserve(n) Реорганизует контейнер c так, чтобы он мог содержать n элементов без вызова функции rehash() Требования к типу ключа неупорядоченных контейнеров

По умолчанию для сравнения элементов неупорядоченные контейнеры используют оператор == типа ключа. Они также используют объект типа hash<key_type> при создании хеш-кода для каждого элемента. Библиотека поставляет также версии шаблона хеша для встроенных типов, включая указатели. Она определяет также шаблон hash для некоторых из библиотечных типов, включая строки и интеллектуальные указатели, которые рассматривались в главе 12. Таким образом, можно непосредственно создать неупорядоченный контейнер, ключ которого имеет один из встроенных типов (включающий типы указателей) либо тип string или интеллектуального указателя.

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

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

size_t hasher(const Sales_data &sd) {

 return hash<string>()(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<Sales_data,

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

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

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

SD_multiset bookstore(42, hasher, eqOp);

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

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

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

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

unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);

Упражнения раздела 11.4

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

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

Резюме

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

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

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

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

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

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

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