Try English version of Quizful



Раздаем бесплатные Q! подробности в группе Quizful.Alpha-test
Партнеры
Рекрутерам: Прескрининг кандидатов about
Топ контрибуторов
loading
loading
Знаете ли Вы, что

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

Лента обновлений
ссылка 09:16:58
Комментарий от uic:
много вопросов, содержащих синтаксис с++11.
для теста по STL...
ссылка Nov 20 18:33
Комментарий от kozak95:
согласен
ссылка Nov 20 14:11
Комментарий от Leff:
pt, pc? Вы это серьезно? Рубеж 2017-2018 за окном!
Зачем де...
ссылка Nov 20 13:47
Комментарий от Leff:
19/20, но много вопросов по тем понятиям, которые уже давно...
ссылка Nov 20 01:38
Добавлен вопрос в тест CSS - Основы
Статистика

Тестов: 153, вопросов: 8578. Пройдено: 387276 / 1881085.

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

head tail Статья
категория
C++
дата05.03.2013
авторmrgluck
голосов12

Вступление

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

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

 

Функторы

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

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

struct Comp
{
    bool operator()(const std::string &s1, const std::string &s2) const
    {
        return s1.length() < s2.length();
    }
};

 

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

template <typename T> 
class Mult 
{
    public:
        T operator()(const T &t1, const T &t2) const
        {
            return t1 * t2;
        }
};

 

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

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. Смысл в том, что объект-функция в случае использования предиката возвращает истину или ложь в зависимости от выполнения необходимого условия. Это либо удовлетворение объектом неких свойств, либо результат сравнения двух объектов по определенному признаку.

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

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<>.

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

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

 

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

bool operator()(const T &lhs, const T &rhs) const 
{
    return lhs > rhs;
}

 

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

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

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.

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

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

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; } );
}

 

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

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

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

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, но его наличие вовсе не обязательно.

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

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.

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.

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 и выше.

Команда в Ubuntu для обновления gcc:

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

 

Литература

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

Если Вам понравилась статья, проголосуйте за нее

Голосов: 12  loading...
AlexVovolka   mrgluck   ITcrusader   priskorbny   Svarog17   Lavroff   lupus   narekvar90   Staller   anti_k   DHMFU   keyzj