Язык программирования C Пятое издание

• Название: Язык программирования C Пятое издание
• Дата: 15.07.2019
• Размер: 1.85 Mb.
• Имя файла: 620354-www.libfox.ru.pdf
• Тип: Документы; #84130
• страница: 30 из 54

Упражнение 11.5. Объясните различие между картой и набором. Когда имеет смысл использовать один, а когда другой?
Упражнение 11.6. Объясните различия между набором и списком. Когда имеет смысл использовать один, а когда другой?
Упражнение 11.7. Определите карту, ключ которой является фамилией семьи, а значение —
вектором имен детей. Напишите код, способный добавлять новые семьи и новых детей в существующие семьи.
Упражнение 11.8. Напишите программу, которая хранит исключенные слова в векторе, а не в наборе. Каковы преимущества использования набора?
11.2.2. Требования к типу ключа
Page 532/1103

Ассоциативные контейнеры налагают ограничения на тип ключа. Требования для ключей неупорядоченных контейнеров рассматриваются в разделе 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() должна выглядеть примерно так:
Page 533/1103

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; // содержит две строки
Page 534/1103

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):
Page 535/1103

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, вектором пар, содержащих имя ребенка и день его рождения.
11.3. Работа с ассоциативными контейнерами
В дополнение к типам, перечисленным в табл. 9.2 (стр. 423), ассоциативные контейнеры определяют типы, перечисленные в табл. 11.3. Они представляют типы ключа и значения контейнера.
Page 536/1103

Таблица 11.3. Псевдонимы дополнительных типов ассоциативных контейнеров key_type Тип ключа контейнера mapped_type Тип, ассоциированный с каждым ключом; только для типа map value_type Для наборов то же, что и key_type. Для карт — pair<const key_type, mapped type>
Для контейнеров типа set типы key_type и value_type совпадают; содержащиеся в наборе данные являются ключами. Элементами карты являются пары ключ-значение. Таким образом, каждый ее элемент — объект класса pair, содержащий ключ и связанное с ним значение. Поскольку ключ элемента изменить нельзя, ключевая часть этих пар константна: set<string>::value_type v1; // v1 - string set<string>::key_type v2; // v2 - string map<string, int>::value_type v3; // v3 - pair<const string, int> map<string, int>::key_type v4; // v4 - string map<string, int>::mapped_type v5; // v5 - int
Подобно последовательным контейнерам (см. раздел 9.2.2), для доступа к члену класса,
например типа map<string, int>::key_type, используется оператор области видимости.
Тип mapped_type определен только для типов карт (unordered_map, unordered_multimap,
multimap и map).
11.3.1. Итераторы ассоциативных контейнеров
При обращении к значению итератора возвращается ссылка на значение типа value_type контейнера. В случае карты типом value_type является пара, переменная-член first которой содержит константный ключ, а переменная-член second — значение:
// получить итератор на элемент контейнера word_count auto map_it = word_count.begin();
//
*map_it - ссылка на объект типа pair<const string, size_t> cout << map_it->first; //
Page 537/1103

отобразить ключ элемента cout << " " << map_it->second; // отобразить значение элемента map_it->first = "new key"; // ошибка: ключ является константой
++map_it->second; // ok: значение можно изменить, используя итератор
Не следует забывать, что типом value_type карты является pair и что можно изменять ее значение, но не ключ. Итераторы наборов константны
Хотя типы наборов определяют типы iterator и const_iterator, оба типа итераторов предоставляют доступ к элементам в наборе только для чтения. Подобно тому, как нельзя изменить ключевую часть элемента карты, ключи в наборе также константны. Итератор набора можно использовать только для чтения, но не для записи значения элемента: set<int> iset = {0,1,2,3,4,5,6,7,8,9}; set<int>::iterator set_it = iset.begin(); if (set_it != iset.end()) {
*set_it = 42; // ошибка: ключи набора только для чтения cout << *set_it << endl; // ok: позволяет читать ключ
} Перебор ассоциативного контейнера
Типы map и set поддерживают все функции begin() и end() из табл. 9.2. Как обычно, эти функции можно использовать для получения итераторов, позволяющих перебрать контейнер.
Например, цикл вывода результатов программы подсчета слов из раздела 11.1 можно переписать следующим образом:
// получить итератор на первый элемент auto map_it = word_count.cbegin();
// сравнить текущий итератор с итератором после конца while (map_it != word_count.cend()) {
// обратиться к значению итератора, чтобы отобразить
Page 538/1103

// пару ключ-значение элемента cout << map_it->first << " occurs "
<< map_it->second << " times" << endl;
++map_it; // прирастить итератор, чтобы перейти на следующий элемент
}
Условие цикла while и инкремент итератора в теле цикла такие же как в программах вывода содержимого векторов или строк. Итератор map_it инициализирован позицией первого элемента контейнера word_count. Пока итератор не равен значению, возвращенному функцией end(), возвращается текущий элемент, а затем происходит приращение итератора.
Оператор вывода обращается к значению итератора map_it для получения членов пары,
оставаясь в остальном тем же, что и в первоначальной программе.
Вывод этой программы имеет алфавитный порядок. При использовании итераторов для перебора контейнеров map, multimap, set и multiset они возвращают элементы в порядке возрастания ключа. Ассоциативные контейнеры и алгоритмы
Как правило, с ассоциативными контейнерами обобщенные алгоритмы (см. главу 10) не используются. Тот факт, что ключи константны, означает невозможность передачи итераторов ассоциативных контейнеров алгоритмам, которые пишут или переупорядочивают элементы контейнеров. Таким алгоритмам нужна возможность записи в элементы. Элементы всех типов наборов константны, а у всех типов карт константным является первый член пары.
Ассоциативные контейнеры применимы с теми алгоритмами, которые только читают элементы. Однако большинство этих алгоритмов осуществляет поиск в последовательности.
Поскольку поиск элементов в ассоциативном контейнере осуществляется быстро (по ключу),
как правило, не имеет смысла использовать для них обобщенный алгоритм поиска.
Например, как будет продемонстрировано в разделе 11.3.5, ассоциативные контейнеры определяют функцию-член find(), позволяющую непосредственно выбрать элемент с заданным ключом. Для поиска элемента можно использовать обобщенный алгоритм find(), но он осуществляет последовательный поиск. Поэтому намного быстрее использовать функцию-член find() класса контейнера, чем вызывать обобщенную версию.
На практике, если это вообще происходит, ассоциативный контейнер используется с алгоритмами в качестве исходной последовательности или последовательности назначения.
Например, обобщенный алгоритм copy() можно использовать для копирования элементов ассоциативного контейнера в другую последовательность. Точно так же адаптер inserter можно использовать для связи итератора вставки (см. раздел 10.4.1) с ассоциативным контейнером. Адаптер inserter позволяет использовать ассоциативный контейнер как место назначения для другого алгоритма. Упражнения раздела 11.3.1
Упражнение 11.15. Каковы типы mapped_type, key_type и value_type карты,

переменные-члены пар которой имеют типы int и vector<int>?
Упражнение 11.16. Используя итератор карты, напишите выражение, присваивающее значение элементу.
Упражнение 11.17. С учетом того, что с — контейнер multiset строк, a v — вектор строк,
Page 539/1103

объясните следующие вызовы. Укажите, допустим ли каждый из них: copy(v.begin(), v.end(), inserter(с, c.end())); copy(v.begin(), v.end(), back inserter(c)); copy(c.begin(), c.end(), inserter(v, v.end())); copy(c.begin(), c.end(), back inserter(v));
Упражнение 11.18. Перепишите определение типа map_it из цикла в данном разделы, не используя ключевое слово auto или decltype.
Упражнение 11.19. Определите переменную, инициализированную вызовом функции begin()
контейнера multiset по имени bookstore из раздела 11.2.2. Определите тип переменной, не используя ключевое слово auto или decltype.
11.3.2. Добавление элементов
Функция-член insert() (табл. 11.4) добавляет один элемент или диапазон элементов в контейнер. Поскольку карта и набор (и их неупорядоченные версии) содержат уникальные ключи, попытка вставки уже присутствующего элемента не имеет никакого эффекта: vector<int> ivec = {2,4,6,8,2,4,6,8}; // ivec содержит
// восемь элементов set<int> set2; // пустой набор set2.insert(ivec.cbegin(), ivec.cend()); // set2 имеет четыре элемента set2.insert({1,3,5,7,1,3,5,7}); // теперь set2 имеет восемь элементов
Таблица 11.4. Функция insert() ассоциативного контейнера с.insert(v) с.emplace( args ) v — объект типа value_type; аргументы args используются при создании элемента. Элементы карты и набора вставляются (или создаются), только если элемента с данным ключом еще нет в контейнере с. Возвращает пару, содержащую итератор на элемент с заданным ключом и логическое значение,
указывающее, был ли вставлен элемент. У контейнеров multimap и multiset осуществляется вставка (или создание) заданного элемента и возвращение итератора на новый элемент с.insert(b, e) с.insert(il) Итераторы b и е обозначают диапазон значений типа с::value_type; il —
Page 540/1103

