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>());
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; } );
if (lhs.second == 0)
?
lhs.second < rhs.second
may return true
or false
and the compiler can clearly deduce bool
. Just wanted to demonstrate the []() -> Type { }
case.
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>());
Try swapping the elements of the pairs so you can use std::sort()
as normal.
Success story sharing
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."is there and easy way to sort the list in increasing order based on the second element of the pair?"