Comment trier un vecteur de paires basé sur le deuxième élément de la paire?

Question

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 fonction qui fera le travail, mais existe-t-il un moyen d'utiliser des parties existantes du STL et du std :: less pour faire le travail directement?

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

std::sort(vec.begin(), vec.end(), std::something_magic<int, int, std::less>());

Answer 1

MODIFIER : avec 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 . Ceci 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 avec lambdas:

std::sort(v.begin(), v.end(), [](const std::pair<int,int> &left, const std::pair<int,int> &right) {
    return left.second < right.second;
});

MODIFIER : en réponse aux modifications apportées à votre question, voici quelques réflexions ... Si vous voulez vraiment être créatif et pouvoir réutiliser beaucoup ce concept, créez 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 soit un peu exagéré, écrivez simplement la fonction 3 lignes et terminez-la :-P

Answer 2

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 méthode standard pour faire ceci de manière aussi courte et concise, mais vous pouvez saisir boost :: bind , il est composé uniquement d'en-têtes.

Answer 3

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 déduit implicitement.

Types de retour Lambda

Quand une fonction lambda a une seule instruction et qu'il s'agit d'une instruction return, le compilateur peut en déduire le type de retour. À partir de C ++ 11, & # 167; 5.1.2 / 4:

  

...

     

  
• Si l'instruction composée est de la forme {return expression; } le type de l'expression renvoyée après la conversion de lvalue en valeur (4.1), la conversion de tableau en pointeur (4.2) et la conversion de fonction en pointeur (4.3);
  
• sinon, void .
  

Pour spécifier explicitement le type de retour, utilisez la forme [] () - > Tapez {} , 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; } );

Answer 4

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 sur la deuxième sélection alors déclarez-vous " maComparison " comme

bool myComparison(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}

Answer 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>());

Answer 6

Vous devez vous appuyer sur un select2nd

Answer 7

Essayez d’échanger les éléments des paires pour pouvoir utiliser std :: sort () normalement.