заключенный в скобки список таких значений. Возвращает void. У карты и набора вставляются элементы с ключами, которых еще нет в контейнере с. У контейнеров multimap и multiset вставляются все элементы диапазона c.insert(p, v) с.emplace(p, args ) Подобны функциям insert(v) и emplace( args ), но используют итератор p как подсказку для начала поиска места хранения нового элемента. Возвращает итератор на элемент с заданным ключом
Версии функции insert(), получающие пару итераторов или список инициализации, работают подобно соответствующим конструкторам (см. раздел 11.2.1), но добавляется только первый элемент с заданным ключом. Добавление элементов в карту
При вставке в карту следует помнить, что типом элемента является pair. Зачастую объекта pair, подлежащего вставке, нет. В этом случае пара создается в списке аргументов функции insert():
// четыре способа добавления слова в word_count word_count.insert({word, 1}); word_count.insert(make_pair(word, 1)); word_count.insert(pair<string, size_t>(word, 1)); word_count.insert(map<string, size_t>::value_type(word, 1));
Как уже упоминалось, по новому стандарту простейшим способом создания пары является инициализация списком аргументов в фигурных скобках. В качестве альтернативы можно вызвать функцию make_pair() или явно создать пару. Вот аргументы последнего вызова функции insert(): map<string, size_t>::value_type(s, 1)
Он создает новый объект пары соответствующего типа для вставки в карту. Проверка значения, возвращаемого функцией insert()
Значение, возвращенное функцией insert() (или emplace()), зависит от типа контейнера и параметров. Для контейнеров с уникальными ключами есть версии функций insert() и emplace(), которые добавляют один элемент и возвращают пару, сообщающую об успехе вставки. Первая переменная-член пары — итератор на элемент с заданным ключом; второй
— логическое значение, указывающее на успех вставки элемента. Если такой ключ уже был в контейнере, то функция insert() не делает ничего, а логическая часть возвращаемого значения содержит false. Если такой ключ отсутствовал, то логическая часть содержит значение true.
Для примера перепишем программу подсчета слов с использованием функции insert():
// более корректный способ подсчета слов во вводе map<string, size_t> word_count; // пустая карта строк и чисел
Page 541/1103

string word; while (cin >> word) {
// вставляет элемент с ключом, равным слову, и значением 1;
// если слово уже есть в word_count, insert() не делает ничего auto ret = word_count.insert({word, 1}); if (!ret.second) // слово уже было в word_count
++ret.first->second; // приращение счетчика
}
Для каждой строки word осуществляется попытка вставки со значением 1. Если слово уже находится в карте, ничего не происходит. В частности, связанный со словом счетчик остается неизменным. Если слова еще нет в карте, оно добавляется, а значение его счетчика устанавливается в 1.
Оператор if проверяет логическую часть возвращаемого значения. Если это значение false, то вставка не произошла. Следовательно, слово уже было в карте word_count, поэтому следует увеличить значение связанного с ним счетчика. Еще раз о синтаксисе
Оператор приращения счетчика в этой версии программы подсчета слов трудно понять.
Разобрать это выражение будет существенно проще, если сначала расставить скобки в соответствии с приоритетом (см. раздел 4.1.2) операторов:
++((ret.first)->second); // эквивалентное выражение
Рассмотрим это выражение поэтапно.
• ret — пара, содержащая значение, возвращаемое функцией insert().
• ret.first — первая переменная-член пары, на которую указывает итератор карты, с данным ключом.
• ret.first-> — обращение к значению итератора, позволяющее получить этот элемент.
Элементы карты также являются парами.
• ret.first->second — та часть пары элемента карты, которая является значением.
• ++ret.first->second — инкремент этого значения.
Таким образом, оператор инкремента получает итератор для элемента с ключом слова и увеличивает счетчик, связанный с ключом, для которого не удалась попытка вставки.
Для читателей, использующих устаревший компилятор или код, предшествующий новому
Page 542/1103

