std :: sort с пользовательским компаратором

Question

В следующем коде, почему все три IntComparator(), IntComparator2 и IntComparator3 работают в качестве 3-го параметра функции sort()? Разве они не имеют разные типы функций с l-значением? На основании https://en.cppreference.com/w/cpp/algorithm/sort написано

Подпись функции сравнения должна быть эквивалентна следующим образом:

bool cmp (const Type1 & a, const Type2 & b);

что, кажется, соответствует IntComparator2 лучше?

Кроме того, какой из них будет предпочтительнее? Третий вариант кажется гораздо более простым и интуитивно понятным.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

struct IntComparator
{
  bool operator()(const int &a, const int &b) const
  {
    return a < b;
  }
};

bool IntComparator2 (const int &a, const int &b)
{
    return a < b;
}

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

int main()
{
    int items[] = { 4, 3, 1, 2 };
    std::sort(items, items+4, IntComparator());

    for (int n=0; n<4; n++) {
        std::cout << items[n] << ", ";
    }

    std::cout << "\n";

    int items2[] = { 4, 3, 1, 2 };
    std::sort(items2, items2+4, IntComparator2);

    for (int n=0; n<4; n++) {
        std::cout << items2[n] << ", ";
    }

    std::cout << "\n";

    int items3[] = { 4, 3, 1, 2 };
    std::sort(items3, items3+4, IntComparator3);

    for (int n=0; n<4; n++) {
        std::cout << items3[n] << ", ";
    }

    std::cout << "\n";

    return 0;
}

Answer 1

std::sort принимает functor. Это любой объект, который можно вызвать (с правильными параметрами). Функция достигает этого с помощью шаблонов, таких как:

template<typename Iter, typename Comp>
void sort(Iter begin, Iter end, Comp compare) { ... }

IntComparator1, 2 и 3 - все действительные функторы для этого компаратора, поскольку все они могут быть вызваны с помощью operator () с двумя целыми числами.

Также, как вы сказали, третий вариант обычно более интуитивно понятен.

Answer 2

Они эквивалентны, потому что спецификация C ++ говорит, что они оба соответствуют требованиям двоичного предиката. Следующие выдержки кажутся актуальными.

[function.objects]

20.14.1 Тип объекта функции - это тип объекта, который может быть типом выражения postfix в вызове функции ([expr.call], [over.match.call]). 224 Объект функции является объект типа объекта функции. В тех местах, где можно ожидать передачи указателя на функцию в алгоритмический шаблон, интерфейс указывается для приема объекта функции. Это не только заставляет алгоритмические шаблоны работать с указателями на функции, но и позволяет им работать с произвольными объектами функций.

[alg.sorting]

25.7.2 Сравнить - это тип функционального объекта ([function.objects]), который отвечает требованиям для параметра шаблона с именем BinaryPredicate ([gorithms.requirements]) . Возвращаемое значение операции вызова функции, примененной к объекту типа Compare, когда контекстно преобразуется в bool ([conv]), возвращает true, если первый аргумент вызова меньше второго, и false в противном случае. Сравнение comp используется повсеместно для алгоритмов, предполагающих отношение порядка.

[algorithms.requirements]

25.2.8 Если нет других ограничений, параметр BinaryPredicate используется всякий раз, когда алгоритм ожидает функциональный объект, который при применении к результату разыменования двух соответствующих итераторов или разыменования итератора и типа T, когда T является частью сигнатуры, возвращает значение, проверяемое как истинное. Другими словами, если алгоритм принимает BinaryPredicate binary_pred в качестве своего аргумента и first1 и first2 в качестве аргументов итератора с соответствующими типами значений T1 и T2, он должен работать правильно в конструкции binary_pred (* first1, * first2), контекстно преобразованной в bool ([ ко]). Если не указано иное, BinaryPredicate всегда принимает значение первого_тератора value_type в качестве первого аргумента, то есть в тех случаях, когда значение T является частью сигнатуры, оно должно работать правильно в конструкции binary_pred (* first1, value), контекстно преобразованной в bool ( [ко]). binary_pred не должен применять какую-либо непостоянную функцию через разыменованные итераторы. Учитывая glvalue u типа (возможно, const) T1, который обозначает тот же объект, что и * first1, и glvalue v типа (возможно, const) T2, который обозначает тот же объект, что и * first2, binary_pred (u, * first2) , binary_pred (* first1, v) и binary_pred (u, v) должны быть допустимым выражением, равным binary_pred (* first1, * first2) , а binary_pred (u, value) должно быть допустимым выражением это равно binary_pred (* first1, значение).

Что касается вопроса, который предпочтительнее, я бы сказал, что он основан на мнении, если только в вашем конкретном случае профилирование не покажет, что оно лучше.

Answer 3

Функция sort() просто вызовет функцию сравнения, которую вы предоставили, когда необходимо сравнение. То, как ваш компаратор получает свои параметры (value, reference, const ref), не относится к sort(), он будет вызывать его одинаково (передавая два аргумента одного типа) независимо от того, как ваш компаратор получает свои параметры внутри.
Он незаметен снаружи определения компаратора, поскольку способ, которым мы называем вас тремя функциями, абсолютно одинаков.

Единственное, что запрашивается, это то, что компаратор принимает только два аргумента, и они должны относиться к одному и тому же типу элементов для сортировки.

Но проходить по const ref лучше, потому что ваш компаратор гарантирует, что он не изменяет сравниваемые параметры, а также избегает ненужных копий (прирост производительности). Вот почему они написали должно быть эквивалентно (что отличается от должно быть эквивалентно ).