154

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>());
Saurav Sahu
  • 13,038
  • 6
  • 64
  • 79
David Norman
  • 19,396
  • 12
  • 64
  • 54
  • 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 '08 at 03:44
  • Here is an example:
    [std::sort in a vector of pairs](http://www.codeguru.com/forum/archive/index.php/t-325645.html)
    – LeppyR64 Nov 11 '08 at 02:46
  • 2
    C++ has lambdas now! Woo! – David Poole Aug 17 '18 at 13:58

7 Answers7

262

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

Evan Teran
  • 87,561
  • 32
  • 179
  • 238
  • 1
    Keep in mind that this is different from `operator<` in `pair`. 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 04 '14 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 05 '14 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 '14 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.

Johannes Schaub - litb
  • 496,577
  • 130
  • 894
  • 1,212
  • 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. – Andreas Magnusson Nov 11 '08 at 08: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 :) – Johannes Schaub - litb Nov 11 '08 at 12:40
  • 1
    I suppose boost isn't standard, but it's close enough. :-) – David Norman Nov 11 '08 at 16:07
  • Posted a followup questions to this answer here: http://stackoverflow.com/q/4184917/220636 – nabulke Nov 15 '10 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;
}
Ezio
  • 723
  • 6
  • 14
  • 6
    Simple and "to-the-point". Doesn't need boost or a specific C++ version. +1 – Thomio Nov 30 '16 at 00:43
  • 1
    This should be marked as the best solution. Doesn't need c++14 to implement it. – Kartik Chauhan Aug 13 '17 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 – era s'q May 04 '20 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 '20 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; } );
Andreas Spindler
  • 7,568
  • 4
  • 43
  • 34
  • 1
    Why `if (lhs.second == 0)`? – the swine Jul 21 '16 at 07: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. – Andreas Spindler Sep 08 '16 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 '18 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>());
Leon Timmermans
  • 30,029
  • 2
  • 61
  • 110
1

You'd have to rely on a non standard select2nd

Greg Rogers
  • 35,641
  • 17
  • 67
  • 94
-1

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

underscore_d
  • 6,309
  • 3
  • 38
  • 64
hadizadeh.ali
  • 63
  • 1
  • 8