стандарту, объявление и инициализация пары ret также не совсем очевидны: pair<map<string, size_t>::iterator, bool> ret = word_count.insert(make_pair(word, 1));
Здесь определяется пара, вторая переменная-член которой имеет тип bool. Понять тип первой переменной-члена этой пары немного труднее. Это тип итератора, определенный типом map<string, size_t>. Добавление элементов в контейнеры multiset и multimap
Работа программы подсчета слов зависит от того факта, что каждый ключ может присутствовать только однажды. Таким образом, с любым словом будет связан только один счетчик. Но иногда необходима возможность добавить дополнительные элементы с тем же ключом. Например, могло бы понадобиться сопоставить авторов с названиями написанных ими книг. В данном случае для каждого автора могло бы быть несколько записей, поэтому будет использован контейнер multimap, а не map. Поскольку ключи контейнеров multi не должны быть уникальным, функция insert() для них всегда вставляет элемент: multimap<string, string> authors;
// добавляет первый элемент с ключом Barth, John authors.insert({"Barth, John", "Sot-Weed Factor"});
// ok: добавляет второй элемент с ключом Barth, John authors.insert({"Barth, John", "Lost in the Funhouse"});
У контейнеров, допускающих совпадение ключей, функция insert() получает один элемент и возвращает итератор на новый элемент. Нет никакой необходимости возвращать логическое значение, поскольку в эти контейнеры функция insert() всегда добавляет новый элемент.
Упражнения раздела 11.3.2
Упражнение 11.20. Перепишите программу подсчета слов из раздела 11.1 так, чтобы использовать функцию insert() вместо индексации. Какая версия программы по-вашему проще? Объясните почему.
Упражнение 11.21. С учетом того, что word_count является картой типов string и size_t, а также того, что word имеет тип string, объясните следующий цикл: while (cin >> word)
++word_count.insert({word, 0}).first->second;
Упражнение 11.22. С учетом, что map<string, vector<int>>, напишите типы,
используемые как аргументы, и возвращаемое значение версии функции insert(),
вставляющей один элемент.
Упражнение 11.23. Перепишите карту, хранящую вектора имен детей с ключом в виде фамилии семьи из упражнений раздела 11.2.1, так, чтобы использовался контейнер multimap.
11.3.3. Удаление элементов
Page 543/1103

Ассоциативные контейнеры определяют три версии функции erase(), описанные в табл. 11.5.
Подобно последовательным контейнерам, можно удалить один элемент или диапазон элементов, передав функции erase() итератор или пару итераторов. Эти версии функции erase() подобны соответствующим функциям последовательных контейнеров: указанный элемент (элементы) удаляется и возвращается тип void.
Таблица 11.5. Удаление элементов ассоциативного контейнера c.erase(k) Удаляет из карты с элемент с ключом k. Возвращает значение типа size_type, указывающее количество удаленных элементов c.erase(p) Удаляет из карты с элемент, обозначенный итератором p.
Итератор p должен относиться к фактически существующему элементу карты с, он не может быть равен итератору, возвращаемому функцией c.end(). Возвращает итератор на элемент после позиции p или c.end(), если итератор p обозначает последний элемент контейнера с c.erase(b, е) Удаляет элементы в диапазоне, обозначенном парой итераторов b и е.
Возвращает итератор е
Ассоциативные контейнеры предоставляют дополнительную версию функции erase(),
получающую аргумент типа key_type. Эта версия удаляет все элементы, если таковые вообще имеются, с заданным ключом и возвращает количество удаленных элементов. Эту версию можно использовать для удаления определенных слов из контейнера word_count прежде, чем вывести результат:
// удалить по ключу, возвратить количество удаленных элементов if (word_count.erase(removal_word)) cout << "ok: " << removal_word << " removed\n"; else cout << "oops: " << removal_word << " not found!\n";
Для контейнеров с уникальными ключами функция erase() всегда возвращает нуль или единицу. Если возвращается значение нуль, значит, удаляемого элемента не было в контейнере.
Для контейнеров с не уникальными ключами функция erase() возвращает количество удаленных элементов и может быть больше единицы: auto cnt = authors.erase("Barth, John");
Если authors — это контейнер multimap, созданный в разделе 11.3.2, то переменная cnt будет содержать значение 2.
11.3.4. Индексация карт
Контейнеры map и unordered_map предоставляют оператор индексирования и соответствующую функцию at() (см. раздел 9.3.2), представленные в табл. 11.6. Типы
Page 544/1103

