Что такое бинарный предикат?

Бинарный предикат — функция с двумя аргументами, возвращающая bool

Предикат в программировании — это функция, которая возвращает логическое значение (true/false). Бинарный означает, что она принимает ровно два параметра.

Определение

Бинарный предикат — функция вида bool f(T1 a, T2 b) или функтор/лямбда, которая сравнивает или проверяет отношение между двумя значениями.

Основное правило: предикат должен возвращать true или false на основе логики сравнения двух элементов.

Примеры в C++

1. Обычная функция

bool compare_less(int a, int b) {
    return a < b;
}

2. Функтор (класс с operator())

struct CompareGreater {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

CompareGreater pred;
bool result = pred(5, 3);  // true

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

auto is_sum_even = [](int a, int b) { return (a + b) % 2 == 0; };
bool result = is_sum_even(2, 4);  // true

Использование в STL алгоритмах

Бинарные предикаты часто используются в алгоритмах для определения порядка сортировки или поиска.

1. std::sort с бинарным предикатом

std::vector<int> nums = {5, 2, 8, 1, 9};

// Сортировка по возрастанию (по умолчанию)
std::sort(nums.begin(), nums.end(), std::less<int>());
// Результат: [1, 2, 5, 8, 9]

// Сортировка по убыванию с лямбдой
std::sort(nums.begin(), nums.end(), 
    [](int a, int b) { return a > b; });
// Результат: [9, 8, 5, 2, 1]

2. std::find_if для поиска

std::vector<std::pair<int, std::string>> students = {
    {1, "Alice"},
    {2, "Bob"},
    {3, "Charlie"}
};

// Найти студента с ID больше 2
auto it = std::find_if(students.begin(), students.end(),
    [](const auto& student) { return student.first > 2; });
// Нашли: {3, "Charlie"}

3. std::sort для объектов

struct Person {
    std::string name;
    int age;
};

std::vector<Person> people = {{"Bob", 30}, {"Alice", 25}, {"Charlie", 35}};

// Сортировка по возрасту
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) { return a.age < b.age; });
// Результат: Alice(25), Bob(30), Charlie(35)

// Сортировка по имени
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) { return a.name < b.name; });
// Результат: Alice, Bob, Charlie

Функторы vs Лямбды

Функтор — класс или структура:

class LessThan {
private:
    int threshold;

public:
    LessThan(int t) : threshold(t) {}
    
    bool operator()(int value) const {
        return value < threshold;
    }
};

std::vector<int> nums = {1, 2, 3, 4, 5};
LessThan pred(3);
auto it = std::find_if(nums.begin(), nums.end(), pred);
// Найдёт: 1

Лямбда — короче и удобнее:

std::vector<int> nums = {1, 2, 3, 4, 5};
int threshold = 3;
auto it = std::find_if(nums.begin(), nums.end(),
    [threshold](int value) { return value < threshold; });

Стандартные бинарные предикаты из <functional>

C++ STL предоставляет готовые предикаты:

#include <functional>

std::vector<int> nums = {3, 1, 4, 1, 5};

// std::less<T> — возвращает a < b
std::sort(nums.begin(), nums.end(), std::less<int>());

// std::greater<T> — возвращает a > b
std::sort(nums.begin(), nums.end(), std::greater<int>());

// std::equal_to<T> — возвращает a == b
std::find_if(nums.begin(), nums.end(),
    std::bind(std::equal_to<int>(), std::placeholders::_1, 4));

Требования к бинарному предикату

1. Принимает два параметра

// ✓ Правильно
bool pred(int a, int b) { return a < b; }

// ❌ Неправильно - не два параметра
bool bad_pred(int a) { return a > 0; }

2. Возвращает bool (или конвертируемое в bool)

// ✓ Правильно
bool pred(int a, int b) { return a < b; }

// Тоже правильно - int конвертится в bool
int pred(int a, int b) { return a - b; }

3. Не должен иметь побочные эффекты

int counter = 0;

// ❌ Плохо - побочный эффект
bool bad_pred(int a, int b) {
    counter++;  // Изменяет внешнее состояние
    return a < b;
}

// ✓ Хорошо - чистая функция
bool good_pred(int a, int b) {
    return a < b;
}

Сложный пример: сортировка структур

struct Book {
    std::string title;
    std::string author;
    int year;
};

std::vector<Book> library = {
    {"1984", "Orwell", 1949},
    {"Brave New World", "Huxley", 1932},
    {"Fahrenheit 451", "Bradbury", 1953}
};

// Сортировка по году (возрастание)
std::sort(library.begin(), library.end(),
    [](const Book& a, const Book& b) { return a.year < b.year; });
// Результат: Huxley(1932), Orwell(1949), Bradbury(1953)

// Сортировка по автору (алфавит)
std::sort(library.begin(), library.end(),
    [](const Book& a, const Book& b) { return a.author < b.author; });
// Результат: Bradbury, Huxley, Orwell

// Сложный предикат: по году убывание, потом по автору возрастание
std::sort(library.begin(), library.end(),
    [](const Book& a, const Book& b) {
        if (a.year != b.year) return a.year > b.year;  // Сначала новые
        return a.author < b.author;  // Потом по алфавиту
    });

Практическое применение: custom comparator для set

// std::set с кастомным предикатом
std::set<int, std::greater<int>> descending_set;
// Автоматически сортирует по убыванию
descending_set.insert(3);
descending_set.insert(1);
descending_set.insert(2);
// Итератор: 3, 2, 1

// Для std::pair<int, std::string>
std::set<std::pair<int, std::string>,
    decltype([](const auto& a, const auto& b) { return a.first > b.first; })
> custom_set;

Вывод

• Бинарный предикат — функция, принимающая два аргумента и возвращающая bool
• Используется в STL алгоритмах для сортировки, поиска, фильтрации
• Лямбды (C++11+) — самый удобный способ определить предикат
• Чистая функция без побочных эффектов — требование для корректной работы
• Стандартные предикаты из <functional> экономят код