Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do I sort a vector of pairs based on the second element of the pair?

Tags:

c++

stl

stdvector

People also ask

How do you get the second element in pair?

To access the elements of the pair, use variable name followed by dot operator followed by the keyword 'first' or 'second', these are public members of class pair.


EDIT: using c++14, the best solution is very easy to write thanks to lambdas that can now have parameters of type auto. This is my current favorite solution

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

ORIGINAL ANSWER:

Just use a custom comparator (it's an optional 3rd argument to 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());

If you're using a C++11 compiler, you can write the same using lambdas:

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

EDIT: in response to your edits to your question, here's some thoughts ... if you really wanna be creative and be able to reuse this concept a lot, just make a template:

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);
    }
};

then you can do this too:

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

or even

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

Though to be honest, this is all a bit overkill, just write the 3 line function and be done with it :-P


You can use boost like this:

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

I don't know a standard way to do this equally short and concise, but you can grab boost::bind it's all consisting of headers.


Its pretty simple you use the sort function from algorithm and add your own compare function

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

Now you have to make the comparison based on the second selection so declare you "myComparison" as

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

With C++0x we can use lambda functions:

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; } );

In this example the return type bool is implicitly deduced.

Lambda return types

When a lambda-function has a single statement, and this is a return-statement, the compiler can deduce the return type. From C++11, §5.1.2/4:

...

  • If the compound-statement is of the form { return expression ; } the type of the returned expression after lvalue-to-rvalue conversion (4.1), array-to-pointer conversion (4.2), and function-to-pointer conversion (4.3);
  • otherwise, void.

To explicitly specify the return type use the form []() -> Type { }, like in:

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; } );

For something reusable:

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);
    }
};

You can use it as

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

or

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

You'd have to rely on a non standard select2nd