11.4. Неупорядоченные контейнеры

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

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

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

Использование неупорядоченного контейнера

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

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

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

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

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. Функции управления неупорядоченным контейнером

Требования к типу ключа неупорядоченных контейнеров

По умолчанию для сравнения элементов неупорядоченные контейнеры используют оператор == типа ключа. Они также используют объект типа 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.