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

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

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

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

Однако нельзя непосредственно определить неупорядоченный контейнер, использующий для ключа собственные типы классов. В отличие от контейнеров, шаблон хеша нельзя использовать непосредственно. Вместо этого придется предоставить собственную версию шаблона 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. Каковы преимущества неупорядоченного контейнера по сравнению с упорядоченной версией этого контейнера? Каковы преимущества упорядоченной версии?