10.3.1. Передача функций алгоритму

Предположим, например, что необходимо вывести вектор после вызова функции 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.3.1

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

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

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