How do I sort a vector of pairs based on the second element of the pair?
Solution 1
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
Solution 2
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.
Solution 3
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;
}
Solution 4
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; } );
Solution 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>());
Comments
-
David Norman about 3 years
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>());
-
Roland Jee over 15 yearsHere is an example:<br> std::sort in a vector of pairs
-
Jason over 15 yearsc++ 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.
-
David Poole over 5 yearsC++ has lambdas now! Woo!
-
-
Andreas Magnusson over 15 years+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.
-
Johannes Schaub - litb over 15 yearsunfortunately, 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 :)
-
David Norman over 15 yearsI suppose boost isn't standard, but it's close enough. :-)
-
nabulke over 13 yearsPosted a followup questions to this answer here: stackoverflow.com/q/4184917/220636
-
Googol over 9 yearsKeep in mind that this is different from
operator<
inpair<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. -
Jason over 9 years@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?"
-
Googol over 9 years@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).
-
the swine almost 8 yearsWhy
if (lhs.second == 0)
? -
Andreas Spindler over 7 yearsNo particular meaning;
lhs.second < rhs.second
may returntrue
orfalse
and the compiler can clearly deducebool
. Just wanted to demonstrate the[]() -> Type { }
case. -
Thomio over 7 yearsSimple and "to-the-point". Doesn't need boost or a specific C++ version. +1
-
Kartik Chauhan over 6 yearsThis should be marked as the best solution. Doesn't need c++14 to implement it.
-
MoDJ almost 6 yearsAt 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.
-
era s'q almost 4 yearsCan 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?
-
Ezio over 3 yearsThe 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