Comment trier un vecteur de paires en fonction du 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 en augmentation de ordre basé sur le 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 de la fonction STL et 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 pour trier. La question est de savoir si je peux ou non la construire à partir d'une fonction standard. Je voudrais vraiment quelque chose qui ressemble à :

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

Answer 1

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

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

---

PREMIÈRE RÉPONSE :

Il suffit d'utiliser un comparateur personnalisé (il s'agit d'un troisième argument facultatif de la commande 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 des 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 aux modifications apportées à votre question, voici quelques réflexions ... si vous vraiment Pour être créatif et pouvoir réutiliser souvent ce concept, il suffit de créer 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> >());

Mais pour être honnête, tout cela est un peu exagéré, il suffit d'écrire la fonction de 3 lignes et d'en finir avec elle :-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 cela de manière aussi courte et concise, mais vous pouvez saisir boost::bind tout est constitué d'en-têtes.

Answer 3

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

Types de retour lambda

Lorsqu'une fonction lambda ne comporte qu'une seule instruction, et que celle-ci est une instruction de retour, le compilateur peut déduire le type de retour. Tiré de C++11, §5.1.2/4 :

...

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

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

Answer 4

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 5

Voici un exemple :
std::sort dans un vecteur de paires