Функторы, предикаты, функциональные адаптеры, лямбда-функции

MrGluck · Регистрация: 29.11.2010

Студворк — интернет-сервис помощи студентам

Вступление

Статья ориентирована на программистов С++, поверхностно знающих/желающих узнать STL, в особенности, с использованием его алгоритмов. Это краткий обзор по основным понятиям, в конце будет приведен список литературы для более полного ознакомления с материалом.

Часто, алгоритмы STL имеют перегруженную версию или схожую по функционалу с добавлением в названии _if в конце, реализующуюся с применением функционального объекта или функции.
Пример:
copy - copy_if
find - find_if
equal
includes
sort
accumulate
и т.д.
Это позволяет гибко подстраивать их в рамках определенной задачи.

Функторы

Функторы (их еще называют объект-функциями) - конструкция, которая предоставляет возможность использовать объект как функцию. Это может быть структура или класс, перегружающие оператор(). В языке С используется указатель на функцию. Конечно, подобная вещь оставлена для совместимости, но в реальности теряет смысл в использовании в С++, впрочем, не упомянуть о возможности было бы неверно.

Пример использования функтора:

C++
1
2
3
4
5
6
7
struct Comp 
{ 
    bool operator()(const std::string &s1, const std::string &s2) const 
    { 
        return s1.length() < s2.length(); 
    } 
};

Данный оператор принимает две const строки по ссылке и возвращает истину если длина первой меньше длины второй. Аналогично можно было бы сделать с использованием класса при указании модификатора доступа public для operator().
Часто, функциональные объекты делают шаблонными для лучшей возможности повторного использования кода.

C++
1
2
3
4
5
6
7
8
9
template <typename T>  
class Mult 
{ 
    public: 
        T operator()(const T &t1, const T &t2) const 
        { 
            return t1 * t2; 
        } 
};

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

C++
1
2
3
const std::size_t N = 3; 
int A[N] = {3, 2, 5}; 
std::cout << std::accumulate(A, A + N, 1, Mult<int>());

Надо отметить, что в общем случае, идентификатор типа возвращаемого значения operator() у функтора может быть любой. В данной программе вызывается перегруженная версия алгоритма accumulate (определена в <numeric>), которая требует возврата того же типа данных, что и при передаче в функциональный объект, но в других алгоритмах может потребоваться и другой тип данных.

Предикаты

Предикаты- подмножество функторов, в которых тип возвращаемого значения operator() bool. Предикаты используются в алгоритмах сортировок, поиска, а также во всех остальных, имеющих на конце _if. Смысл в том, что объект-функция в случае использования предиката возвращает истину или ложь в зависимости от выполнения необходимого условия. Это либо удовлетворение объектом неких свойств, либо результат сравнения двух объектов по определенному признаку.

Пример использования предиката:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class DividedByTwo 
{ 
    public: 
        bool operator()(const int x) const 
        { 
            return x % 2 == 0; 
        } 
}; 
 
int main() 
{ 
    const std::size_t N = 3; 
    int A[N] = {3, 2, 5}; 
    std::cout << std::count_if(A, A + N, DividedByTwo()); 
}

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

Основные унарные и бинарные функциональные объекты, необходимые для сравнения, уже включены в STL и используются с добавлением хедера functional. Все они являются шаблонными классами и требуют определения необходимых операторов в типе данных, с которым работают. Примеры: std::greater<>, std::less<>.

Следующий код сортирует элементы по убыванию с применением нашего объекта.

C++
1
2
3
4
5
6
int main() 
{ 
    const std::size_t N = 3; 
    int A[N] = {3, 2, 5}; 
    std::sort(A, A + N, std::greater<int>()); 
}

Принцип работы std::greater схож со следующим кодом:

C++
1
2
3
4
bool operator()(const T &lhs, const T &rhs) const  
{ 
    return lhs > rhs; 
}

