Сортировка объектов в порядке убывания при определении <компаратора?

Question

У меня есть класс A и компаратор <. Как я могу использовать их для сортировки массива A в по убыванию заказать?

class A { 
... 
}; 

class LessA { 
    bool operator()(const A& a1, const A& a2) const { 
    ... 
    } 
} 

vector<A> v; 
sort(v.begin(), v.end(), ???); 

Я полагаю, я должен заменить ??? с чем-то на основе LessA, но я не могу понять, что должен пойти туда. Я думал об использовании лямбда-функции, но я искал что-то более короткое.

Answer 1

Если вы хотите отсортировать по отношению определенно вашего LessA компаратора, просто передать экземпляр LessA в качестве третьего аргумента (и, так как вы используете C++ 11, предпочитают глобальную std::begin() и std::end() функции):

std::sort(std::begin(a), std::end(a), LessA()); 
//         ^^^^^^^ 

Теперь, если ваш LessA() выражает < отношение и вы хотите отсортировать по противоположному критерию, вы могли бы сделать:

std::sort(std::begin(a), std::end(a), 
    [] (A const& a1, A const& a2)) 
{ 
    return LessA()(a2, a1); 
} 

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

class CompA { 
    bool lessThan; 
public: 
    CompA(bool lessThan) : _lessThan(lessThan) { } 
    bool operator()(const A& a1, const A& a2) const { 
     if (_lessThan) 
     { 
      // return true iff a1 < a2; 
     } 
     else 
     { 
      // return true iff a1 > a2; 
     } 
    } 
}; 

Вы могли бы использовать его таким образом, чтобы отсортировать в порядке возрастания:

std::sort(std::begin(a), std::end(a), CompA(true)); 

И этот способ сортировки в порядке убывания:

std::sort(std::begin(a), std::end(a), CompA(false)); 

другой возможности, учитывая исходный LessA компаратор, является использование std::bind поменять порядок аргументов пользовательского компаратора:

LessA comp; 
using namespace std::placeholders; 
std::sort(std::begin(v), std::end(v), 
    std::bind(&LessA::operator(), comp, _2, _1)); 

Answer 2

Сделать () оператор LessA класса возврата !(a1 < a2) и передать его в так:

std::sort(v.begin(), v.end(), LessA()); 

Answer 3

Сортировать диапазон в обратном направлении:

vector<A> v; 
sort(v.rbegin(), v.rend(), LessA()); 

rbegin и rend дают вам обратные итераторы.

Encapsulate, если это слишком запутанным:

void reverse_sort(vector<A>& v) { 
    sort(v.rbegin(), v.rend(), LessA());  
} 

Использование:

vector<A> v; 
reverse_sort(v); 

Answer 4

Использование std::greater для функтора сравнения. По умолчанию (std::less) вы получите восходящий порядок; это даст вам убывающий порядок. (Вам нужно будет добавить оператор (link) или указать явно operator>.)

Пример

Взятые из cppreference.com

#include <algorithm> 
#include <functional> 
#include <array> 
#include <iostream> 

int main() 
{ 
    std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3}; 

    // sort using the default operator< 
    std::sort(s.begin(), s.end()); 
    for (int a : s) { 
     std::cout << a << " "; 
    } 
    std::cout << '\n'; 

    // sort using a standard library compare function 
    std::sort(s.begin(), s.end(), std::greater<int>()); 
    for (int a : s) { 
     std::cout << a << " "; 
    } 
    std::cout << '\n'; 

    // sort using a custom functor 
    struct { 
     bool operator()(int a, int b) 
     { 
      return a < b; 
     } 
    } customLess; 
    std::sort(s.begin(), s.end(), customLess); 
    for (int a : s) { 
     std::cout << a << " "; 
    } 
    std::cout << '\n'; 

    // sort using a lambda 
    std::sort(s.begin(), s.end(), [](int a, int b) { 
     return b < a; 
    }); 
    for (int a : s) { 
     std::cout << a << " "; 
    } 
    std::cout << '\n'; 
} 

Answer 5

Учитывая функцию lt(a, b), которая реализует a<b, вы можете создать функцию, которая реализует a>=b путем возврата !lt(a, b). Чтобы реализовать >, вам необходимо вернуть !lt(b, a) && !(lt(a,b) || lt(b,a)).

lt(a, b) || lt(b, a) эквивалентен a!=b, поэтому приведенное выше эквивалентно a>=b && a!=b, которое сводится к a>b.

Однако, возможно, вам, возможно, сойти с рук только std::not2(LessA()). Это будет сортироваться с >=, который будет сортироваться в порядке убывания.