Описанный код работает с числами. Параметризуем типы (Листинг 32):
Листинг 32. Параметризация типов для сортировки пузырькомtemplate <typename Data> // (1)
void sort_bubble(Data* data, size_t size) // (2)
{
for (size_t i = 0; i < size 1; i++)
{
for (size_t j = 0; j < size i 1; j++)
{
if (data[j + 1] < data[j])
{
Data temp = data[j]; // (3)
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}
По сравнению с предыдущим листингом изменений здесь совсем немного: в строке 1 объявлен параметр шаблона для типа данных, в реализации функции вместо типа данных подставляется параметр шаблона (строки 2 и 3). Теперь мы можем делать сортировку для любого типа данных: мы просто вызываем функцию и передаем ей требуемую переменную-массив, а компилятор сгенерирует код для соответствующего массива.
4.3.3. Объявление предикатов
После описанной модификации первоначального кода у нас остается одна проблема: как выполнять операции сравнения для нечисловых данных, например, структур? Ведь алгоритм не знает, да и не должен знать, по каким правилам нужно их сравнивать. Выход очевидный делегировать эти операции создателю данных. Для этого будем использовать обратный вызов «вычисление по запросу» (п. 1.2.2). Параметрами вызова будут экземпляры данных, а возвращать он будет результат сравнения. Оформленный таким образом вызов называется предикатом.
Предикат это выражение, принимающее одну или более величину и возвращающее результат булевого типа.
Объявим предикат как дополнительный параметр шаблона (Листинг 33).
Листинг 33. Шаблон с объявлением предикатаtemplate <typename Data, typename Predicate> // (1)
void sort_bubble(Data* data, size_t size, Predicate less) // (2)
{
for (size_t i = 0; i < size 1; i++)
{
for (size_t j = 0; j < size i 1; j++)
{
if (less (data[j + 1], data[j])) // (3)
{
Data temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}
По сравнению с предыдущим кодом из Листинг 32 изменения здесь следующие: в объявлении шаблона (строка 1) объявлен дополнительный параметр предикат, в функции шаблона (строка 2) предикат объявляется как дополнительный входной параметр, в строке 3 вместо операции сравнения происходит вычисление предиката.
В качестве предикатов могут использоваться:
глобальные функции;
статические функции класса;
перегруженные операторы;
лямбда-выражения.
В Листинг 34 продемонстрировано использование предикатов различных типов.
Листинг 34. Сортировка данных с использованием предикатов различных типовstruct DBRecord // (1)
{
char firstName[50];
char lastName[50];
};
bool CompareByFirstName(const DBRecord& rec1, const DBRecord& rec2) // (2)
{
return strcmp(rec1.firstName, rec2.firstName) < 0;
}
bool CompareByLastName(const DBRecord& rec1, const DBRecord& rec2) // (3)
{
return strcmp(rec1.lastName, rec2.lastName) < 0;
}
class SortRules // (4)
{
public:
enum {SORT_ASC = 1, SORT_DESC = 2} sortDirect; // (5)
enum { SORT_FIRST_NAME = 1, SORT_LAST_NAME = 2 } sortWhat; // (6)
bool operator () (const DBRecord& rec1, const DBRecord& rec2) const // (7)
{
if (sortDirect == SORT_ASC)
{
if (sortWhat == SORT_FIRST_NAME)
{
return strcmp(rec1.firstName, rec2.firstName) < 0;
}
else
{
return strcmp(rec1.lastName, rec2.lastName) < 0;
}
}
else
{
if (sortWhat == SORT_FIRST_NAME)
{
return strcmp(rec1.firstName, rec2.firstName) > 0;
}
else
{
return strcmp(rec1.lastName, rec2.lastName) > 0;
}
}
}
};
int main()
{
DBRecord dbRecArray[10]; // (8)
//Read from database
sort_bubble(dbRecArray, 10, CompareByFirstName); // (9)
sort_bubble(dbRecArray, 10, CompareByLastName); // (10)
sort_bubble(dbRecArray, 10, [](const DBRecord& rec1, const DBRecord& rec2) // (11)
{
return strcmp(rec1.firstName, rec2.firstName) < 0;
{
return strcmp(rec1.firstName, rec2.firstName) < 0;
});
sort_bubble(dbRecArray, 10, [](const DBRecord& rec1, const DBRecord& rec2) // (12)
{
return strcmp(rec1.lastName, rec2.lastName) < 0;
});
SortRules rules; // (13)
rules.sortWhat = SortRules::SORT_LAST_NAME; // (14)
rules.sortDirect = SortRules::SORT_ASC; // (15)
sort_bubble(dbRecArray, 10, rules); // (16)
}
В строке 8 объявлен массив структур, сами структуры объявлены в строке 1 (предположим, что это записи базы данных). В строке 9 и 10 происходит сортировка массива с использованием предикатов в виде внешней функции, в строках 11 и 12 в виде лямбда-выражений.
В строке 13 объявлен предикат как экземпляр класса. Если посмотреть объявление класса (строка 4), то можно увидеть, что он позволяет осуществлять настройку правил: в строке 5 имеется переменная для настройки порядка сортировки (возрастание либо убывание), в строке 6 имеется переменная для настройки поля сортировки. В строке 7 реализован перегруженный оператор, который в соответствии с настроенными правилами вычисляет, является ли первый элемент меньше второго. В строках 14 и 15 производится настройка предиката, в строке 16 сортировка в соответствии с заданными правилами.
4.3.4. Предикаты по умолчанию
Итак, мы рассмотрели, как с помощью предикатов реализуется операция вычисления меньшего из двух элементов. Но далеко не всегда требуется сортировать сложные структуры данных, зачастую это всего лишь обычные числовые значения. В этом случае придется объявлять предикат с тривиальной реализацией (сравнить два числа). Может также случиться, что у нас в объявлении элемента данных уже реализован перегруженный оператор сравнения, тогда в предикате придется дублировать его код. Всего этого можно избежать, если объявить предикат, который будет использоваться по умолчанию. Реализация приведена в Листинг 35.
Листинг 35. Шаблон с предикатом по умолчаниюtemplate <typename Data> // (1)
struct default_less
{
bool operator()(const Data& x, const Data& y) // (2)
{
return x < y;
}
};
template <typename Data, typename Predicate = default_less<Data>> // (3)
void sort_bubble(Data* data, size_t size, Predicate less = Predicate()) // (4)
{
for (size_t i = 0; i < size 1; i++)
{
for (size_t j = 0; j < size i 1; j++)
{
if (less (data[j + 1], data[j]))
{
Data temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
}
}
}
}
В строке 1 объявлен шаблон для структуры, реализующей предикат сравнения. В этой структуре перегружен оператор (строка 2), который возвращает результат сравнения двух аргументов. Он будет корректно работать как для чисел, так и для объектов, в которых перегружен оператор «меньше».
В строке 3 объявлен шаблон для функции сортировки. Первый параметр шаблона это тип данных, которые необходимо сортировать, а второй параметр это тип предиката. По умолчанию типом предиката является структура, объявленная выше, которая инстанциируется соответствующим типом данных.
В строке 4 объявлена функция шаблона. Первый параметр здесь это данные для сортировки, а второй параметр предикат для вычисления меньшего элемента. Если при вызове функции предикат не задан, то в качестве значения по умолчанию будет подставлена переменная экземпляр структуры, объявленной в строке 1. Инстанциироваться эта структура будет типом Data, переданным как первый параметр шаблона.
Итак, на примере алгоритма сортировки мы рассмотрели, как реализуются предикаты для выбора меньшего элемента из двух. Подобным образом можно реализовать множество других операций: сравнения, сложения, вычисления хэш-суммы и т. п. Таким образом, предикаты предлагают удобный способ реализации арифметико-логических операций с нечисловыми типами данных. Частично снимается проблема монолитной архитектуры при использовании функциональных объектов: мы можем реализовать любое количество нужных объектов и подставлять их в шаблон по мере необходимости19. И в заключение отметим, что концепция предикатов широко используется в реализации алгоритмов стандартной библиотеки STL.