Иногда, нам может потребоваться реализовать, например, подсчет элементов исходя из нескольких условий, т.е. необходимо скомбинировать результаты с определенными значениями или другими функциями. В таких случаях применяют функциональные адаптеры. Необходимо отметить, что и сами адаптеры могут служить частью вычислений других адаптеров, за счет чего достигается гибкость вычислений. Основные адаптеры: bind1st, bind2nd, not1, not2.

Пример: подсчитать количество элементов, больших (>), чем два.

C++
1
2
3
4
5
6
int main() 
{ 
    const std::size_t N = 3; 
    int A[N] = {3, 2, 5}; 
    std::cout << std::count_if(A, A + N, std::bind2nd(std::greater<int>(), 2)); 
}

Данный код выведет 2. Все верно, лишь элементы 3 и 5 превосходят 2.

Пример объединения адаптеров: подсчитать количество элементов, не больших !(>), чем два.

C++
1
2
3
4
5
6
int main() 
{ 
    const std::size_t N = 3; 
    int A[N] = {3, 2, 5}; 
    std::cout << std::count_if(A, A + N, std::not1(std::bind2nd(std::greater<int>(), 2)));
}

Этот ужас, как и ожидалось, выдаст результат 1. Почему ужас? Не знаю, как вам, но по мне, так читаемость этого кода оставляет желать лучшего. И С++11 вводит специальный инструментарий, который позволяет всего этого избежать - лямбда функции, о них мы поговорим далее. Стоит отметить, что и некоторые старые адаптеры и функции были заменены новыми конструкциями - std::function, std::mem_fn, std::bind, а такие, как std::bind1st, std::bind2nd были признаны устаревшими.

Лямбда-функции

Наверное, самая приятная часть 11 стандарта, которая позволяет создавать очень гибкий код прямо на месте, не расползаясь мыслью по разным специальным классам и структурам, создаваемым для сравнения, а также повышающая читаемость кода в разы, ведь критерий сравнения или необходимая для выполнения функция определяется прямо рядом с местом использования. Тем не менее, это не отменяет использование всего того, что было озвучено выше, функциональные объекты имеют право на существование и должны использоваться там, где это действительно принесет полезный результат. Например, если необходимых инструкций для выполнения в теле функции достаточно много и определение данной функции на месте понизит удобочитаемость, или если у нас есть схожие куски кода и мы хотим вынести общий в одно место. В остальных случаях, данная конструкция будет очень удобна. Она обладает множеством различных тонкостей, мы лишь покажем общее с ней ознакомление, т.к. описание всех возможностей требовало бы отдельной статьи. Я покажу лишь использование конструкций с лямбда-функциями, и вы поймете, почему её так полюбили программисты.

Пример: необходимо подсчитать количество неотрицательных элементов, кратных 7

C++
1
2
3
4
5
6
7
8
int main() 
{ 
    const std::size_t N = 20; 
    int A[N]; 
    std::iota(A, A + N, -10); // A[0] = -10, A[1] = -9, ... A[N-1] = 9 
    std::cout << std::count_if(A, A + N, [](const int x) 
        { return x >=0 && x % 7 != 0; } ); 
}

C++
1
[](const int x) { return x >=0 && x % 7 != 0; }

и есть наша лямбда-функция.

Или же другой: вывести максимальный по модулю элемент

C++
1
2
3
4
5
6
7
8
int main() 
{ 
    const std::size_t N = 20; 
    int A[N]; 
    std::iota(A, A + N, -10); // A[0] = -10, A[1] = -9, ... A[N-1] = 9 
    std::cout << *std::max_element(A, A + N, [](const int x, const int y) 
        { return std::abs(x) < std::abs(y); } ); 
}

Необходимо лишь знать список аргументов, передаваемых функции, и то, что она должна делать (список функций вы можете посмотреть по ссылкам на информационные источники ниже в разделе algorithms library). В круглых скобках - список аргументов, которые она принимает (все как и у функтора). В фигурных идет тело функции, выполнение заканчивается после возврата с помощью return, но его наличие вовсе не обязательно.

Например, следующий код значение каждого элемента увеличивает значение на единицу и выводит на экран.

