Come funziona std :: sort per l'elenco di coppie?

Question

Perché this:

#include <iostream> 
#include <string> 
#include <vector>                
#include <algorithm> 

using namespace std; 

vector<pair<int, string>> list; 

int main() { 
    int one = 1, two = 2, three =3, five =5, six = 6; 
    string bla = "bla"; 

    list.push_back(pair<int, string>(two, bla)); 
    list.push_back(pair<int, string>(one, bla)); 
    list.push_back(pair<int, string>(two, bla)); 
    list.push_back(pair<int, string>(six, bla)); 
    list.push_back(pair<int, string>(five, bla)); 

    sort(list.begin(), list.end()); 

    for(auto item : list) { 
     cout << item.first << endl; 
    } 
} 

lavoro come previsto? output è:

1 
2 
2 
5 
6 

Come std::sort ottiene come ordinare i miei int-string coppie? Come farlo fare così per una mia classe come coppia first? C'è un modo per ordinare per second utilizzando std::sort?

Answer 1

Dal operator< è definita per std::pair e si basa su std::pair::first e poi std::pair::second (lessicografico), in modo che il codice sta lavorando come standard. Fascicolarlo basato sulla seconda parte del std::pair si può provare questo:

std::sort(list.begin(), list.end(), [](const std::pair<int, string> &x, 
             const std::pair<int, string> &y) 
{ 
    return x.second < y.second; 
}); 

Answer 2

C'è un ordinamento "ovvio" di tipi di prodotto indotte dai rispettivi ordinamenti dei componenti, e che è lexicographical order:

(a, b) < (c, d) <=> a < c || (a == c && b < d) 

Questo è l'ordine utilizzato da operator< di std::pair. Nel tuo esempio, poiché tutti i primi componenti sono distinti, l'ordine sembra essere uguale all'ordinamento del primo componente. Diventa più interessante se si hanno più occorrenze dello stesso valore nel primo componente, in cui viene utilizzato il secondo componente per rompere i legami.

Come si fa a farlo per una mia classe come prima coppia?

Devi solo definire operator< per il tuo tipo. Ma tieni presente che il secondo componente sarà considerato se necessario e potresti non volerlo.

C'è un modo per ordinare tramite second utilizzando std::sort?

Sì, utilizzare solo uno custom comparator functor. È sempre possibile farlo se non si desidera utilizzare l'impostazione predefinita operator< per l'ordinamento.