Роль функций библиотеки STL

Если статья "Итераторы STL" (см. "Мир ПК", # 6/98, с. 184) посвящена краеугольному камню библиотеки STL, то другой, не менее важной ее частью являются функции. В STL функции подразделяются на следующие категории: собственно функции, предикаты и функциональные объекты. В стандарте Cи++ подобная классификация функций отсутствует, что делает использование библиотеки STL просто незаменимым для программистов. Примеры из этой статьи призваны научить применять функции всех трех категорий.

Функции

Простые функции в STL применяются преимущественно как аргумент для алгоритмов. Вы, вероятно, уже знакомы с алгоритмом for_each, последний аргумент которого - указатель на функцию. В контексте STL вы будете применять функции именно как аргумент для того или иного алгоритма. Наша программа отображает на экране таблицу квадратов чисел от 0 до 10:

#include 
#include 
using namespace std;
void build_sqr_table(int num)
{
  cout << num << "	" << (num * num) << endl;
}
main(void)
{
  int values[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  cout << endl << "Number	" << "Square
" << endl;
  for_each(values , values + 10, &build_sqr_table);  
}

Алгоритм for_each последовательно берет элементы, на которые ссылается итератор, и передает их как аргумент функции, что является третьим параметром алгоритма. После чего процесс повторяется, и так до тех пор, пока итератор не указывает на значение "за пределом". Обратите внимание, что всю основную работу выполняет функция build_sqr_table(), в теле которой и происходит вычисление квадрата числа и вывод данных на экран. Еще одно маленькое замечание относительно вызова build_sqr_table(). Вы наверняка заметили, что перед именем функции стоит символ амперсанда (&), означающий операцию взятия адреса. Современные компиляторы языка Cи++ без проблем "проглатывают" имя функции и без указания оператора разадресации, но в таком случае вы получите предупреждение о передаче функции без списка аргументов. Чтобы избежать такого рода предупреждения, мы и ставим амперсанд.

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

Листинг 1. Вызов бинарной функции

#include 
#include 
using namespace std;
const char& strDif(const char& arg1, const char& arg2)
{ 
static int counter = 0;
  counter++;
  if(arg1 == arg2)
      return arg1;
  else 
  {
    cout << "Символы различаются в позиции" << counter <<
 endl; 
    return NULL;
  }
}
main(void)
{
  const char s1[] = "string1";
  const char s2[] = "strang2";
  char result[7];
  transform(s1, s1 + 7, s2, result, &strCmp);
  copy(result, result + 7, ostream_iterator(cout,
 ""));
}

В нашем примере специальный алгоритм transform занимается тем, что шаг за шагом вызывает бинарную функцию strDif(), передавая ей очередные символы, взятые из разных строк. Функция strDif() получает ссылки на символы и возвращает ссылку на символ. Внутри нее встроен статический счетчик, который сохраняет свое значение между вызовами. Если переданные символы равны, то происходит возврат из функции с передачей значения текущего символа. Если же символы различаются, то выводится сообщение с номером текущей позиции и возвращается значение NULL. Возвращаемый символ записывается в массив, строка из которого отображается на экране. Выводятся все совпадающие символы, а различающиеся показываются знаком пробела.

Предикаты

Частенько могут понадобиться средства принятия решения для управления выполнением вашей программы. С этим, как правило, хорошо справляются логические выражения языка Cи++. Но в STL принят другой подход - создание предикатов, функций, возвращающих логические значения true или false. Создать предикат очень легко - просто напишите функцию с возвращаемым типом bool.

Создадим предикат, который определяет четность числа и, если число - четное, возвращает true. Четность определяется взятием остатка от деления на 2. Далее в теле программы происходит заполнение контейнера-списка значениями от 1 до 10, для чего вызывается метод push_back(), добавляющий очередное значение в конец списка. Затем эти значения печатаются на экране. Следующий этап заключается в поиске и отделении всех четных значений. С этим успешно справляется алгоритм remove_if. Отметьте для себя, что многие алгоритмы, заканчивающиеся суффиксом _if, требуют поставить в качестве последнего параметра предикаты. Алгоритм remove_if сам по себе очень интересен. Судя по названию, он должен удалять из контейнера все элементы, для которых предикат возвращает true. Но это совсем не так - алгоритм просто сдвигает все подходящие значения в начало области данных контейнера и возвращает итератор, указывающий на элемент, следующий за удаляемыми значениями. Это позволяет считать, что начиная с адреса, на который ссылается возвращаемый итератор, и до конца области данных контейнера располагаются неудаленные значения, для которых предикат вернул false. В своей программе мы пользуемся этим свойством: все четные значения выводятся на экран, для чего мы копируем их в поток вывода, передав потоковому итератору пару итераторов, описывающих область удаленных значений. Исходный текст предиката см. в Листинге 2.

Листинг 2. Предикат, определяющий четность числа

#include 
#include 
#include 
using namespace std;
bool isEven(int num)
{
  return bool(num % 2); 
}
main(void)
{
  list l;
  list::iterator t;
    for(int i = 1; i <= 10; i++)
        l.push_back(i);
  copy(l.begin(), l.end(), ostream_iterator(cout, 
" "));
  cout << endl;
  t = remove_if(l.begin(), l.end(), isEven);
  copy(l.begin(), t, ostream_iterator(cout, " "));
}

Функциональные объекты

Функциональные объекты - это особая разновидность классов, включающих в свой состав перегруженный оператор вызова функции. Как правило, функциональный объект можно применить в любом месте, где требуется функция, к примеру, в алгоритме for_each. Каждый раз, когда должна быть вызвана функция, вызывается перегруженный оператор вызова функции. Главное, что отличает функциональный объект от обычной функции, это возможность хранения некоторого значения точно так же, как это делают статические переменные. Во время самого первого обращения к функциональному объекту вызывается инициализирующий его конструктор. В случае с обычными функциями нам пришлось бы изощряться, чтобы выполнить инициализацию. Документация от STL в реализации компании Rogue Wave утверждает, что вызов функционального объекта происходит быстрее, чем вызов функции с помощью указателя. Честно говоря, по мнению автора, это утверждение весьма спорно, но кто его знает... Может быть, вам удастся сделать тест и убедиться в правоте инженеров Rogue Wave.

Идем далее. Чтобы действительно понять, как работают функциональные объекты, нужно написать пример, скажем, таблицу умножения: слева направо увеличивается множитель, а сверху вниз - множимое. Это классический пример на алгоритм итерации. Для его реализации нужно разбить задачу на две: генерацию строки с набором частных для одного числа и повторение генерации для нескольких чисел. Первая задача, соответственно, разбивается на инициализацию, заполнение контейнера-списка (или вектора) и вывод его значений на экран. Создаваемый нами функциональный объект должен последовательно генерировать число, начиная от заданного, и каждый раз увеличивать его на определенное значение. Мы назовем функциональный объект addNumberFrom. Это имя подчеркивает, что у нас есть некоторое число, которое мы должны добавлять к некоторому начальному значению.

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

#include 
#include 
#include 
using namespace std;

Теперь опишем функциональный объект и два его поля: для хранения значения приращения (delta) и для текущего значения генерируемого числа (current):

class addNumberFrom
{
  int delta;
  int current;

Конструктор класса инициализирует значение приращения и текущее значение. Последнее может быть опущено, и тогда оно будет считаться равным 0:

public:
  addNumberFrom(int number, int from = 0)
    : delta(number), current(from)  { }

Сердце функционального объекта - перегруженный оператор вызова функции выполняет довольно скромную задачу: он просто в очередной раз прибавляет значение приращения к текущему генерируемому числу:

 int operator() ()
  { 
    return current += delta; 
  }
};

Теперь займемся той частью программы, где происходит вывод заголовка для таблицы умножения:

main(void)
{
  cout << "Таблица умножения" << endl;
  cout << "----------" << endl;

Основное действие заключено внутри цикла. Сначала на стеке создается контейнер-список:

for(int i = 1; i <= 10; i++)
  {
    list l(10);

Затем вызывается алгоритм generate_n. Конечно же, он не может сам ничего генерировать, однако он последовательно перебирает значения, диапазон которых задан начальным итератором и количеством элементов списка. Для записи числа в каждое значение вызывается функция, на которую ссылается третий параметр:

    generate_n(l.begin(), l.size(), addNumberFrom(i));

Но мы вместо функции подставляем перегруженный оператор вызова функции - объект addNumberFrom. Если вызов происходит впервые, то вызывается конструктор объекта. В нашем случае он инициализирует поле delta значением переменной i, а поле current - значением по умолчанию второго параметра конструктора, т. е. 0. Таким образом, контейнер-список заполняется произведениями числа в переменной i и множителями от 1 до 10. Обратите внимание, что в алгоритме generate_n используется метод size(), возвращающий количество элементов в списке. Если имеются начальный и конечные итераторы, тогда лучше воспользоваться алгоритмом generate.

Теперь нужно показать числа из контейнера-списка и начать новый виток цикла:

    copy(l.begin(), l.end(), ostream_iterator(cout,
 "	"));
  }
}

Очень часто арифметические и логические операции, а также операции сравнения могут быть реализованы стандартными средствами STL - набором готовых функциональных объектов (см. таблицу).

Приведенный ниже пример (см. Листинг 3) демонстрирует использование бинарных функциональных объектов. Результаты сравнений, выполненных с применением функциональных объектов, сначала заносятся в контейнеры-списки, а затем выводятся на экран дисплея.

Листинг 3. Использование бинарных функциональных объектов

#include 
#include 
#include 
using namespace std;
main(void)
{
  int v1[] = {1, 2, 3, 4, 5};
  int v2[] = {5, 4, 3, 2, 1};
  bool b1[] = {true, true, false, false};
  bool b2[] = {true, false, true, false};
  list arithmetic(5);
  list comparison(5);
  list logical(4);
  cout << "Arithmetic operations" << endl;
  transform(v1, v1 + 5, v2, arithmetic.begin(),
plus());
  copy(arithmetic.begin(), arithmetic.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  transform(v1, v1 + 5, v2, arithmetic.begin(),
 minus());
  copy(arithmetic.begin(), arithmetic.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  transform(v1, v1 + 5, v2, arithmetic.begin(),
 multiplies());
  copy(arithmetic.begin(), arithmetic.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  transform(v1, v1 + 5, v2, arithmetic.begin(),
 divides());
  copy(arithmetic.begin(), arithmetic.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  transform(v1, v1 + 5, v2, arithmetic.begin(),
 modulus());
  copy(arithmetic.begin(), arithmetic.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  cout << "Comparison operations" << endl;
  transform(v1, v1 + 5, v2, comparison.begin(),
 equal_to());
  copy(comparison.begin(), comparison.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  transform(v1, v1 + 5, v2, comparison.begin(),
 not_equal_to());
  copy(comparison.begin(), comparison.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  transform(v1, v1 + 5, v2, comparison.begin(),
 greater());
  copy(comparison.begin(), comparison.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  transform(v1, v1 + 5, v2, comparison.begin(),
 less());
  copy(comparison.begin(), comparison.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  transform(v1, v1 + 5, v2, comparison.begin(),
 greater_equal());
  copy(comparison.begin(), comparison.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  transform(v1, v1 + 5, v2, comparison.begin(),
less_equal());
  copy(comparison.begin(), comparison.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  cout << "Logical operations" << endl;
  transform(b1, b1 + 4, b2, logical.begin(),
 logical_and());
  copy(logical.begin(), logical.end(), 
        ostream_iterator(cout, " "));
  cout << endl;
  transform(b1, b1 + 4, b2, logical.begin(),
 logical_or());
  copy(logical.begin(), logical.end(), 
        ostream_iterator(cout, " "));
}

Все функции STL использовать удобно и просто. И если вы хорошенько подумаете, то наверняка сможете найти им применение в ваших проектах.