158

If I have a vector of pairs:

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

Is there and easy way to sort the list in increasing order based on the second element of the pair?

I know I can write a little function object that will do the work, but is there a way to use existing parts of the STL and std::less to do the work directly?

EDIT: I understand that I can write a separate function or class to pass to the third argument to sort. The question is whether or not I can build it out of standard stuff. I'd really something that looks like:

std::sort(vec.begin(), vec.end(), std::something_magic<int, int, std::less>());
3
  • Here is an example:<br> std::sort in a vector of pairs
    – LeppyR64
    Nov 11, 2008 at 2:46
  • 1
    c++ doesn't have lamdas so you can't do exactly what you want, you'll need to create a separate function/functor. This can be a one-liner so it really shouldn't be a big deal.
    – Evan Teran
    Nov 11, 2008 at 3:44
  • 2
    C++ has lambdas now! Woo! Aug 17, 2018 at 13:58

7 Answers 7

269

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

3
  • 1
    Keep in mind that this is different from operator< in pair<T1,T2>. The default comparator uses both first and second element (in case first ones are equal). Here only the second one is being used.
    – Googol
    Dec 4, 2014 at 23:11
  • @Googol: That's precisely what the OP asked for... He said: "is there and easy way to sort the list in increasing order based on the second element of the pair?"
    – Evan Teran
    Dec 5, 2014 at 18:42
  • @evan-teran, yes, I know. I was only indicating that if both seconds elements are equal, then the result can be confusing (if used for sorting, for example). This problem is not suffered by the default comparator because it uses the second element for tie-breaking. I reached this question looking for a comparator that used the second element as main information for comparing, but I also needed that it used the first one for tie-breaking, so I'd like to avoid others miss that point (as I, in fact, did).
    – Googol
    Dec 15, 2014 at 20:13
71

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.

4
  • 1
    +1 for using Boost. Btw, with a modern compiler you could probably already replace boost with std::tr1 as this will be in the standard soon. Nov 11, 2008 at 8:26
  • unfortunately, i tried the same with gcc trunk's c++1x std::bind, and it failed because it doesn't have the op< for bind. dunno however whether what c++1x says about this. probably it tells you to use lambda for that :) Nov 11, 2008 at 12:40
  • 1
    I suppose boost isn't standard, but it's close enough. :-) Nov 11, 2008 at 16:07
  • Posted a followup questions to this answer here: stackoverflow.com/q/4184917/220636
    – nabulke
    Nov 15, 2010 at 13:48
49

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;
}
4
  • 6
    Simple and "to-the-point". Doesn't need boost or a specific C++ version. +1
    – Thomio
    Nov 30, 2016 at 0:43
  • 1
    This should be marked as the best solution. Doesn't need c++14 to implement it. Aug 13, 2017 at 11:32
  • Can you explain to me how this comparison works? Are we passing two elements to the myComparision at a time then how is it able to sort? Also, What role does a.second<b.second play?
    – era s'q
    May 4, 2020 at 11:24
  • The myComparison function is called by the sort function where the sort function sends two value and expect a True or False in order for it to determine which should be placed first and which element should be placed second, so that is how the comparison function helps the developer to define his own definition of greater than and less than
    – Ezio
    Oct 26, 2020 at 11:52
30

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; } );
3
  • 1
    Why if (lhs.second == 0)?
    – the swine
    Jul 21, 2016 at 7:49
  • No particular meaning; lhs.second < rhs.second may return true or false and the compiler can clearly deduce bool. Just wanted to demonstrate the []() -> Type { } case. Sep 8, 2016 at 10:34
  • At least with clang, this implicit deduction may not work properly, I had to add ->bool as the lambda return type to get it working properly.
    – MoDJ
    Jul 17, 2018 at 20:28
5

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>());
1

You'd have to rely on a non standard select2nd

-1

Try swapping the elements of the pairs so you can use std::sort() as normal.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.