Comment trier un vecteur de paires en fonction du deuxième élément de la paire?

133

Si j'ai un vecteur de paires:

std::vector<std::pair<int, int> > vec;

Existe-t-il un moyen simple de trier la liste par 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 y a-t-il un moyen d'utiliser les parties existantes de la STL et std::lessde faire le travail directement?

EDIT: Je comprends que je peux écrire une fonction ou une classe distincte à passer au troisième argument à trier. La question est de savoir si je peux ou non le construire à partir de choses standard. Je voudrais vraiment quelque chose qui ressemble à:

std::sort(vec.begin(), vec.end(), std::something_magic<int, int, std::less>());
David Norman
la source
Voici un exemple: <br> std :: sort dans un vecteur de paires
LeppyR64
1
c ++ n'a pas de lamdas donc vous ne pouvez pas faire exactement ce que vous voulez, vous devrez créer une fonction / un foncteur séparé. Cela peut être une ligne unique, donc cela ne devrait vraiment pas être un gros problème.
Evan Teran
1
C ++ a maintenant des lambdas! Courtiser!
David Poole

Réponses:

212

EDIT : en utilisant c ++ 14, la meilleure solution est très facile à écrire grâce aux lambdas qui peuvent désormais avoir des paramètres de type auto. C'est ma solution préférée actuelle

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 réflexions ... si vous voulez vraiment être créatif et pouvoir beaucoup réutiliser ce concept, créez simplement 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é, écrivez simplement la fonction à 3 lignes et en avez terminé :-P

Evan Teran
la source
Gardez à l'esprit que c'est différent de operator<in pair<T1,T2>. Le comparateur par défaut utilise à la fois le premier et le deuxième élément (dans le cas où les premiers sont égaux). Ici, seul le second est utilisé.
Googol
@Googol: C'est précisément ce que l'OP a demandé ... Il a dit: "is there and easy way to sort the list in increasing order based on the second element of the pair?"
Evan Teran
@ evan-teran, oui, je sais. J'indiquais seulement que si les deux éléments des secondes sont égaux, le résultat peut être déroutant (s'il est utilisé pour le tri, par exemple). Ce problème n'est pas subi par le comparateur par défaut car il utilise le deuxième élément pour le bris d'égalité. J'ai atteint cette question à la recherche d'un comparateur qui utilisait le deuxième élément comme information principale pour comparer, mais j'avais également besoin qu'il utilise le premier pour briser l'égalité, alors j'aimerais éviter que d'autres ne manquent ce point (comme je, en fait, fait).
Googol
71

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 manière standard de faire cela aussi court et concis, mais vous pouvez saisir boost::bindtout cela composé d'en-têtes.

Johannes Schaub - litb
la source
1
+1 pour l'utilisation de Boost. Btw, avec un compilateur moderne, vous pourriez probablement déjà remplacer boost par std :: tr1 car ce sera bientôt dans le standard.
Andreas Magnusson
malheureusement, j'ai essayé la même chose avec le c ++ 1x std :: bind de gcc trunk, et cela a échoué car il n'a pas l'op <pour bind. Je ne sais pas cependant si ce que dit c ++ 1x à ce sujet. il vous dit probablement d'utiliser lambda pour cela :)
Johannes Schaub - litb
1
Je suppose que le boost n'est pas standard, mais c'est assez proche. :-)
David Norman
Publié une question de suivi à cette réponse ici: stackoverflow.com/q/4184917/220636
nabulke
34

C'est assez simple, vous utilisez la fonction de tri de l'algorithme et ajoutez votre propre fonction de comparaison

vector< pair<int,int > > v;
sort(v.begin(),v.end(),myComparison);

Maintenant, vous devez faire la comparaison basée sur la deuxième sélection donc déclarez vous "maComparaison" comme

bool myComparison(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
Ezio
la source
5
Simple et "au point". N'a pas besoin de boost ou d'une version C ++ spécifique. +1
Thomio
1
Cela devrait être marqué comme la meilleure solution. N'a pas besoin de C ++ 14 pour l'implémenter.
Kartik Chauhan
Pouvez-vous m'expliquer comment fonctionne cette comparaison? Sommes-nous en train de passer deux éléments à myComparision à la fois, comment est-il capable de trier? De plus, quel rôle joue a.second <b.second?
era s'q
30

Avec C ++ 0x, nous pouvons utiliser des 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 boolest implicitement déduit.

Types de retour Lambda

Lorsqu'une fonction lambda a une seule instruction, et qu'il s'agit d'une instruction de retour, le compilateur peut déduire le type de retour. À partir de C ++ 11, §5.1.2 / 4:

...

  • Si l'instruction composée est de la forme { return expression ; }du type de l'expression retournée après la conversion de lvaleur en rvalue (4.1), la conversion de tableau en pointeur (4.2) et la conversion de fonction en pointeur (4.3);
  • autrement, 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; } );
Andreas Spindler
la source
1
Pourquoi if (lhs.second == 0)?
the swine
Aucune signification particulière; lhs.second < rhs.secondpeut retourner trueou falseet le compilateur peut clairement en déduire bool. Je voulais juste démontrer le []() -> Type { }cas.
Andreas Spindler
Au moins avec clang, cette déduction implicite peut ne pas fonctionner correctement, j'ai dû ajouter -> bool comme type de retour lambda pour le faire fonctionner correctement.
MoDJ
5

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>());
Léon Timmermans
la source
1

Il faudrait compter sur une norme non select2nd

Greg Rogers
la source
-1

Essayez d'échanger les éléments des paires afin de pouvoir les utiliser std::sort()normalement.

hadizadeh.ali
la source