контейнеров set не поддерживают индексацию, поскольку в наборе нет никакого "значения",
связанного с ключом. Элементы сами являются ключами, поэтому операция "доступа к значению, связанному с ключом", бессмысленна. Нельзя индексировать контейнер multimap или unordered_multimap, поскольку с заданным ключом может быть ассоциировано несколько значений.
Таблица 11.6. Операторы индексирования контейнеров map и unordered_map c[k] Возвращает элемент с ключом k; если ключа k нет в контейнере с, добавляется новый элемент,
инициализированный значением с ключом k c.at(k) Проверяет наличие элемента с ключом k;
если его нет в контейнере с, передает исключение out_of_range (см. раздел 5.6)
Подобно другим использованным ранее операторам индексирования, оператор индексирования карт получает индекс (т.е. ключ) и возвращает связанное с ним значение.
Однако, в отличие от других операторов индексирования, если такого ключа еще нет, создается новый элемент и добавляется в карту для того ключа. Ассоциированное значение инициализируется значением по умолчанию (см. раздел 3.3.1).
Рассмотрим следующий код: map <string, size_t> word_count; // пустая карта
// вставить инициализированный значением по умолчанию элемент
// с ключом Anna; а затем установить для него значение 1 word_count["Anna"] = 1;
Ниже приведена имеющая место последовательность действий.
• В контейнере word_count происходит поиск элемента с ключом Anna. Элемент не найден.
• В контейнер word_count добавляется новая пара ключ-значение. Ключ (константная строка)
содержит текст Anna. Значение инициализируется по умолчанию, в данном случае нулем.
• Вновь созданному элементу присваивается значение 1.
Поскольку оператор индексирования способен вставить элемент, его можно использовать только для карты, которая не является константной.
Индексация карт существенно отличается от индексации массивов или векторов:
использование отсутствующего ключа приводит к добавлению элемента с таким ключом в карту.Использование значения, возвращенного оператором индексирования
Иной способ индексирования карт, отличающий его от других использованных ранее операторов индексирования, влияет на тип возвращаемого значения. Обычно тип,
возвращенный в результате обращения к значению итератора, и тип, возвращенный оператором индексирования, совпадают. У карт все не так: при индексировании
Page 545/1103

возвращается объект типа mapped_type, а при обращении к значению итератора карты —
объект типа value_type (см. раздел 11.3).
Общим у всех операторов индексирования является то, что они возвращают l-значение (см.
раздел 4.1.1). Поскольку возвращается l-значение, возможно чтение и запись в элемент: cout << word_count["Anna"]; // получить элемент по индексу Anna;
// выводит 1
++word_count["Anna"]; // получить элемент и добавить к нему 1 cout << word_count["Anna"]; // получить элемент и вывести его;
// выводит 2
В отличие от вектора или строки, тип данных, возвращаемых оператором индексирования карты, отличается из типа, полученного при обращении к значению итератора карты.
Тот факт, что индексирование добавляет элемент, если карта его еще не содержит,
позволяет создавать удивительно сжатый код, такой как цикл в программе подсчета слов (см.
раздел 11.1). С другой стороны, иногда необходимо только узнать, присутствует ли элемент,
но не добавлять его в случае отсутствия. В таких случаях не следует использовать оператор индексирования.Упражнения раздела 11.3.4
Упражнение 11.24. Что делает следующая программа? map<int, int> m; m[0] = 1;
Упражнение 11.25. Сравните следующую программу с предыдущей: vector<int> v; v[0] = 1;
Упражнение 11.26. Какой тип применяется при индексировании карты? Какой тип возвращает оператор индексирования? Приведите конкретный пример, т.е. создайте карту, используйте типы, которые применимы для ее индексирования, а затем выявите типы, которые будет возвращать оператор индексирования.
11.3.5. Доступ к элементам
Page 546/1103

