простая операция сравнения. Кроме того, код для вызова функции больше, чем код простого сравнения.
21.4.2. Предикаты на членах класса
Как мы уже видели, стандартные алгоритмы хорошо работают с последовательностями элементов базовых типов, таких как int и double. Однако в некоторых предметных областях более широко используются контейнеры объектов пользовательских классов. Рассмотрим пример, играющий главную роль во многих областях, — сортировка записей по нескольким критериям.
struct Record {
string name; // стандартная строка
char addr[24]; // старый стиль для согласованности
// с базами данных
// ...
};
vector<Record> vr;
Иногда мы хотим сортировать вектор vr по имени, а иногда — по адресам. Если мы не стремимся одновременно к элегантности и эффективности, наши методы ограничены практической целесообразностью. Мы можем написать следующий код:
// ...
sort(vr.begin(),vr.end(),Cmp_by_name()); // сортировка по имени
// ...
sort(vr.begin(),vr.end(),Cmp_by_addr()); // сортировка по адресу
// ...
Cmp_by_name — это объект-функция, сравнивающий два объекта класса Record по членам name. Для того чтобы дать пользователю возможность задавать критерий сравнения, в стандартном алгоритме sort предусмотрен необязательный третий аргумент, указывающий критерий сортировки. Функция Cmp_by_name() создает объект Cmp_by_name для алгоритма sort(), чтобы использовать его для сравнения объектов класса Record. Это выглядит отлично, в том смысле, что нам не приходится об этом беспокоиться самим. Все, что мы должны сделать, — определить классы Cmp_by_name и Cmp_by_addr.
// разные сравнения объектов класса Record:
struct Cmp_by_name {
bool operator()(const Record& a,const Record& b) const
{ return a.name < b.name; }
};
struct Cmp_by_addr {
bool operator()(const Record& a, const Record& b) const
{ return strncmp(a.addr,b.addr,24) < 0; } // !!!
};
Класс Cmp_by_name совершенно очевиден. Оператор вызова функции operator()() просто сравнивает строки name, используя оператор < из стандартного класса string. Однако сравнение в классе Cmp_by_addr выглядит ужасно. Это объясняется тем, что мы выбрали неудачное представление адреса — в виде массива, состоящего из 24 символов (и не завершающегося нулем). Мы сделали этот выбор частично для того, чтобы показать, как объект-функцию можно использовать для сокрытия некрасивого и уязвимого для ошибок кода, а частично для того, чтобы продемонстрировать, что библиотека STL может решать даже ужасные, но важные с практической точки зрения задачи. Функция сравнения использует стандартную функцию strncmp(), которая сравнивает массивы символов фиксированной длины и возвращает отрицательное число, если вторая строка лексикографически больше, чем первая. Как только вам потребуется выполнить такое устаревшее сравнение, вспомните об этой функции (см., например, раздел Б.10.3).
21.5. Численные алгоритмы
Большинство стандартных алгоритмов из библиотеки STL связаны с обработкой данных: они их копируют, сортируют, выполняют поиск среди них и т.д. В то же время некоторые из них предназначены для вычислений. Они могут оказаться полезными как для решения конкретных задач, так и для демонстрации общих принципов реализации численных алгоритмов в библиотеке STL. Существуют всего четыре таких алгоритма.
Эти алгоритмы определены в заголовке <numeric>. Мы опишем первые два из них, а остальные при необходимости читатели могут изучить самостоятельно.
21.5.1. Алгоритм accumulate()
Простейшим и наиболее полезным численным алгоритмом является алгоритм accumulate(). В простейшем варианте он суммирует значения, принадлежащие последовательности.
template<class In, class T> T accumulate(In first, In last, T init)
{
while (first!=last) {
init = init + *first;
++first;
}
return init;
}
Получив начальное значение init, он просто добавляет к нему каждое значение из последовательности [first:last] и возвращает сумму. Переменную init, в которой накапливается сумма, часто называют аккумулятором (accumulator). Рассмотрим пример.
int a[] = { 1, 2, 3, 4, 5 };
cout << accumulate(a, a+sizeof(a)/sizeof(int), 0);
Этот фрагмент кода выводит на экран число 15, т.е. 0+1+2+3+4+5 (0 является начальным значением). Очевидно, что алгоритм accumulate() можно использовать для всех видов последовательностей.
void f(vector<double>& vd,int* p,int n)
{
double sum = accumulate(vd.begin(),vd.end(),0.0);
int sum2 = accumulate(p,p+n,0);
}
Тип результата (суммы) совпадает с типом переменной, которую алгоритм accumulate() использует в качестве аккумулятора. Это обеспечивает высокую степень гибкости которая может играть важную роль. Рассмотрим пример.
void f(int* p,int n)
{
int s1 = accumulate(p, p+n, 0); // суммируем целые числа в int
long sl = accumulate(p, p+n, long(0)); // суммируем целые числа
// в long
double s2 = accumulate(p, p+n, 0.0); // суммируем целые числа
// в double
}
На некоторых компьютерах переменная типа long состоит из гораздо большего количества цифр, чем переменная типа int. Переменная типа double может представить большие (и меньшие) числа, чем переменная типа int, но, возможно, с меньшей точностью. В главе 24 мы еще вернемся к вопросу о диапазоне и точности в вычислениях.
Использование переменной init в качестве аккумулятора представляет собой весьма распространенную идиому, позволяющую задать тип аккумулятора.
void f(vector<double>& vd,int* p,int n)
{
double s1 = 0;
s1 = accumulate(vd.begin(),vd.end(),s1);
int s2 = accumulate(vd.begin(), vd.end(),s2); // Ой
float s3 = 0;
accumulate(vd.begin(), vd.end(), s3); // Ой
}
Не забудьте инициализировать аккумулятор и присвоить результат работы алгоритма accumulate() какой-нибудь переменной. В данном примере в качестве инициализатора использовалась переменная s2, которая сама еще не получила начальное значение до вызова алгоритма; результат такого вызова будет непредсказуем. Мы передали переменную s3 алгоритму accumulate() (по значению; см. раздел 8.5.3), но результат ничему не присвоили; такая компиляция представляет собой простую трату времени.
21.5.2. Обобщение алгоритма accumulate()
Итак, основной алгоритм accumulate() с тремя аргументами выполняет суммирование. Однако существует много других полезных операций, например умножение и вычитание, которые можно выполнять над последовательностями, поэтому в библиотеке STL предусмотрена версия