11.2.2. Требования к типу ключа

Ассоциативные контейнеры налагают ограничения на тип ключа. Требования для ключей неупорядоченных контейнеров рассматриваются в разделе 11.4. У упорядоченных контейнеров (map, multimap, set и multiset) тип ключа должен определять способ сравнения элементов. По умолчанию для сравнения ключей библиотека использует оператор < типа ключа. В наборах тип ключа соответствует типу элемента; в картах тип ключа — тип первого элемента пары. Таким образом, типом ключа карты word_count (см. раздел 11.1) будет string. Аналогично типом ключа набора exclude также будет string.

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

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

• Два ключа не могут быть "меньше" друг друга; если ключ k1 "меньше", чем k2, то k2 никогда не должен быть "меньше", чем k1.

• Если ключ k1 "меньше", чем k2, и ключ k2 "меньше", чем k3, то ключ k1 должен быть "меньше", чем k3.

• Если есть два ключа и ни один из них не "меньше" другого, то эти ключи "эквивалентны". Если ключ k1 "эквивалентен" ключу k2 и ключ k2 "эквивалентен" ключу k3, то ключ k1 должен быть "эквивалентен" ключу k3.

Если два ключа эквивалентны (т.е. если ни один не "меньше" другого), то контейнер рассматривает их как равные. С этими ключами в карте будет ассоциирован только один элемент, и любой из них предоставит доступ к тому же значению.

Использование функции сравнения для типа ключа

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

Каждый тип в угловых скобках — это только тип. Специальный оператор сравнения (тип которого должен совпадать с типом, указанным в угловых скобках) предоставляется как аргумент конструктора при создании контейнера.

Например, невозможно непосредственно определить контейнер multiset объектов класса Sales_data, поскольку класс Sales_data не имеет оператора <. Но для этого можно использовать функцию compareIsbn() из упражнений раздела 10.3.1. Эта функция обеспечивает строгое сравнение на основании ISBN двух объектов класса Sales_data. Функция compareIsbn() должна выглядеть примерно так:

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

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

}

Чтобы использовать собственный оператор, следует определить контейнер multiset с двумя типами: типом ключа Sales_data и типом сравнения, являющимся типом указателя на функцию (см. раздел 6.7), способным указывать на функцию compareIsbn(). Когда определяют объекты этого типа, предоставляют указатель на функцию, которую предстоит использовать. В данном случае предоставляется указатель на функцию compareIsbn():

// в программе может быть несколько транзакций с тем же ISBN

// элементы bookstore упорядочены по ISBN

multiset<Sales_data, decltype(compareIsbn)*>

 bookstore(compareIsbn);

Здесь для определения типа оператора используется спецификатор decltype. При использовании спецификатора decltype для получения указателя на функцию следует добавить символ * для обозначения использования указателя на заданный тип функции (см. раздел 6.7). Инициализацию bookstore осуществляет функция compareIsbn(). Это означает, что при добавлении элементов в bookstore они будут упорядочены при вызове функции compareIsbn(). Таким образом, элементы bookstore будут упорядочены по их члену ISBN. Аргумент конструктора можно записать как compareIsbn, вместо &compareIsbn, поскольку при использовании имени функции оно автоматически преобразуется в указатель, если это нужно (см. раздел 6.7). С тем же результатом можно написать &compareIsbn.

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

Упражнение 11.9. Определите карту, которая ассоциирует слова со списком номеров строк, в которых оно встречается.

Упражнение 11.10. Можно ли определить карту для типов vector<int>::iterator и int? А для типов list<int>::iterator и int? Если нет, то почему?

Упражнение 11.11. Переопределите bookstore, не используя спецификатор decltype.