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

Упражнение 11.33. Реализуйте собственную версию программы преобразования слов.

Упражнение 11.34. Что будет, если в функции transform()вместо функции find()использовать оператор индексирования ?

Упражнение 11.35. Что будет (если будет) при таком изменении функции buildMap():

trans_map[key] = value.substr(1);

as trans_map.insert({key, value.substr(1)})?

Упражнение 11.36. Текущая версия программы не проверяет допустимость входного файла. В частности, она подразумевает, что все правила в файле преобразований корректны. Что будет, если строка в этом файле содержит ключ, один пробел и больше ничего? Проверьте свой ответ на текущей версии программы.

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

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

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

Кроме функций управления хешированием, неупорядоченные контейнеры предоставляют те же функции ( find(), insert()и т.д.), что и упорядоченные контейнеры. Это значит, что функции, использовавшиеся для контейнеров mapи set, применимы также к контейнерам unordered_mapи unordered_set. Аналогично неупорядоченные контейнеры имеют версии с не уникальными ключами.

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

Например, первоначальную программу подсчета слов из раздела 11.1 можно переписать так, чтобы использовать контейнер unordered_map:

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

unordered_map 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

...

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

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

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