C++
1
2
3
4
5
6
7
int main() 
{ 
    const std::size_t N = 20; 
    int A[N]; 
    std::iota(A, A + N, -10); // A[0] = -10, A[1] = -9, ... A[N-1] = 9 
    std::for_each(A, A + N, [](int x) {std::cout << ++x << " "; } ); 
}

Передача аргументов в лямбда-функцию может происходить как по значению, так и по ссылке. Но что делать, если нужно, например, посчитать количество элементов, кратных некоему числу k, которое введет пользователь? Для этого используется список захвата, он передается функции в квадратных скобках, аргументы перечисляются через запятую. Передача может идти также как по значению, так и по ссылке.

Ниже приведен пример, в котором подсчитывается количество элементов, кратных k и больших, чем m.

C++
1
2
3
4
5
6
7
8
9
int main() 
{ 
    const std::size_t N = 20; 
    int A[N], k, m; 
    std::iota(A, A + N, -10); // A[0] = -10, A[1] = -9, ... A[N-1] = 9 
    std::cin >> k >> m; 
    std::cout << std::count_if(A, A + N, [k, m](const int x) 
        { return x % k != 0 && x > m; } ); 
}

Все просто и лаконично, а главное, читаемость кода возрастает в разы. Теперь я покажу пример, где используется передача аргумента по ссылке.

Пример: подсчитать количество положительных элементов и отдельно количество четных, результат вывести на экран. Для простоты, используем алгоритм for_each.

C++
1
2
3
4
5
6
7
8
9
10
11
12
int main() 
{ 
    const std::size_t N = 20; 
    int A[N], num_positives = 0, num_evens = 0; 
    std::iota(A, A + N, -10); // A[0] = -10, A[1] = -9, ... A[N-1] = 9 
    std::for_each(A, A + N, [&num_positives, &num_evens](const int x) 
    { 
        if (x >= 0) num_positives++; 
        if (x % 2 == 0) num_evens++; 
    } ); 
    std::cout << num_positives << " " << num_evens << std::endl; 
}

Подведение итогов

Я рассмотрел лишь часть функционала, впрочем вышло и так объемно.
Лямбда-функции являются частью языка и не требует подключения дополнительных хедеров. Перед их использованием необходимо убедиться, что ваш компилятор поддерживает 11 стандарт, и установлен ключ -std=c++11 (или -std=c++0x). Также, лямбда-выражения доступны с использованием семейства библиотек boost. VS поддерживает лямбда-функции лишь с 2010 студии, для пользователей gcc и, соотв. mingw рекомендуется обновиться до/на основе версии 4.7.0 и выше.

Bash
1
2
3
sudo add-apt-repository ppa:ubuntu-toolchain-r/test
sudo apt-get update
sudo apt-get install gcc-4.8 g++-4.8

Если вы пользуетесь CodeBlocks/Dev-cpp/QtCreator - можете отдельно скачать новый компилятор mingw и прописать пути к нему в IDE. Если наберется много вопросов о подключении - могу создать отдельную статью.
За сим откланиваюсь.
С уважением, MrGluck.

Данная статья была написана специально для сайта онлайн тестов http://www.quizful.net/test
Ссылка на первоисточник: http://www.quizful.net/post/fu... ers-in-STL

Литература

1) Л.Аммераль - STL для программистов на С++, глава 6 (Функциональные объекты и адаптеры)
2) Дэвид Р.Мюссер, Жилмер Дж.Дердж, Атул Сейни - C++ и STL справочное руководство, 2 изд,
глава 8 (Функциональные объекты), глава 23 (Справочное руководство по функциональным
объектам и адаптерам)
3) http://en.cppreference.com/w/c... functional
4) http://cplusplus.com/reference/functional
5) http://en.wikipedia.org/wiki/A... on#C.2B.2B

@Dmitriy_M · 03.02.2014, 10:46

Тема сисек не раскрыта.
Спрашивается зачем плодить лишние классы Comp, Mult, DividedByTwo?

