Функциональные адаптеры C++.

Любой программист С++ при написании кода стремится достичь, как минимум, трех целей: сделать код производительным, наглядным и максимально компактным. Активное использование алгоритмов STL здесь может существенно помочь. Если алгоритм выбран правильно, то в большинстве случаев он выполнит задачу быстрее, чем самописный код. Использование алгоритмов вместо обычных циклов повышает наглядность кода, поскольку алгоритмы в тексте программы гораздо более четко отражают намерения программиста, чем однотипные циклы for. Возможность "налету" генерировать объекты функций и передавать их в алгоритмы в качестве предикатов обеспечивает коду компактность.

С предикатами в C++ все не так просто. По большому счету - предикат, это функция, возвращающая тип bool. Поэтому в качестве предикатов в алгоритмы можно передавать указатели на обычные функции. Однако, объекты функций гораздо предпочтительнее. Причина проста - объекты функций обеспечивают более эффективный код. В книге Скотта Мейерса на этот случай приводится пример с функцией std::sort - использование объектов функций всегда работает быстрее, выигрыш в скорости может составлять от 50% до 160%. Объясняется все тривиально - при использовании объекта функции компилятор способен встроить передаваемую функцию в тело алгоритма, а при использовании обычной функции встраивания не производится.

Но с объектам функций тоже все не просто! Прежде всего, из-за огромного количества вариантов подобных объектов, которые встречаются на практике. Может потребоваться вызов обычной функции или функции-члена класса. Алгоритм может требовать бинарную или унарную функцию. Подходящая для наших целей функция может требовать передачи дополнительных параметров. Объект, которому принадлежит функция, может быть константым или не константым. Аргументы в функцию могут передаваться по значению или по ссылке. Функция может быть реализована в класее. Наконец, требуемую функциональность могут реализовывать ни одна, а несколько разных функций, так что потребуется как-то скомбинировать их вызовы в одном функциональном объекте.

Впрочем, разработчики STL были прекрасно осведомлены обо всех этих сложностях. В состав STL включен отдельный файл <functional>, содержащий массу функциональных адаптеров, позволяющих "налету" создавать подходящие объекты функций в самых разнообразных случаях. Дело за малым - осталось разобраться какие адаптеры когда применять.

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

std::vector<int> t;
bool f(int Value) {
  return Value == 2;
}
std::vector<int>::iterator p = 
  std::find_if(t.begin(), t.end(), f); //находим 2

тот же самый вызов алгоритма можно переписать вот так

std::vector<int>::iterator p = 
  std::find_if(t.begin(), t.end(), std::ptr_fun(f)); 

Код работает одинаково. Но во втором случае в алгоритм передается уже не просто функция, а сгенерированный "налету" объект функции.

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

bool f2(int Value1, int Value2) {
  return Value1 == Value2;
}
int n = 10;
std::vector<int>::iterator p = 
  std::find_if(t.begin(), t.end()
   , std::bind1st(std::ptr_fun(f2), n)); 

Теперь наша функция f2() принимает два значения. Но алгоритму find_id требуется функция, которая принимает только ОДИН параметр - элемент из списка. Поэтому, мы воспользовались функцией std::bind1st. Эта функция создает экземпляр функционального адаптера std::binder1st, который "заворачивает" вызов функции с двумя параметрами в функцию с одним параметром. В итоге, алгоритм вызывает правильную функцию с одним параметром. Вызов этой функции преобразуется адаптером std::binder1st в вызов f2, причем в качестве значения дополнительного параметра адаптер подставляет то значение, которое мы передали ему при вызове std::bind1st.

В STL два связывающих адаптера: std::binder1st и std::binder2nd. Первый подставляет переданное нами значение в качестве первого параметра функции, второй - в качестве второго. Поскольку оба этих адаптера представляют из себя шаблоны с несколькими параметрами, их обычно создают через вспомагательные функции std::bind1st и std::bind2st, которые позволяют не указывать типы параметров шаблона вручную.

Пусть нам теперь требуется решить обратную задачу - найти в векторе значение, НЕ РАВНОЕ заданному. Можем ли мы для ее решения обойтись все той же функцией f2? Элементарно:

std::vector::iterator p = 
  std::find_if(t.begin(), t.end()
   , std::not1(std::bind1st(std::ptr_fun(f2), n))); 