Ассоциативные контейнеры предоставляют различные способы поиска заданных элементов,
описанные в табл. 11.7. Используемый способ зависит от решаемой задачи. Если нужно лишь выяснить, находится ли некий элемент в контейнере, то, вероятно, лучше использовать функцию find(). Для контейнеров, способных содержать только уникальные ключи, вероятно,
не имеет значения, используется ли функция find() или count(). Но для контейнеров с не уникальными ключами функция count() выполняет больше работы: если элемент присутствует, ей все еще нужно подсчитать количество элементов с тем же ключом. Если знать количество не обязательно, лучше использовать функцию find(): set<int> iset = {0,1,2,3,4,5,6,7,8,9}; iset.find(1); // возвращает итератор на элемент с ключом == 1 iset.find(11); // возвращает итератор == iset.end() iset.count(1); // возвращает 1 iset.count(11); // возвращает 0
Таблица 11.7. Функции поиска элементов в ассоциативном контейнере Функции lower_bound()
и upper_bound() неприменимы для неупорядоченных контейнеров. Оператор индексирования и функция at() применимы только для тех контейнеров map и unordered_map, которые не являются константами. c.find(k) Возвращает итератор на (первый) элемент с ключом k или итератор после конца, если такого элемента нет в контейнере c.count(k) Возвращает количество элементов с ключом k. Для контейнеров с уникальными ключами результат всегда нуль или единица c.lower_bound(k) Возвращает итератор на первый элемент, значение ключа которого не меньше, чем k c.upper_bound(k) Возвращает итератор на первый элемент,
значение ключа которого больше, чем k c.equal_range(k) Возвращает пару итераторов,
обозначающих элементы с ключом k. Если такового элемента нет, значение обеих переменных-членов равно c.end() Использование функции find() вместо индексирования карт
Для контейнеров map и unordered_map оператор индексирования представляет простейший способ поиска значения. Но, как уже упоминалось, у оператора индексирование есть серьезный побочный эффект: если искомого ключа еще нет в карте, индексирование добавляет элемент с таким ключом. Насколько правильно такое поведение, зависит от обстоятельств. Программа подсчета слов полагалась на тот факт, что использование несуществующего ключа при индексировании приводило к вставке элемента с этим ключом и значением 0.
Иногда мы хотим знать, присутствует ли элемент с заданным ключом, не изменяя карту.
Нельзя использовать оператор индексирования для определения наличия элемента,
поскольку при его отсутствии оператор индексирования добавит новый элемент с таким ключом. В таких случаях следует использовать функцию find(): if (word_count.find("foobar") == word_count.end()) cout << "foobar is not in the map" << endl; Поиск элементов в контейнерах multimap и
Page 547/1103

multiset
Поиск элемента в ассоциативном контейнере с уникальными ключами довольно прост —
элемент либо есть в контейнере, либо нет. Для контейнеров с не уникальными ключами все несколько сложнее, так как может существовать несколько элементов с заданным ключом.
Когда в контейнере multimap или multiset содержится несколько элементов с одинаковым ключом, они располагаются в контейнере рядом.
Предположим, например, что, имея карту авторов и их книг, следует вывести все книги некоего автора. Эту задачу можно решить тремя способами. Самый очевидный из них —
использовать функции find() и count(): string search_item("Alain de Botton"); // искомый автор auto entries = authors.count(search_item); // количество записей auto iter = authors.find(search_item); // первая запись для этого
// автора
// перебор записей данного автора while (entries) { cout << iter->second << endl; // вывод каждого заглавия
++iter; // переход к следующему заглавию
--entries; // отследить количество выведенных записей
}
Код начинается с вызова функции count(), позволяющего выяснить количество записей для данного автора, и вызова функции find(), позволяющего получить итератор на первый элемент с этим ключом. Количество итераций цикла for зависит от числа, возвращенного функцией count(). В частности, если функция count() возвратит нуль, то цикл не выполнится вообще.
Гарантируется, что перебор контейнера multimap или multiset возвратит все элементы с заданным ключом. Другое решение на основании итератора
Задачу можно решить иначе, используя функции lower_bound() и upper_bound(). Каждая из
Page 548/1103