@Avazart · 04.02.2014, 13:59

Сообщение от Dmitriy_M

Спрашивается зачем плодить лишние классы Comp, Mult, DividedByTwo?

Лучше одни раз создать к примеру "Comp" и потом его использовать например в 10 алгоритмах, нежели городить лямбды, каждый раз.
Хорошо если тело лямбды короткое, а если нет то получается награмождение.

@Dmitriy_M · 04.02.2014, 14:33

Avazart, в качестве функторов в SLT алгоритмах допускаются функции, объекты, лямды.
Объекты обычно используются для каррирования, задания начального значения функтора, агрегирования результата и т.д.

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cassert>
#include <iostream>
#include <algorithm>
 
#define COUNT(array) sizeof(array)/sizeof(array[0])
 
bool dividedByThree(int x)
{
  return (x % 3== 0);
}
class DividedBy 
{ 
  int m_val;
  public: 
  
  DividedBy (int val): m_val(val)
  {
    assert(m_val!=0);
  }
  
  bool operator()(const int x) const 
  { 
    return x % m_val == 0; 
  } 
}; 
 
class Foo
{
  int m_bar;
  int m_val;
  
  public:
  Foo(int bar):
    m_bar(bar),
    m_val(0)
  {
  }
  
  void operator()(const int x)
  { 
    if(x % m_bar == 0)
    {
      m_val+=x;
    } 
  } 
  int val()const
  {
    return m_val;
  }  
};
 
int main()
{
  int A[] = {3, 2, 5, 6, 8, 10}; 
  std::cout << std::count_if(A, A + COUNT(A), dividedByThree)<<std::endl; 
  std::cout << std::count_if(A, A + COUNT(A), DividedBy(3))<<std::endl; 
  std::cout << std::count_if(A, A + COUNT(A), DividedBy(3))<<std::endl; 
  std::cout << std::for_each(A, A + COUNT(A), Foo(3)).val()<<std::endl;
  return 0;
}

MrGluck · 04.02.2014, 15:00 **[ТС]**

Dmitriy_M, создайте вменяемо тип set со своим компаратором основываясь на функциях. Даже с лямбдами это не так элегантно и нагромождает код.

Не по теме:

А почему бы не пользовать std::begin, std::end?

@Dmitriy_M · 04.02.2014, 15:38

MrGluck, причем тут set?

Не по теме:

Сообщение от MrGluck

А почему бы не пользовать std::begin, std::end?

Потому что в Debian 6 gcc 4.4.5

MrGluck · 04.02.2014, 17:30 **[ТС]**

Сообщение от Dmitriy_M

MrGluck, причем тут set?

как нормально в параметрах set, например, задать свой компаратор с помощью функций?

C++
1
2
3
bool fncomp (int lhs, int rhs) {return lhs<rhs;}
bool(*fn_pt)(int,int) = fncomp;
  std::set<int,bool(*)(int,int)> name (fn_pt);

то же через функциональный объект:

C++
1
2
3
4
5
struct classcomp {
  bool operator() (const int& lhs, const int& rhs) const
  {return lhs<rhs;}
};
std::set<int,classcomp> name;

примеры отсюда:
http://www.cplusplus.com/reference/set/set/set/
Да, первый вариант можно слегка "улучшить" через лямбды, но я это к тому, что функции и функциональные объекты не одно и то же.
Про необходимость дополнить статью примерами с использованием аргументированных конструкторов в классах, описывающих функциональные объекты я уже понял.
Про внятное вступление с парой слов об алгоритмах STL и для чего иногда возникает в них потребность писать свои колбэки я тоже подметил. Если вы к этому вели, то спасибо.
Есть еще несколько пунктов для правки статьи. Сейчас времени нет, как появится - сразу буду шлифовать и добавлять.

@Dmitriy_M · 04.02.2014, 22:01

Сообщение от MrGluck

как нормально в параметрах set, например, задать свой компаратор с помощью функций?

Внезапно

C++
1
2
3
4
bool fncomp (int lhs, int rhs) {return lhs<rhs;}
typedef bool(*BIN_INT_COMP)(int,int);
//...
std::set<int,BIN_INT_COMP> bar (fncomp);

Такую штуку сделали что бы обобщить такой вариант использования

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <set>
#include <assert.h>
 
struct classcomp {
  int m_val;
  classcomp(int val):m_val(val)
  {
      assert(val != 0);
  }
 
  bool operator() (const int& lhs, const int& rhs) const
  {return (lhs % m_val)<(rhs % m_val);}
};
 
int main ()
{
  int myints[]= {10,20,30,40,50};
  std::set<int, classcomp> s1(myints,myints+5, classcomp(11));
  std::set<int, classcomp> s2(myints,myints+5, classcomp(7));
}

DiffEreD · 04.02.2014, 22:19

Компаратор для set я так делал:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <string>
#include <vector>
#include <set>
 
using std::string;
 
template <typename T>
bool func(const T& x, const T& y)
{
   return x.size() < y.size();
};
 
using my_set = std::multiset<string, decltype(&func<std::string>)>;
 
int main()
{
   std::vector<string> words{"freedom", "tree", "fox", "green", "less"};
   my_set set(words.begin(), words.end(), func);
 
   for (auto& i : set) std::cout << i << "\n";
 
   return 0;
}

MrGluck · 05.02.2014, 02:41 **[ТС]**

Сообщение от Dmitriy_M

Такую штуку сделали что бы обобщить такой вариант использования

Ну т.е. указатели на функцию во всех формах записи намного удобнее?

Посмотрите например Мюссер Д., Дердж Ж., Сейни Ф, - С++ и STL. Справочное руководство. Глава 8.2. Называется внезапно

Преимущества передачи функциональных объектов как параметров шаблонов

Из плюсов такого подхода перед функциями:
1) вы уже сами указали, удобно передавать значения
2) эффективность т.к.

при передаче функционального объекта через параметр шаблона и перегрузке оператора operator() компилятор может выполнить встраивание вызова binary_function <...> тем самым полностью устранив все дополнительные шаги по разыменовыванию указателя и

3) макроподстановка в шаблонах (все же в качестве параметра шаблона бинарную функцию не передашь)

Встраивание функционального объекта и функции не одно и то же.

Я set всегда (кроме тех случаев когда хотел с указателями на функцию поизвращаться чисто из любопытства) задавал через параметр шаблона, и не нужно помнить, что последним параметром указатель на функцию передавать надо. Считай поведение меняется в одной строке, а не во всех точках вызовов конструктора.

@Dmitriy_M · 06.02.2014, 15:03

Сообщение от MrGluck

1) вы уже сами указали, удобно передавать значения

это не плюс, это причина по которой нужно использовать объект.

Сообщение от MrGluck

2) эффективность т.к.

Есть тесты? Т.к. объект это то же оверхед, а что будет с -O3 вообще неизвестно.

Сообщение от MrGluck

3) макроподстановка в шаблонах

а в алгоритмах это нужно?

@sourcerer · 06.10.2015, 21:37

MrGluck, отличная статья! В избранное, однозначно.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@Dmitriy_M 1443 / 1326 / 131 Регистрация: 20.03.2009 Сообщений: 4,689 Записей в блоге: 11
	03.02.2014, 10:46
	Тема сисек не раскрыта. Спрашивается зачем плодить лишние классы Comp, Mult, DividedByTwo? 0

MrGluck Форумчанин 8216 / 5047 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	04.02.2014, 15:00 [ТС]
	Dmitriy_M, создайте вменяемо тип set со своим компаратором основываясь на функциях. Даже с лямбдами это не так элегантно и нагромождает код. Не по теме: А почему бы не пользовать std::begin, std::end? 0

@sourcerer Модератор 5288 / 2376 / 342 Регистрация: 20.02.2013 Сообщений: 5,773 Записей в блоге: 20
	06.10.2015, 21:37
	MrGluck, отличная статья! В избранное, однозначно. 0