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

133

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

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

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

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

EDIT: я понимаю, что могу написать отдельную функцию или класс для перехода к третьему аргументу для сортировки. Вопрос в том, смогу ли я построить его из стандартных вещей. Я бы действительно что-то вроде:

std::sort(vec.begin(), vec.end(), std::something_magic<int, int, std::less>());
Дэвид Норман
источник
Вот пример: <br> std :: sort в векторе пар
LeppyR64
1
В c ++ нет ламд, поэтому вы не можете делать именно то, что хотите, вам нужно создать отдельную функцию / функтор. Это может быть однострочный текст, так что это не должно иметь большого значения.
Эван Теран
1
В C ++ теперь есть лямбды! Woo!
Дэвид Пул

Ответы:

212

РЕДАКТИРОВАТЬ : используя С ++ 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, вы можете написать то же самое, используя лямбды:

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

Эван Теран
источник
Имейте в виду, что это отличается от operator<in pair<T1,T2>. Компаратор по умолчанию использует и первый, и второй элемент (если первые равны). Здесь используется только второй.
Googol
@Googol: Именно это и просил ОП ... Он сказал: "is there and easy way to sort the list in increasing order based on the second element of the pair?"
Эван Теран
@ evan-teran, да, я знаю. Я только указывал, что если оба элемента секунд равны, то результат может сбивать с толку (например, если используется для сортировки). Компаратор по умолчанию не сталкивается с этой проблемой, потому что он использует второй элемент для разрыва связи. Я подошел к этому вопросу в поисках компаратора, который использовал второй элемент в качестве основной информации для сравнения, но мне также нужно было, чтобы он использовал первый для разрыва связи, поэтому я хотел бы, чтобы другие не пропустили этот момент (как я, в факт, сделал).
Googol
71

Вы можете использовать ускорение следующим образом:

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

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

Йоханнес Шауб - litb
источник
1
+1 за использование Boost. Кстати, с современным компилятором вы, вероятно, уже могли бы заменить boost на std :: tr1, поскольку это скоро будет в стандарте.
Андреас Магнуссон
К сожалению, я попробовал то же самое с c ++ 1x std :: bind ствола gcc, и это не удалось, потому что у него нет op <для привязки. не знаю, однако, говорит ли об этом то, что c ++ 1x. вероятно, он говорит вам использовать для этого лямбду :)
Йоханнес Шауб - litb
1
Полагаю, наддува не стандартная, но достаточно близкая. :-)
Дэвид Норман
Разместил дополнительные вопросы к этому ответу здесь: stackoverflow.com/q/4184917/220636
nabulke
34

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

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;
}
Эцио
источник
5
Просто и по делу. Не требует повышения или конкретной версии C ++. +1
Thomio
1
Это следует отметить как лучшее решение. Для его реализации не требуется C ++ 14.
Картик Чаухан
Вы можете объяснить мне, как работает это сравнение? Передаем ли мы два элемента в myComparision за раз, как тогда он сможет сортировать? Кроме того, какую роль играет a.second <b.second?
era s'q
30

С 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-to-rvalue (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; } );
Андреас Шпиндлер
источник
1
Почему if (lhs.second == 0)?
the swine
Нет особого смысла; lhs.second < rhs.secondможет вернуть trueили falseкомпилятор может ясно вывести bool. Просто хотел продемонстрировать []() -> Type { }дело.
Андреас Шпиндлер
По крайней мере, с clang этот неявный вывод может работать некорректно, мне пришлось добавить -> bool в качестве возвращаемого типа лямбда, чтобы заставить его работать правильно.
MoDJ
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>());
Леон Тиммерманс
источник
1

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

Грег Роджерс
источник
-1

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

hadizadeh.ali
источник