Будет 5 статей по темам:
Стеки и очереди - они же адаптеры
Функциональные объекты (Вы тут)
Основные алгоритмы - последние будут иногда проскакивать во всех статьях выше
Хотел написать статью про основные алгоритмы раньше, чем про предикаты, но внезапно понял, что вставлять короткие объяснения предикатов в статью напрямую связанную с разбором работы алгоритмов - плохая идея и это будет отвлекать, поэтому сразу как разберетесь с этим материалом - можете смело поступать к самой желанной части плюсов - алгоритмам STL.
На LeetCode вам довольно часто придется удалять, сортировать и разбивать контейнер на несколько более мелких - функциональные объекты помогут вам быстро решить задачу и не тратить время на написание велосипеда, который вероятнее всего будет медленнее и длиннее чем ваш вариант. Встроенные предикаты - это простые идеи решающие половину вашей головной боли при написании алгоритмов.
Наполнение статьи:
1) Функциональные объекты.
2) Предикаты - не бойтесь этого слова - это замаскированные односложные булевые функции.
Встроенные предикаты:
std::less - предикат сравнения меньше для типа T
std::greater - предикат сравнения больше для типа T
std::equal_to - предикат сравнения равенства для типа T
Про адаптеры функций(bind1st, bind2nd) поговорим в 5-ой статье, где уже разберем алгоритмы и там они будут нужны, а здесь без алгоритма - ну бесполезны абсолютно.
Внимание: 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); // тут вернется true3) Безымянные(Анонимные) функции - Лямбда-функции
Краткое описание: мы можем использовать функции с любым возвращаемым типом кроме 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<<" "; }Это одна из самых коротких статей, но пятая будет очень большой по сравнению со всеми предыдущими - я не знаю когда она будет готова, но фундамент уже готов для полноценного обзора основного пласта алгоритмов.
