Как устроен и работает предикат?

#cpp #stl

Не могу разобраться как устроен и работает предикат. Вот простенький пример использования
предиката в сортировке:

#include 
#include 
#include 

using namespace std;

bool mySort(int x, int y){ // функция будет использоваться в качестве предиката
    return x < y;
}

int main (){
    vector va;

    va.push_back(10);
    va.push_back(100);
    va.push_back(2);

    // for (vector::iterator it = va.begin(); it != va.end(); it++)
        // cout << *it << endl;

    sort(va.begin(), va.end(), mySort); //третий параметр является предикатом

    // cout << endl;

    // for (vector::iterator it = va.begin(); it != va.end(); it++)
        // cout << *it << endl;

    return 0;
}


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

Ответы

Ответ 1

std::sort третьим параметром принимает что-то, что можно вызвать как функцию имеющую
2 параметра(полный список требований можно посмотреть тут). Не 3, не 1 — именно 2.
Почему 2? Потому что для сортировки, за одну операцию, нужно сравнить именно 2 элемента.

Теперь касательно типа параметров: чтобы корректно сравнить 2 элемента массива, тип
параметров функции должен быть совместим с типом элементов массива. Поэтому у Вас в
коде и используется int. Но можете использовать и long и любой другой тип, который
даст корректный результат сравнения. Но вот если Вы сделаете параметры функции, к примеру,
типа std::string, то получите ошибку компиляции.



Для лучшего пониманию, предлагаю рассмотреть следующий пример:

#include 

void myFunc(int x, int y) 
{ 
    std::cout << "x: " << x << ", y:" << y << "\n";
}

template
void superFunction(Fun fun)
{
    fun(156, 11);
}

int main(int argc, char* argv[])
{
    superFunction(myFunc);
}


Здесь, superFunction чем-то похожа на std::sort, она принимает своим аргументом что-то,
что можно вызвать с двумя параметрами, причём каждый параметр является int. Внутри
это «что-то» вызывается. Передав в функции main нашу myFunc мы получаем вызов оной,
косвенно, через superFunc. Точно так же всё происходит в std::sort, только там переданная
функция используется для сравнения двух элементов и в эту функцию передаются два члена
массива, вместо констант, как в моём коде.


Ответ 2

Предикат в данном случае - функция сравнения, используемая алгоритмом сортировки.
std::sort является шаблоном и компилятор подставит вызов функции-предиката при инстанцировании
шаблона. Алгоритм будет менять порядок элементов коллекции основываясь на отношении
(полного) порядка, которое и задаётся предикатом. Иными словами, для любых двух элементов
коллекции предикат должен "сказать" который из них меньше.

В предикате два параметра потому, что алгоритм std::sort при работе сравнивает два
элемента. Если использовать какой-либо хитронавороченный алгоритм, то ему может потребоваться
и иное число параметров.

Тип int у аргументов предиката потому, что контейнер содержит элементы типа int.
В общем случае типы не обязаны совпадать, а должны быть приводимыми. например, можно
использовать предикат с аргументами типа long или double.

Кстати, вместо функций в качестве предикатов можно использовать лямбды (C++11):

std::sort(va.begin(), va.end(), [](const int x, const int y) {
    return x < y   
});