Come faccio a ordinare un vettore di coppie in base al secondo elemento della coppia?

Question

Se ho un vettore di coppie:

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

Esiste un modo semplice per ordinare l'elenco in ordine crescente in base al secondo elemento della coppia?

So di poter scrivere un piccolo oggetto funzione che farà il lavoro, ma c'è un modo per usare parti esistenti di STL e std :: less in fai il lavoro direttamente?

EDIT: capisco che posso scrivere una funzione o classe separata per passare al terzo argomento da ordinare. La domanda è se posso costruirlo o meno con roba standard. Vorrei davvero qualcosa che assomiglia:

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

Answer 1

MODIFICA : usando c ++ 14, la soluzione migliore è molto facile da scrivere grazie a lambdas che ora possono avere parametri di tipo auto . Questa è la mia attuale soluzione preferita

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

---

Basta usare un comparatore personalizzato (è un terzo argomento opzionale per 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());

Se stai usando un compilatore C ++ 11, puoi scrivere lo stesso usando lambdas:

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

MODIFICA : in risposta alle tue modifiche alla tua domanda, ecco alcuni pensieri ... se davvero vuoi essere creativo ed essere in grado di riutilizzare molto questo concetto, crea un modello:

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);
    }
};

allora puoi farlo anche tu:

std::sort(v.begin(), v.end(), sort_pair_second<int, int>());

o persino

std::sort(v.begin(), v.end(), sort_pair_second<int, int, std::greater<int> >());

Anche se ad essere sinceri, questo è un po 'eccessivo, basta scrivere la funzione a 3 righe e finirla :-P

Answer 2

Puoi usare boost in questo modo:

std::sort(a.begin(), a.end(), 
          boost::bind(&std::pair<int, int>::second, _1) <
          boost::bind(&std::pair<int, int>::second, _2));

Non conosco un modo standard per farlo allo stesso modo breve e conciso, ma puoi prendere boost :: bind è tutto composto da intestazioni.

Answer 3

Con C ++ 0x possiamo usare le funzioni 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; } );

In questo esempio il tipo restituito bool viene dedotto implicitamente.

Tipi di ritorno Lambda

Quando una funzione lambda ha una singola istruzione e questa è un'istruzione return, il compilatore può dedurre il tipo restituito. Da C ++ 11, & # 167; 5.1.2 / 4:

  

...

     

  
• Se l'istruzione composta ha la forma {restituisce espressione; } il tipo dell'espressione restituita dopo la conversione da lvalue a rvalue (4.1), la conversione da array a puntatore (4.2) e la conversione da funzione a puntatore (4.3);
  
• altrimenti, void .
  

Per specificare esplicitamente il tipo di ritorno usa il modulo [] () - > Digita {} , come in:

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

È piuttosto semplice usi la funzione di ordinamento dall'algoritmo e aggiungi la tua funzione di confronto

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

Ora devi fare il confronto in base alla seconda selezione pertanto ti dichiari " myComparison " come

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

Answer 5

Per qualcosa di riutilizzabile:

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);
    }
};

Puoi usarlo come

std::sort(foo.begin(), foo.end(), compare_pair_second<>());

o

std::sort(foo.begin(), foo.end(), compare_pair_second<std::less>());

Answer 6

Dovresti fare affidamento su un select2nd

Answer 7

Prova a scambiare gli elementi delle coppie in modo da poter usare std :: sort () normalmente.