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>());
109
demandé sur Angie Quijano 2008-11-11 05:41:23

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

176
répondu Evan Teran 2016-05-19 16:09:10

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.

69
répondu Johannes Schaub - litb 2008-11-11 06:08:41

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; } );
29
répondu Andreas Spindler 2013-05-29 10:10:44

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;
}
23
répondu Ezio 2015-11-11 11:20:26

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>());
5
répondu Leon Timmermans 2008-11-11 14:50:50

Vous devriez compter sur un select2nd{[3 non standard]}

1
répondu Greg Rogers 2008-11-11 02:48:19

Essayez d'échanger les éléments des paires afin que vous puissiez utiliser std::sort() comme d'habitude.

-1
répondu hadizadeh.ali 2017-10-01 15:15:30