11.2. Обзор ассоциативных контейнеров.

Ассоциативные контейнеры (и упорядоченные, и неупорядоченные) поддерживают общие функции контейнеров, описанные в разделе 9.2 и перечисленные в табл. 9.2. Ассоциативные контейнеры не поддерживают функции, специфические для последовательных контейнеров, такие как push_front() или back(). Поскольку элементы хранятся на основании их ключа, эти операции были бы бессмысленны для ассоциативных контейнеров. Кроме того, ассоциативные контейнеры не поддерживают конструкторы и функции вставки, получающие значение элемента и его позицию.

Кроме функций, общих для всех контейнеров, ассоциативные контейнеры предоставляют некоторые функции (табл. 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.

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

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

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

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

11.2.3. Тип pair.

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

Объект типа pair хранит две переменные-члена. Подобно контейнерам, тип pair является шаблоном, позволяющим создавать конкретные типы. При создании пары следует предоставить имена двух типов, которые будут типами ее двух переменных-членов. Совпадать эти типы вовсе не обязаны.

pair<string, string> anon;       // содержит две строки

pair<string, size_t> word_count; // содержит строку и целое число

pair<string, vector<int>> line;  // содержит строку и vector<int>

При создании объекта пары без указания инициализирующих значений используются стандартные конструкторы типов его переменных-членов. Таким образом, пара anon содержит две пустые строки, а пара line — пустую строку и пустой вектор целых чисел. Значением переменной-члена типа int в паре word_count будет 0, а его переменная-член типа string окажется инициализирована пустой строкой.

Можно также предоставить инициализаторы для каждого члена пары:

pair<string, string> author{"James", "Joyce"};

Этот код создает пару по имени author, инициализированную значениями "James" и "Joyce".

В отличие от других библиотечных типов, переменные-члены класса pair являются открытыми (см. раздел 7.2). Эти члены — first (первый) и second (второй) соответственно. К ним можно обращаться непосредственно, используя обычный точечный оператор (см. раздел 1.5.2), как, например, было сделано в операторе вывода программы подсчета слов в разделе 11.1:

// отобразить результаты

cout << w.first << " occurs " << w.second

     << ((w.second > 1) ? " times" : " time") << endl;

Где w — ссылка на элемент карты. Элементами карты являются пары. В данном операторе выводится переменная-член first элемента, являющаяся ключом, затем переменная-член second элемента, являющаяся счетчиком. Библиотека определяет весьма ограниченный набор операций с парами, который приведен в табл. 11.2.

Таблица 11.2. Операции с парами

pair<T1, T2> p;	p — пара с переменными-членами типов T1 и T2, инициализированными значением по умолчанию (см. раздел 3.3.1)
pair<T1, T2> р(v1, v2);	p — пара с переменными-членами типов T1 и T2, инициализированными значениями v1 и v2 соответственно
pair<T1, T2> р = {v1, v2};	Эквивалент p(v1, v2)
make_pair(v1, v2)	Возвращает пару, инициализированную значениями v1 и v2. Тип пары выводится из типов значений v1 и v2
p.first	Возвращает открытую переменную-член first пары p
p.second	Возвращает открытую переменную-член second пары p
p1 опсравн p2	Операторы сравнения ( <, >, <=, >=). Сравнение осуществляется подобно упорядочиванию в словаре, т.е. оператор < возвращает значение true в случае, если p1.first < p2.first или !(p2.first < p1.first) && p1.second < p2.second
p1 == p2, p1 != p2	Две пары равны, если их первый и второй члены соответственно равны. При сравнении используется оператор == хранимых элементов

Функция для создания объектов типа pair.

Предположим, некая функция должна возвратить значение типа pair. По новому стандарту возможна списочная инициализация возвращаемого значения (см. раздел 6.3.2):

pair<string, int>

process(vector<string> &v) {

 // обработка v

 if (!v.empty())

  return {v.back(), v.back().size()}; // списочная инициализация

 else

  return pair<string, int>(); // возвращаемое значение создано явно

}

Если вектор v не пуст, возвращается пара, состоящая из последней строки в векторе v и размера этой строки. В противном случае явно создается и возвращается пустая пара.

В прежних версиях языка С++ нельзя было использовать инициализаторы в скобках для возвращения типа, подобного pair. Вместо этого можно было написать оба оператора return как явно созданное возвращаемое значение:

if (!v.empty())

 return pair<string, int>(v.back(), v.back().size());

В качестве альтернативы можно использовать функцию make_pair() для создания новой пары соответствующего типа из двух аргументов:

if (!v.empty())

 return make_pair(v.back(), v.back().size());

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

Упражнение 11.12. Напишите программу, читающую последовательность строк и целых чисел, сохраняя каждую прочитанную пару в объекте класса pair. Сохраните пары в векторе.

Упражнение 11.13. Существует по крайней мере три способа создания пар в программе предыдущего упражнения. Напишите три версии программы, создающей пары каждым из этих способов. Укажите, какая из форм проще и почему.

Упражнение 11.14. Дополните карту фамилий семей и их детей, написанную для упражнения в разделе 11.2.1, вектором пар, содержащих имя ребенка и день его рождения.