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

Упражнение 10.10. Почему алгоритмы не изменяют размер контейнеров?

Большинство алгоритмов сравнивает элементы исходной последовательности. По умолчанию такие алгоритмы используют оператор <или ==типа элемента. Библиотека предоставляет также версии этих алгоритмов, позволяющие использовать собственный оператор вместо заданного по умолчанию.

Например, алгоритм 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 &words,

vector::size_type sz) {

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

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

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