них получает ключ и возвращает итератор. Если ключ найден в контейнере, функция lower_bound() возвратит итератор на первый экземпляр элемента с этим ключом, а итератор,
возвращенный функцией upper_bound(), указывает на следующий элемент после последнего экземпляра с заданным ключом. Если таковой элемент в контейнере multimap отсутствует, то функции lower_bound() и upper_bound() возвратят одинаковые итераторы на позицию, в которой мог бы находиться такой ключ согласно принятому порядку. Таким образом, вызов функций lower_bound() и upper_bound() для того же ключа возвращает диапазон итераторов
(см. раздел 9.2.1), обозначающий все элементы с тем же ключом.
Безусловно, возвращенный этими функциями итератор может указывать на элемент непосредственно после конца контейнера. Если искомый элемент имеет самый большой ключ в контейнере, вызов функции upper_bound() возвратит итератор на элемент после последнего элемента контейнера. Если элемент отсутствует и ключ является самым большим в контейнере, то вызов функции lower_bound() также возвратит итератор на элемент после последнего элемента контейнера.
Итератор, возвращенный функцией lower_bound(), может указывать, а может и не указывать на элемент с заданным ключом. Если такового элемента в контейнере нет, функция lower_bound() возвращает итератор на первую позицию, в которую, согласно порядку расположения элементов, мог бы быть вставлен элемент с данным ключом.
Используя эти функции, можно переписать программу следующим образом:
// определения authors и search_item как прежде
// итераторы beg и end обозначают диапазон элементов данного автора for (auto beg = authors.lower_bound(search_item), end = authors.upper_bound(search_item); beg != end; ++beg) cout << beg->second << endl; // вывод каждого заглавия
Эта программа делает то же, что и предыдущая, использовавшая функции count() и find(), но более непосредственно. Вызов функции lower_bound() устанавливает итератор beg так,
чтобы он указывал на первый элемент, соответствующий search_item, если он есть. Если его нет, то итератор beg укажет на первый элемент с ключом, большим, чем search_item, который может оказаться итератором после конца. Вызов функции upper_bound() присвоит итератору end позицию элемента непосредственно после последнего элемента с заданным ключом. Эти функции ничего не говорят о том, присутствует ли данный ключ в контейнере. Важный момент заключается в том, что возвращаемые значения формируют диапазон итераторов (см. раздел
9.2.1).
Если элемента с искомым ключом нет, то возвращаемые функциями lower_bound() и upper_bound() значения будут равны. Оба, по сути, укажут позицию вставки элемента с указанным ключом при сохранении текущего порядка элементов контейнера.
Если элементы с заданным ключом есть, то итератор beg укажет на первый такой элемент.
Приращение итератора beg позволит перебрать элементы с этим ключом. Равенство
Page 549/1103

итератора beg итератору end свидетельствует о завершении перебора всех элементов с этим ключом.
Поскольку эти итераторы формируют диапазон, для его перебора можно использовать цикл for. Цикл выполняется нуль или большее количество раз, выводя записи для данного автора,
если таковые вообще имеются. Если таких элементов нет, то итераторы beg и end равны и цикл не выполняется ни разу. В противном случае инкремент итератора beg в процессе вывода каждой связанной с данным автором записи сравняет его в конечном счете с итератором end.
Если функции lower_bound() и upper_bound() возвращают тот же итератор, то заданного ключа в контейнере нет. Функция equal_range()
Последний способ решения этой задачи самый простой из всех: вместо функций upper_bound() и lower_bound() можно вызвать функцию equal_range().
Эта функция получает ключ и возвращает пару итераторов. Если элементы с таким ключом в контейнере присутствуют, то первый итератор укажет на первый экземпляр элемента, а второй — на следующий после последнего экземпляра. Если подходящего элемента нет, то первый и второй итераторы укажут позицию, в которую этот элемент может быть вставлен.
Функцию equal_range() можно использовать для еще одного изменения программы:
// определения authors и search_item, как прежде
// pos содержит итераторы, обозначающие диапазон элементов
// с заданным ключом for (auto pos = authors.equal_range(search_item); pos.first != pos.second; ++pos.first) cout << pos.first->second << endl; // вывод каждого заглавия
Эта программа очень похожа на предыдущую, где использовались функции upper_bound() и lower_bound(). Для хранения диапазона итераторов вместо локальных переменных beg и end используется пара, возвращенная функцией equal_range(). Переменная-член first этой пары содержит тот же итератор, который возвратила бы функция lower_bound(), а переменная-член second — итератор, который возвратила бы функция upper_bound(). Таким образом, в этой программе значение pos.first эквивалентно значению beg, a pos.second — значению end.
Упражнения раздела 11.3.5