Comment trier un vecteur de paires en fonction du deuxième élément de la paire?
Si j'ai un vecteur de paires:
std::vector<std::pair<int, int> > vec;
Existe-t-il un moyen facile de trier la liste dans un ordre croissant en fonction du deuxième élément de la paire?
Je sais que je peux écrire un petit objet de fonction qui fera le travail, mais existe-t-il un moyen d'utiliser les parties existantes du STL et std::less
pour faire le travail directement?
EDIT: je comprends que je peux écrire une fonction ou une classe distincte pour passer au troisième argument à trier. La question Est de savoir si oui ou non je peux le construire de la norme des choses. Je voudrais vraiment quelque chose qui ressemble à:
std::sort(vec.begin(), vec.end(), std::something_magic<int, int, std::less>());
7 réponses
EDIT : en utilisant c++14, la meilleure solution est très facile à écrire grâce à lambdas qui peut maintenant avoir des paramètres de type auto
. C'est ma solution préférée
std::sort(v.begin(), v.end(), [](auto &left, auto &right) {
return left.second < right.second;
});
Utilisez simplement un comparateur personnalisé (c'est un 3ème argument optionnel pour 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());
Si vous utilisez un compilateur C++11, Vous pouvez écrire la même chose en utilisant 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: en réponse à vos modifications à votre question, voici quelques pensées ... si vous vraiment vous voulez être créatif et être capable de réutiliser ce concept beaucoup, il suffit de faire un modèle:
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);
}
};
, Alors vous pouvez le faire aussi:
std::sort(v.begin(), v.end(), sort_pair_second<int, int>());
Ou même
std::sort(v.begin(), v.end(), sort_pair_second<int, int, std::greater<int> >());
Bien que pour être honnête, tout cela est un peu exagéré, il suffit d'écrire la fonction 3 lignes et d'en faire: - P
Vous pouvez utiliser boost comme ceci:
std::sort(a.begin(), a.end(),
boost::bind(&std::pair<int, int>::second, _1) <
boost::bind(&std::pair<int, int>::second, _2));
Je ne connais pas de moyen standard de le faire aussi court et concis, mais vous pouvez saisir boost::bind
tout est composé d'en-têtes.
Avec C++0x, nous pouvons utiliser les fonctions 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; } );
Dans cet exemple, le type de retour bool
est implicitement déduite.
Types de retour Lambda
Lorsqu'une fonction lambda a une seule instruction, et qu'il s'agit d'une instruction return, le compilateur peut déduire le type de retour. De C++11, §5.1.2/4:
...
- si l'instruction compound est de la forme
{ return expression ; }
le type de l'expression renvoyée après la conversion lvalue-to-rvalue (4.1), conversion tableau-pointeur (4.2), et conversion fonction-pointeur (4.3);- sinon
void
.
Pour spécifier explicitement le type de retour, utilisez le formulaire []() -> Type { }
, comme dans:
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; } );
C'est assez simple vous utilisez la fonction de tri de l'algorithme et ajouter votre propre fonction de comparaison
vector< pair<int,int > > v;
sort(v.begin(),v.end(),myComparison);
Maintenant, vous devez faire la comparaison en fonction de la deuxième sélection alors déclarez-vous "myComparison" comme
bool myComparison(const pair<int,int> &a,const pair<int,int> &b)
{
return a.second<b.second;
}
Pour quelque chose de réutilisable:
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);
}
};
, Vous pouvez l'utiliser comme
std::sort(foo.begin(), foo.end(), compare_pair_second<>());
Ou
std::sort(foo.begin(), foo.end(), compare_pair_second<std::less>());
Essayez d'échanger les éléments des paires afin que vous puissiez utiliser std::sort()
comme d'habitude.