Читать онлайн «Язык программирования C++. Пятое издание». Страница 131

Например, алгоритм sort() использует оператор < типа элемента. Но может понадобиться сортировать последовательность в порядке, отличном от определенного оператором <, либо у типа элемента последовательности может не быть оператора < (как у класса Sales_data). В обоих случаях необходимо переопределить стандартное поведение функции sort().

Предположим, например, что необходимо вывести вектор после вызова функции elimDups() (см. раздел 10.2.3). Однако слова должны быть упорядочены сначала по размеру, а затем в алфавитном порядке в пределах каждого размера. Чтобы переупорядочить вектор по длине слов, используем вторую перегруженную версию функции sort(). Она получает третий аргумент, называемый предикатом.

Предикат (predicate) — это допускающее вызов выражение, возвращающее значение, применимое в условии. Библиотечные алгоритмы используют унарные предикаты (unary predicate) (с одним параметром) или бинарные предикаты (binary predicate) (с двумя параметрами). Получающие предикаты алгоритмы вызывают его для каждого элемента в исходном диапазоне. Поэтому тип элемента должен допускать преобразование в тип параметра предиката.

Версия функции sort(), получающей бинарный предикат, использует его вместо оператора < при сравнении элементов. Предикаты, предоставляемые функции sort(), должны соответствовать требованиям, описанным в разделе 11.2.2, а пока достаточно знать, что он должен определить единообразный порядок для всех возможных элементов в исходной последовательности. Функция isShorter() из раздела 6.2.2 — хороший пример функции, соответствующей этим требованиям. Таким образом, функцию isShorter() можно передать как предикат алгоритму sort(). Это переупорядочит элементы по размеру:

// функция сравнения, используемая при сортировке слов по длине

bool isShorter(const string &s1, const string &s2) {

 return s1.size() < s2.size();

}

// сортировка слов по длине от коротких к длинным

sort(words.begin(), words.end(), isShorter);

Если контейнер words содержит те же данные, что и в разделе 10.2.3, то этот вызов переупорядочит его так, что все слова длиной 3 символа расположатся перед словами длиной 4 символа, которые в свою очередь расположатся перед словами длиной 5 символов, и т.д.

При сортировке вектора words по размеру следует также обеспечить алфавитный порядок элементов одинаковой длины. Для обеспечения алфавитного порядка можно использовать алгоритм stable_sort(), обеспечивающий первоначальный порядок сортировки среди равных элементов.

Обычно об относительном порядке равных элементов можно не заботиться. В конце концов, они ведь равны. Но в данном случае под "равными" подразумеваются элементы со значениями одинаковой длины. Элементы одинаковой длины все еще отличаются друг от друга при просмотре их содержимого. Вызов функции stable_sort() позволяет расположить элементы с одинаковыми значениями длины в алфавитном порядке:

elimDups(words); // расположить слова в алфавитном порядке

// и удалить дубликаты

// пересортировать по длине, поддерживая алфавитный порядок среди слов

// той же длины

stable_sort(words.begin(), words.end(), isShorter);

for (const auto &s : words) // копировать строки не нужно

 cout << s << " "; // вывести каждый элемент, отделяя его пробелом

cout << endl;

Предположим, что перед этим вызовом вектор words был отсортирован в алфавитном порядке. После вызова он будет отсортирован по размеру элемента, а слова одинаковой длины остаются в алфавитном порядке. Если выполнить этот код для первоначального содержимого вектора, то результат будет таким:

fox red the over slow jumps quick turtle

Упражнение 10.11. Напишите программу, использующую функции stable_sort() и isShorter() для сортировки вектора, переданного вашей версии функции elimDups(). Для проверки правильности программы выведите содержимое вектора.

Упражнение 10.12. Напишите функцию compareIsbn(), которая сравнивает члены isbn двух объектов класса Sales_data. Используйте эту функцию для сортировки вектора объектов класса Sales_data.

Упражнение 10.13. Библиотека определяет алгоритм partition(), получающий предикат и делящий контейнер так, чтобы значения, для которых предикат возвращает значение true, располагались в начале последовательности, а для которых он возвращает значение false — в конце. Алгоритм возвращает итератор на следующий элемент после последнего, для которого предикат возвратил значение true. Напишите функцию, которая получает строку и возвращает логическое значение, указывающее, содержит ли строка пять символов или больше. Используйте эту функцию для разделения вектора words. Выведите элементы, у которых есть пять или более символов.

У передаваемых алгоритмам предикатов должен быть точно один или два параметра, в зависимости от того, использует ли алгоритм унарный или бинарный предикат соответственно. Но иногда необходима обработка, которая требует большего количества аргументов, чем позволяет предикат алгоритма. Например, решение для последнего упражнения в предыдущем разделе имело жестко заданный размер в 5 символов, согласно которому предикат делил последовательность. Было бы удобней иметь возможность разделять последовательность без необходимости писать отдельный предикат для каждого возможного размера.

Для примера пересмотрим программу из раздела 10.3.1 так, чтобы вывести количество слов с указанным размером или больше него. Вывод изменим так, чтобы он сообщал только те слова, длина которых равна или больше заданной.

Вот "эскиз" этой функции, которую мы назовем biggies():

void biggies(vector<string> &words,

vector<string>::size_type sz) {

 elimDups(words); // расположить слова в алфавитном порядке

                  // и удалить дубликаты

 // пересортировать по длине, поддерживая алфавитный порядок среди слов

 // той же длины

 stable_sort(words.begin(), words.end(), isShorter);

 // получить итератор на первый элемент, размер которого >= sz

 // вычислить количество элементов с размером >= sz

 // вывести слова, размер которых равен или больше заданного, разделяя

 // их пробелами

}

Новая проблема — поиск первого элемента вектора заданного размера. Как известно, чтобы выяснить количество элементов, размер которых равен или больше заданного, можно использовать их позицию.

Для поиска элементов определенного размера можно использовать библиотечный алгоритм find_if(). Подобно функции find() (см. раздел 10.1), алгоритм find_if() получает два итератора, обозначающих диапазон. В отличие от функции find(), третий аргумент функции find_if() является предикатом. Алгоритм find_if() вызывает переданный предикат для каждого элемента в исходном диапазоне. Он возвращает первый элемент, для которого предикат возвращает отличное от нуля значение, или конечный итератор, если ни один подходящий элемент не найден.

Совсем не сложно написать функцию, которая получает строку и размер, а возвращает логическое значение, означающее, не превосходит ли размер данной строки указанный. Однако функция find_if() получает унарный предикат, поэтому любая передаваемая ей функция, которая может быть вызвана с элементом исходной последовательности, должна иметь только один параметр. Нет никакого способа передать ей второй аргумент, представляющий размер. Чтобы решить эту часть проблемы, используем некоторые дополнительные средства языка.

Алгоритму можно передать любой вид вызываемого объекта (callable object). Объект или выражение является вызываемым, если к нему можно применить оператор вызова (см. раздел 1.5.2). Таким образом, если е — вызываемое выражение, то можно написать е(аргументы), где аргументы — это разделяемый запятыми список любого количества аргументов.

Единственными вызываемыми объектами, использованными до сих пор, были функции и указатели на функции (см. раздел 6.7). Есть еще два вида вызываемых объектов: классы, перегружающие оператор вызова функции (будут рассматриваться в разделе 14.8), и лямбда-выражения (lambda expression).