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

Кроме функций, общих для всех контейнеров, ассоциативные контейнеры предоставляют некоторые функции (табл. 11.7) и псевдонимы типов (табл. 11.3), которых нет у последовательных контейнеров. Помимо этого, неупорядоченные контейнеры предоставляют функции настройки производительности их хеша, которые рассматриваются в разделе 11.4.

Итераторы ассоциативных контейнеров двунаправлены (см. раздел 10.5.1).

11.2.1. Определение ассоциативного контейнера

Как только что упоминалось, при определении карты следует указать типы ключа и значения; при определении набора задают только тип ключа, поскольку значения у него нет. Каждый из ассоциативных контейнеров имеет стандартный конструктор, который создает пустой контейнер заданного типа. Ассоциативный контейнер можно также инициализировать копией другого контейнера того же типа или диапазоном значений, тип которых может быть приведен к типу контейнера. По новому стандарту возможна также списочная инициализация элементов:

map<string, size_t> word_count; // пустая карта

// списочная инициализация 

set<string> exclude = {"the", "but", "and", "or", "an", "a",

                       "The", "But", "And", "Or", "An", "A"};

// три элемента; authors сопоставляет фамилию с именем

map<string, string> authors = { {"Joyce", "James"},

                                {"Austen", "Jane"},

                                {"Dickens", "Charles"} };

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

При инициализации карты следует предоставить и ключ, и значение. Каждая пара ключ-значение заключается в фигурные скобки, {ключ, значение}, означая, что вместе элементы формируют единый элемент карты. Первый элемент каждой пары — это ключ, второй — значение. Таким образом, карта authors сопоставляет фамилии с именами и инициализируется тремя элементами.

Инициализация контейнеров multimap и multiset

Ключи в контейнерах map и set должны быть уникальными; с каждым ключом может быть сопоставлен только один элемент. У контейнеров multimap и multiset такого ограничения нет; вполне допустимо несколько элементов с тем же ключом. Например, у использованной для подсчета слов карты должен быть только один элемент, содержащий некое слово. С другой стороны, у словаря может быть несколько определений того же слова.

Следующий пример иллюстрирует различия между контейнерами с уникальными ключами и таковыми с не уникальными ключами. Сначала необходимо создать вектор целых чисел ivec на 20 элементов: две копии каждого из целых чисел от 0 до 9 включительно. Этот вектор будет использован для инициализации контейнеров set и multiset:

// определить вектор из 20 элементов, содержащий две копии каждого

// числа от 0 до 9

vector<int> ivec;

for (vector<int>::size_type i = 0; i != 10; ++i) {

 ivec.push_back(i);

 ivec.push_back(i); // сдублировать каждое число

}

// iset содержит уникальные элементы ivec;

// miset содержит все 20 элементов

set<int> iset(ivec.cbegin(), ivec.cend());

multiset<int> miset(ivec.cbegin(), ivec.cend());

cout << ivec.size() << endl;  // выводит 20

cout << iset.size() << endl;  // выводит 10

cout << miset.size() << endl; // выводит 20

Хотя набор iset был инициализирован значениями всего контейнера ivec, он содержит только десять элементов: по одному для каждого уникального элемента вектора ivec. С другой стороны, контейнер miset содержит 20 элементов, сколько и вектор ivec.

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

Упражнение 11.5. Объясните различие между картой и набором. Когда имеет смысл использовать один, а когда другой?

Упражнение 11.6. Объясните различия между набором и списком. Когда имеет смысл использовать один, а когда другой?

Упражнение 11.7. Определите карту, ключ которой является фамилией семьи, а значение — вектором имен детей. Напишите код, способный добавлять новые семьи и новых детей в существующие семьи.

Упражнение 11.8. Напишите программу, которая хранит исключенные слова в векторе, а не в наборе. Каковы преимущества использования набора?

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

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

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

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

Подобно тому, как собственный оператор сравнения можно предоставить алгоритму (см. раздел 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.