Como faço para classificar um vetor de pares de base no segundo elemento do par?
Pergunta
Se eu tiver um vetor de pares:
std::vector<std::pair<int, int> > vec;
Existe maneira fácil e para ordenar a lista em ordem crescente com base no segundo elemento do par?
Eu sei que posso escrever um pequeno objeto de função que irá fazer o trabalho, mas há uma maneira de usar partes existentes do STL e std::less
para fazer o trabalho diretamente?
EDIT: Eu entendo que eu posso escrever uma função ou classe separada para passar para o terceiro argumento para espécie. A questão é se ou não posso construí-lo fora do padrão stuff. Eu realmente algo que se parece com:
std::sort(vec.begin(), vec.end(), std::something_magic<int, int, std::less>());
Solução
Editar : usando c ++ 14, a melhor solução é muito fácil escrever graças a lambdas que agora podem ter parâmetros do tipo auto
. Esta é a minha solução favorita atual
std::sort(v.begin(), v.end(), [](auto &left, auto &right) {
return left.second < right.second;
});
Basta usar um comparador personalizado (é um 3º argumento opcional para 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());
Se você estiver usando um C ++ 11 compilador, você pode escrever o mesmo usando lambdas:
std::sort(v.begin(), v.end(), [](const std::pair<int,int> &left, const std::pair<int,int> &right) {
return left.second < right.second;
});
Editar : em resposta a suas edições à sua pergunta, aqui está alguns pensamentos ... se você realmente quero ser criativo e ser capaz de reutilizar este conceito muito, basta fazer um 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);
}
};
então você pode fazer isso também:
std::sort(v.begin(), v.end(), sort_pair_second<int, int>());
ou mesmo
std::sort(v.begin(), v.end(), sort_pair_second<int, int, std::greater<int> >());
Apesar de ser honesto, tudo isso é um pouco exagerado, basta escrever a função linha 3 e ser feito com ele :-P
Outras dicas
Você pode usar boost assim:
std::sort(a.begin(), a.end(),
boost::bind(&std::pair<int, int>::second, _1) <
boost::bind(&std::pair<int, int>::second, _2));
Eu não sei uma maneira padrão de fazer isso igualmente curto e conciso, mas você pode pegar boost::bind
tudo é constituído por cabeçalhos.
Com C ++ 0x podemos usar funções lambda:
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; } );
Neste exemplo, o tipo de retorno bool
é implicitamente deduzido.
tipos retorno Lambda
Quando uma função lambda tem uma única instrução, e este é um retorno declaração, o compilador pode deduzir o tipo de retorno. De C ++ 11, §5.1.2 / 4:
...
- Se o composto-afirmação é do
{ return expression ; }
forma do tipo da expressão devolvido depois da conversão Ivalue-a-rvalue (4.1), matriz-de-ponteiro conversão (4.2), e conversão de função-para-ponteiro (4,3) ;- Caso contrário,
void
.
Para especificar explicitamente o tipo de retorno uso do formulário []() -> Type { }
, como em:
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; } );
Sua bastante simples você usa a função de classificação de algoritmo e adicionar sua própria função de comparação
vector< pair<int,int > > v;
sort(v.begin(),v.end(),myComparison);
Agora você tem que fazer a comparação com base na segunda seleção assim o declarará você "myComparison" como
bool myComparison(const pair<int,int> &a,const pair<int,int> &b)
{
return a.second<b.second;
}
Para algo reutilizável:
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);
}
};
Você pode usá-lo como
std::sort(foo.begin(), foo.end(), compare_pair_second<>());
ou
std::sort(foo.begin(), foo.end(), compare_pair_second<std::less>());
Você teria que contar com um padrão não select2nd
Tente trocar os elementos dos pares para que você possa usar std::sort()
como normal.