Базовый набор для решения задач на LeetCode/Codeforces, ч.4 Функциональные объекты C++

Будет 5 статей по темам:

• Последовательные контейнеры

• Ассоциативные контейнеры

• Стеки и очереди — они же адаптеры

• Функциональные объекты (Вы тут)

• Основные алгоритмы — последние будут иногда проскакивать во всех статьях выше

Хотел написать статью про основные алгоритмы раньше, чем про предикаты, но внезапно понял, что вставлять короткие объяснения предикатов в статью напрямую связанную с разбором работы алгоритмов — плохая идея и это будет отвлекать, поэтому сразу как разберетесь с этим материалом — можете смело поступать к самой желанной части плюсов — алгоритмам STL.

На LeetCode вам довольно часто придется удалять, сортировать и разбивать контейнер на несколько более мелких — функциональные объекты помогут вам быстро решить задачу и не тратить время на написание велосипеда, который вероятнее всего будет медленнее и длиннее чем ваш вариант. Встроенные предикаты — это простые идеи решающие половину вашей головной боли при написании алгоритмов.

Наполнение статьи:

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

2) Предикаты — не бойтесь этого слова — это замаскированные односложные булевые функции.

Встроенные предикаты:

std::less — предикат сравнения меньше для типа T
std::greater — предикат сравнения больше для типа T
std::equal_to — предикат сравнения равенства для типа T

Внимание: std::bind1st — убраны в C++14 и std::bind2nd — убраны в C++17 на LeetCode они работают, потому что для них подставляют одноименную шаблонную альтернативу — пользуйтесь std::bind_front

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

1) Маскируем функции в объекты — функциональные объекты

Краткое описание: Функциональные объекты — это когда мы при помощи классов или структур реализуем некий метод, но он формализуется до объекта, то есть функция умножения числа на 5 будет выглядеть так:

struct x5{     int operator()(int number){         return number * 5;     } };  int main() {     cout<<x5()(5)<<endl;     //здесь x5 - конструктор по умолчанию     //последующие скобки вызовут перегруженый оператор - при условии, что он у вас написан     //не смог найти название такого вызова функции, но в моем кругу - это расширенный вызов функции }

Единственное отличие от обычных функций, которое вам как новичку может быть неизвестно — это операторы, почитайте про них и напишите свои операторы.

В качестве примера реализуем через функциональные объекты — max() и min(), там в операторе будет 2 элемента.

Напишем max() и min() через функциональные объекты(Зачем тип long long — узнаете дальше):

struct MIN{     bool operator()(const long long& x, const long long& y){         return x <= y;       //следите за очередностью, если вы поменяете местами x и y, то знак тоже < поверните >       // тут x<=y - это булевая операция       // если 20 <= 10, то вернется - false, который конвертнется в 0       // если 20 >= 10, то вернется - true, который конвертнется в 1     } };  struct MAX{     bool operator()(const long long& x, const long long& y){         return x >= y;     } };  class PairGenerator{ public:     PairGenerator(const long long& x, const long long& y){         this->x = x;         this->y = y;         cout<<"MIN ELEM: "<<(MIN()(x,y) ? x : y)<<endl; //MIN()(X,Y) - вернет bool, если левый элемент меньше правого, то 1, если нет, то 0 // тернарный оператор ()?true->x:false->y         cout<<"MAX ELEM: "<<(MAX()(x,y) ? x : y)<<endl;     } private:     long long x, y; };  int main(){     PairGenerator some(20, 10); //Результат: //MIN ELEM: 10 //MAX ELEM: 20 }

Зачем нам это делать? В некоторых задачах нужно сравнивать 2 числа, но при этом оба числа разных типов, вот такая задача: 2234. Maximum Total Beauty of the Gardens

Но к сожалению max() и min() работают с числами одинаковых типов, и для решения этой задачи вовсе не нужны функциональные объекты, используйте C-каст для int в long long, но не наоборот — иначе потеря точности. Делайте касты из меньшей в большую сторону. Если вы уверены в том, что промежуток меньшего является подпоследовательностью большего.

/*Я не хочу воровать время, поэтому ненужную информацию зачеркиваю:
Расскажу смешную историю: Был 2019-ый год и я участвовал в олимпиаде по программированию что-то типо КИТа, но это был не он. Я указал телефон своей матери и ей на работе позвонили с вопросом про стиль кода и знаю ли я про предикаты хоть что-нибудь(я не знал, что это такое), а чтобы вы понимали — раньше я даже отступы в строке не делал(я не любил тернарные операторы и мог if else сделать в одну строку) и в начале кода были перебиты некоторые мои заготовки функций — по памяти. Заготовка с проверкой на разные типы ne_min() ne_max() — тоже была. ne — not equal.*/

Если ветераны С++ читают этот текст, то less<> и greater<> — решает проблему разных типов, но все равно нужно самому следить за типами, в который вы конвертируете числа, иначе implicit conversion. Поскольку это предикаты расскажу о них во 2-ом пункте.

2) Односложные замаскированные булевые функции — предикаты

Предикат — заявленное, упомянутое, сказанное — спасибо википедии.
Краткое описание: Если вы пишите свою реализацию, то для описания можно сказать так — мы создаем логическое выражение и его результат обрабатываем. Логические это те, которые можно сократить до true и false — все операции сравнения.

Предикатами вы будете пользоваться довольно часто, поскольку пользуясь только функцией std::sort() вы сможете отсортировать числа в порядке возрастания, но не сможете отсортировать его по убыванию. Есть вариант с разворотом вектора через reverse(), но это медленнее и я написал только функцией std::sort. До конца 2019 — я делал так и мне не приходило в голову загуглить как в нем сортировать в другом порядке.

Встроенные предикаты(вы будете использовать их очень-очень-очень часто):

std::less<T> — сравнивает 2 числа и находит наименьшее.

