Как отсортировать вектор пар на основе второго элемента пары?

Question

Если у меня есть вектор пар:

std::vector<std::pair<int, int> > vec;

Есть ли простой способ сортировки списка по возрастанию на основе второго элемента пары?

Я знаю, что могу написать небольшой функциональный объект, который будет выполнять работу, но есть ли способ использовать существующие части STL и std::less для непосредственного выполнения работы?

РЕДАКТИРОВАТЬ: я понимаю, что я могу написать отдельную функцию или класс, чтобы передать третий аргумент для сортировки. Вопрос в том, смогу ли я сделать это из стандартных вещей. Я бы действительно что-то, что выглядит так:

std::sort(vec.begin(), vec.end(), std::something_magic<int, int, std::less>());

Answer 1

РЕДАКТИРОВАТЬ : используя c ++ 14, лучшее решение очень легко написать благодаря лямбда-выражениям, которые теперь могут иметь параметры типа auto. Это мое любимое решение

std::sort(v.begin(), v.end(), [](auto &left, auto &right) {
    return left.second < right.second;
});

---

Просто используйте пользовательский компаратор (это необязательный третий аргумент для std::sort)

struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
        return left.second < right.second;
    }
};

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

Если вы используете компилятор C ++ 11, вы можете написать то же самое, используя lambdas:

std::sort(v.begin(), v.end(), [](const std::pair<int,int> &left, const std::pair<int,int> &right) {
    return left.second < right.second;
});

РЕДАКТИРОВАТЬ : в ответ на ваши правки на ваш вопрос, вот некоторые мысли ... если вы действительно хотите проявить креативность и много раз использовать эту концепцию, просто создайте шаблон:

template <class T1, class T2, class Pred = std::less<T2> >
struct sort_pair_second {
    bool operator()(const std::pair<T1,T2>&left, const std::pair<T1,T2>&right) {
        Pred p;
        return p(left.second, right.second);
    }
};

тогда вы можете сделать это тоже:

std::sort(v.begin(), v.end(), sort_pair_second<int, int>());

или даже

std::sort(v.begin(), v.end(), sort_pair_second<int, int, std::greater<int> >());

Хотя, если честно, все это немного излишне, просто напишите трехстрочную функцию и покончите с этим: -P

Answer 2

Вы можете использовать повышение как это:

std::sort(a.begin(), a.end(), 
          boost::bind(&std::pair<int, int>::second, _1) <
          boost::bind(&std::pair<int, int>::second, _2));

Я не знаю стандартного способа сделать это одинаково кратким и лаконичным, но вы можете взять boost::bind, все это состоит из заголовков.

Answer 3

С C ++ 0x мы можем использовать лямбда-функции:

using namespace std;
vector<pair<int, int>> v;
        .
        .
sort(v.begin(), v.end(),
     [](const pair<int, int>& lhs, const pair<int, int>& rhs) {
             return lhs.second < rhs.second; } );

В этом примере тип возврата bool выводится неявно.

Лямбда-типы возврата

Когда лямбда-функция имеет один оператор, а это оператор возврата, компилятор может определить тип возвращаемого значения. Из C ++ 11, §5.1.2 / 4:

...

• Если составной оператор имеет форму { return expression ; }, то тип возвращаемого выражения после преобразования lvalue-в-значение (4.1), преобразования массив-указатель (4.2) и преобразования функции-указатель ( 4,3);
• в противном случае void.

Чтобы явно указать тип возвращаемого значения, используйте форму []() -> Type { }, например:

sort(v.begin(), v.end(),
     [](const pair<int, int>& lhs, const pair<int, int>& rhs) -> bool {
             if (lhs.second == 0)
                 return true;
             return lhs.second < rhs.second; } );

Answer 4

Это довольно просто Вы используете функцию сортировки из алгоритма и добавляете свою собственную функцию сравнения

vector< pair<int,int > > v;
sort(v.begin(),v.end(),myComparison);

Теперь вы должны сделать сравнение на основе второго выбора поэтому объявляю вас "myComparison" как

bool myComparison(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}

Answer 5

Для чего-то многоразового использования:

template<template <typename> class P = std::less >
struct compare_pair_second {
    template<class T1, class T2> bool operator()(const std::pair<T1, T2>& left, const std::pair<T1, T2>& right) {
        return P<T2>()(left.second, right.second);
    }
};

Вы можете использовать его как

std::sort(foo.begin(), foo.end(), compare_pair_second<>());

или

std::sort(foo.begin(), foo.end(), compare_pair_second<std::less>());

Answer 6

Вы должны полагаться на нестандартный select2nd

Answer 7

Попробуйте поменять местами элементы пар, чтобы вы могли использовать std::sort() как обычно.