Бинарные функции

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

bool less(int lhs, int rhs) {
 return lhs < rhs;
}
//используем собственную функцию сравнения
std::sort(t.begin(), t.end(), std::ptr_fun(less)); 

//используем стандартные функции меньше, больше
std::sort(t.begin(), t.end(), std::less<int>() ); 
std::sort(t.begin(), t.end(), std::greater<int>() ); 

//используем стандартные функции больше/меньше или равно
std::sort(t.begin(), t.end(), std::greater_equal<int>() ); 
std::sort(t.begin(), t.end(), std::less_equal<int>() ); 

//Комбинируем адаптеры: НЕ "больше или равно"
std::sort(t.begin(), t.end()
  , std::not2(std::greater_equal<int>()));

Другой пример. Переместим в начало списка все элементы удовлетворяющие заданному условию:

//все элементы равные двум
std::partition(t.begin(), t.end()
  , std::bind2nd(std::equal_to<int>(), 2));
//все элементы НЕ равные двум
std::partition(t.begin(), t.end()
  , std::bind2nd(std::not2(std::equal_to<int>()), 2));

Логические операции "меньше", "больше", "не", "больше или равно" и т.д. используются настолько часто, что шаблоны для определения подходящих функциональных объектов уже включены в STL. Та же история со стандартными арифметическими и логическими операциями.

std::vector<int> a, b;

//n = N % a1 % a2 % a3...
n = std::accumulate(a.begin(), a.end(), N
  , std::modulus<int>());

//n = n0 - (a1*b1) - (a2*b2) - (a3*b3) - ...
n = std::inner_product(a.begin(), a.end(), b.begin(), n0
  , std::minus<int>()
  , std::multiplies<int>());

//n = n0 + (a1/b1) + (a2/b2) + (a3/b3) + ...
n = std::inner_product(a.begin(), a.end(), b.begin(), n0
  , std::plus<int>()
  , std::divides<int>());

//n = N || a1 || a2 || a3...
n = std::accumulate(a.begin(), a.end(), N
  , std::logical_or<int>());

//n = N && a1 && a2 && a3...
n = std::accumulate(a.begin(), a.end(), N
  , std::logical_and<int>());

Переходим к объектам

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

struct x {
  bool f() {
    return true;}
};
std::vector<x> v;

Нам требуется найти объект, у которого функция f вернет "true". Как это сделать?

Вместо std::ptr_fun нужно использовать std::mem_fun_ref:

std::vector<x>::iterator p = std::find_if(v.begin(), v.end()
  , std::mem_fun_ref(&x::f));

Если в векторе хранятся указатели на объекты, то нужен адаптер std::mem_fun:

std::vector<x*> w;
std::vector<x*>::iterator p = std::find_if(w.begin(), w.end()
  ,std::mem_fun(&x::f1));

Собственные объекты функций

Если вы определяете собственные функциональные объекты, то их желательно наследовать от std::binary_function или std::unary_function. Эти функции добавят в определение ваших классов необходимые объявления типов и, в результате, стандартные функциональные адаптеры, типа std::bind1st, std::not1 и т.п. смогут с ними работать точно так же, как со стандартными.

Чего не хватает для счастья

Очень много. При использовании стандартных адаптеров можно налететь на проблему "ссылка на ссылку". Нужно не забывать указывать std::ptr_fun. Нет стандартных функций для создания композиций функциональных адаптеров (как, например, найти в векторе 2 ИЛИ 3?). Адаптеры std::bindXXX не пригодны для работы с функциями, у которых больше двух параметров. Наконец, в нашем распоряжении нет функторов!

Все проблемы решаются с помощью boost. Библиотека реализует улучшенный набор функциональных адаптеров, которые идентичны по синтаксису стандартным и, одновременно, свободны от проблемы "ссылки на ссылку" и не требуют явного указания std::ptr_fun. Но главная прелесть не в этом. В boost есть замечательные библиотеки: boost::bind, boost::function, boost::mem_fn и boost::lambda, которые позволяют снять указанные выше проблемы как класс и на порядок упростить создание функциональных объектов. Библиотеки boost::bind, boost::function, boost::mem_fn вошли в TR1 и теперь являются стандартными. Однако обсуждение этих библиотек - тема слишком обширная, так что отложим ее до другого раза.