    vector<int> vec{10, 30, 20, 40, 50};     std::sort(vec.begin(), vec.end(), less<int>());     for(auto& elem : vec)         cout<<elem<<" ";     //Результат: 10 20 30 40 50      //В дополнение к предыдущей программе вы можете написать так:     //Оба числа скастятся к типу, который указан в less<T>()     std::less<double>{}(5, 5.6); // тут вернется true, потому что 5 идет первым     std::less<double>{}(5.6, 5); // тут вернется false, поскольку 5.6 идет первым     std::less<double>{}(5, 5); // тут вернется false, потому что в базовой имплементации находится оператор сравнения <

std::greater<T> — сравнивает 2 числа и находит наибольшее

    vector<int> vec{10, 30, 20, 40, 50};     std::sort(vec.begin(), vec.end(), greater<int>());     for(auto& elem : vec)         cout<<elem<<" ";     //Результат: 50 40 30 20 10      //В дополнение к предыдущей программе вы можете написать так:     //Оба числа скастятся к типу, который указан в greater<T>()     std::greater<double>{}(5.6, 5); // тут вернется true, потому что 5.6 идет первым     std::greater<double>{}(5, 5.6); // тут вернется false, поскольку 5 идет первым     std::greater<double>{}(5, 5); // тут вернется false, потому что в базовой имплементации находится оператор сравнения >

std::equal_to<T> — возвращает true, если числа одинаковые

    //Оба числа скастятся к типу, который указан в less<T>()     std::equal_to<double>{}(5.6, 5); // тут вернется false     std::equal_to<double>{}(5, 5.6); // тут вернется false     std::equal_to<double>{}(5, 5); // тут вернется true

3) Безымянные(Анонимные) функции — Лямбда-функции

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

[захват_переменных] (аргументы) -> возвращаемый_тип { тело_функции };

• [захват_переменных] — сюда помещаются внешние переменные или объекты, также как и в обычной функции

• (аргументы) — такие же переменные или объекты, как и в обычных функциях

      auto sum = [](int a, int b) -> int {         return a + b;     }; //Здесь результа сохраняется в sum, но сама функция анонимна

  в захват переменных можно добавлять специальные конструкции:
  
  [=] — все переменные захватываются по значению

  [&] — все переменные захватываются по ссылке

  [ваша_переменная] — только перечисленные элементы захватываются по значению

  [&ваша_переменная] — только перечисленные элементы захватываются по ссылке

  Реализуем сортировку по убыванию через лямбда-функцию:

      vector<int> numbers = {10, 20, 30, 40, 50};      // Сортировка вектора с использованием лямбда-функции     sort(numbers.begin(), numbers.end(), [](int& a, int& b) {         return a > b;     });      for (int num : numbers) {         cout<<num<<" ";     }

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