Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.77
MrGluck
Ворчун
Эксперт CЭксперт С++
6671 / 3852 / 509
Регистрация: 29.11.2010
Сообщений: 10,209
#1

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

02.02.2014, 15:37. Просмотров 3376. Ответов 11

Вступление

Статья ориентирована на программистов С++, поверхностно знающих/желающих узнать 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/functors...dapters-in-STL


Литература

1) Л.Аммераль - STL для программистов на С++, глава 6 (Функциональные объекты и адаптеры)
2) Дэвид Р.Мюссер, Жилмер Дж.Дердж, Атул Сейни - C++ и STL справочное руководство, 2 изд,
глава 8 (Функциональные объекты), глава 23 (Справочное руководство по функциональным
объектам и адаптерам)
3) http://en.cppreference.com/w/cpp/utility/functional
4) http://cplusplus.com/reference/functional
5) http://en.wikipedia.org/wiki/Anonymous_function#C.2B.2B
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2014, 15:37     Функторы, предикаты, функциональные адаптеры, лямбда-функции
Посмотрите здесь:

Предикаты\Функторы C++
C++ Стандартные функторы-адаптеры
Передача лямбда в функции C++
C++ callback функции и функциональные объекты в качестве параметров
STL функторы, предикаты C++
C++ Лямбда функции
C++ Функторы, алгоритмы и адаптеры
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Dmitriy_M
1338 / 1219 / 111
Регистрация: 20.03.2009
Сообщений: 4,352
Записей в блоге: 11
03.02.2014, 10:46     Функторы, предикаты, функциональные адаптеры, лямбда-функции #2
Тема сисек не раскрыта.
Спрашивается зачем плодить лишние классы Comp, Mult, DividedByTwo?
Avazart
7063 / 5240 / 262
Регистрация: 10.12.2010
Сообщений: 23,058
Записей в блоге: 17
04.02.2014, 13:59     Функторы, предикаты, функциональные адаптеры, лямбда-функции #3
Цитата Сообщение от Dmitriy_M Посмотреть сообщение
Спрашивается зачем плодить лишние классы Comp, Mult, DividedByTwo?
Лучше одни раз создать к примеру "Comp" и потом его использовать например в 10 алгоритмах, нежели городить лямбды, каждый раз.
Хорошо если тело лямбды короткое, а если нет то получается награмождение.
Dmitriy_M
1338 / 1219 / 111
Регистрация: 20.03.2009
Сообщений: 4,352
Записей в блоге: 11
04.02.2014, 14:33     Функторы, предикаты, функциональные адаптеры, лямбда-функции #4
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
Ворчун
Эксперт CЭксперт С++
6671 / 3852 / 509
Регистрация: 29.11.2010
Сообщений: 10,209
04.02.2014, 15:00  [ТС]     Функторы, предикаты, функциональные адаптеры, лямбда-функции #5
Dmitriy_M, создайте вменяемо тип set со своим компаратором основываясь на функциях. Даже с лямбдами это не так элегантно и нагромождает код.

Не по теме:

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

Dmitriy_M
1338 / 1219 / 111
Регистрация: 20.03.2009
Сообщений: 4,352
Записей в блоге: 11
04.02.2014, 15:38     Функторы, предикаты, функциональные адаптеры, лямбда-функции #6
MrGluck, причем тут set?

Не по теме:


Цитата Сообщение от MrGluck Посмотреть сообщение
А почему бы не пользовать std::begin, std::end?
Потому что в Debian 6 gcc 4.4.5

MrGluck
Ворчун
Эксперт CЭксперт С++
6671 / 3852 / 509
Регистрация: 29.11.2010
Сообщений: 10,209
04.02.2014, 17:30  [ТС]     Функторы, предикаты, функциональные адаптеры, лямбда-функции #7
Цитата Сообщение от 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
1338 / 1219 / 111
Регистрация: 20.03.2009
Сообщений: 4,352
Записей в блоге: 11
04.02.2014, 22:01     Функторы, предикаты, функциональные адаптеры, лямбда-функции #8
Цитата Сообщение от 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
1427 / 764 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
04.02.2014, 22:19     Функторы, предикаты, функциональные адаптеры, лямбда-функции #9
Компаратор для 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
Ворчун
Эксперт CЭксперт С++
6671 / 3852 / 509
Регистрация: 29.11.2010
Сообщений: 10,209
05.02.2014, 02:41  [ТС]     Функторы, предикаты, функциональные адаптеры, лямбда-функции #10
Цитата Сообщение от Dmitriy_M Посмотреть сообщение
Такую штуку сделали что бы обобщить такой вариант использования
Ну т.е. указатели на функцию во всех формах записи намного удобнее?

Посмотрите например Мюссер Д., Дердж Ж., Сейни Ф, - С++ и STL. Справочное руководство. Глава 8.2. Называется внезапно
Преимущества передачи функциональных объектов как параметров шаблонов
Из плюсов такого подхода перед функциями:
1) вы уже сами указали, удобно передавать значения
2) эффективность т.к.
при передаче функционального объекта через параметр шаблона и перегрузке оператора operator() компилятор может выполнить встраивание вызова binary_function <...> тем самым полностью устранив все дополнительные шаги по разыменовыванию указателя и
3) макроподстановка в шаблонах (все же в качестве параметра шаблона бинарную функцию не передашь)

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

Я set всегда (кроме тех случаев когда хотел с указателями на функцию поизвращаться чисто из любопытства) задавал через параметр шаблона, и не нужно помнить, что последним параметром указатель на функцию передавать надо. Считай поведение меняется в одной строке, а не во всех точках вызовов конструктора.
Dmitriy_M
1338 / 1219 / 111
Регистрация: 20.03.2009
Сообщений: 4,352
Записей в блоге: 11
06.02.2014, 15:03     Функторы, предикаты, функциональные адаптеры, лямбда-функции #11
Цитата Сообщение от MrGluck Посмотреть сообщение
1) вы уже сами указали, удобно передавать значения
это не плюс, это причина по которой нужно использовать объект.
Цитата Сообщение от MrGluck Посмотреть сообщение
2) эффективность т.к.
Есть тесты? Т.к. объект это то же оверхед, а что будет с -O3 вообще неизвестно.
Цитата Сообщение от MrGluck Посмотреть сообщение
3) макроподстановка в шаблонах
а в алгоритмах это нужно?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.10.2015, 21:37     Функторы, предикаты, функциональные адаптеры, лямбда-функции
Еще ссылки по теме:

C++ Изменение содержимого вектора из лямбда функции
C++ Лямбда функции
C++ Назначение mutable в лямбда-функции
C++ лямбда как параметр функции
C++ Функциональные адаптеры

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
gru74ik
Модератор
Эксперт CЭксперт С++
3925 / 1683 / 189
Регистрация: 20.02.2013
Сообщений: 4,743
Записей в блоге: 21
06.10.2015, 21:37     Функторы, предикаты, функциональные адаптеры, лямбда-функции #12
MrGluck, отличная статья! В избранное, однозначно.
Yandex
Объявления
06.10.2015, 21:37     Функторы, предикаты, функциональные адаптеры, лямбда-функции
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru