Функция C ++ STL sort (), двоичный предикат

Question

У меня есть фрагмент кода, который меня смущает:

   sort(data, data+count, greater<int>() );

это функция сортировки в стандартной библиотеке языка C. У меня проблемы с выяснением смысла третьего аргумента. Я читал, что это называется двоичным предикатом. Что это значит и как я могу создать свой собственный предикат?

Answer 1

Третий аргумент называется предикатом .Вы можете думать о предикате как о функции, которая принимает несколько аргументов и возвращает true или false.

Так, например, вот предикат, который говорит вам, является лицелое число нечетное:

bool isOdd(int n) {
    return n & 1;
}

Приведенная выше функция принимает один аргумент, так что вы можете назвать ее унарный предикат.Если бы вместо этого потребовалось два аргумента, вы бы назвали его предикатом двоичный .Вот двоичный предикат, который сообщает вам, если его первый аргумент больше, чем второй:

bool isFirstGreater(int x, int y) {
    return x > y;
}

Предикаты обычно используются функциями очень общего назначения, чтобы вызывающая функция могла указать, как функция должнавести себя путем написания собственного кода (при использовании таким образом предикат является специализированной формой callback ).Например, рассмотрим функцию sort, когда она должна отсортировать список целых чисел.Что если бы мы захотели отсортировать все нечетные числа перед всеми четными?Мы не хотим, чтобы нас заставляли писать новую функцию сортировки каждый раз, когда мы хотим изменить порядок сортировки, потому что механика (алгоритм) сортировки явно не связана со спецификой (в каком порядке мы хотим это сделать).sort).

Итак, давайте дадим sort наш собственный предикат, чтобы сделать его сортировку в обратном порядке:

// As per the documentation of sort, this needs to return true
// if x "goes before" y. So it ends up sorting in reverse.
bool isLarger(int x, int y) {
    return x > y;
}

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

sort(data, data+count, isLarger);

Способ, которым это работает, заключается в том, что sort внутренне сравнивает пары целых чисел, чтобы решить, какой из них должен идти перед другим.Для такой пары x и y она делает это, вызывая isLarger(x, y).

Итак, на данный момент вы знаете, что такое предикат, где вы можете его использовать и как создать свой собственный,Но что означает greater<int>?

greater<T> - это двоичный предикат, который сообщает, больше ли его первый аргумент, чем второй.Это также templated struct, что означает, что он имеет много различных форм в зависимости от типа его аргументов.Этот тип должен быть указан, поэтому greater<int> - это специализация шаблона для типа int (читайте больше о шаблонах C ++, если вы чувствуете необходимость).

Так что если greater<T>такое struct, как это тоже может быть предикатом?Разве мы не говорили, что предикаты являются функциями ?

Ну, greater<T> - это функция в том смысле, что она может вызываться : она определяет оператор bool operator()(const T& x, const T& y) const;, что делает написание этого допустимого:

std::greater<int> predicate;
bool isGreater = predicate(1, 2); // isGreater == false

Объекты типа класса (или struct s, что почти одинаково в C ++), которые можно вызывать, называются функциональными объектами или функторы .

Answer 2

Существует шаблон класса с именем greater, которому требуется аргумент типа.Таким образом, вы предоставляете int как единое целое.Он стал greater<int>, и вы создаете экземпляр этого класса и передаете его функции в качестве третьего аргумента.

Такой объект называется функциональным объектом или просто функтором в C ++, так каккласс перегрузок () оператор.Это вызываемая сущность.Это выглядит так:

template<typename T>
struct greater
{
   bool operator()(const T &a, const T &b)
   {
      //compare a and b and return either true or false.
      return a > b;
   }
};

Если вы создаете экземпляр greater<int> и, скажем, объект является g, то вы можете написать g(100,200), который оценивает логическое значение, как выражениеg(100,200) вызывает operator(), передавая 100 в качестве первого аргумента и 200 в качестве второго аргумента, а operator() сравнивает их и возвращает либо true или false.

       std::cout << g(100,200) << std::endl;
       std::cout << g(200,100) << std::endl;

Выходные данные:

0
1

Демо онлайн: http://ideone.com/1HKfC

Answer 3

Бинарный предикат - это любая функция / объект, который получает два объекта (следовательно, двоичный) и возвращает bool (следовательно, предикат ); идея состоит в том, что он оценивает, удовлетворяют ли два объекта какому-то определенному условию - в примере, если один больше другого.

Вы можете создать предикат, просто определив функцию с правильной сигнатурой

bool IsIntGreater(int First, int Second)
{
    return First>Second;
}

и передачи имени функции в качестве аргумента (это приведет к передаче указателя функции) или создания объекта функции ( функтор ), то есть объекта, который перегружает оператор вызова функции и таким образом, может использоваться как функция; тип std::greater<T> является функтором шаблона, и в вашем фрагменте создается временный объект типа std::greater<int>, который передается алгоритму std::sort.

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

Answer 4

См. comp в http://www.cplusplus.com/reference/algorithm/sort/

Это функция, которая выполняет сравнение.