Wie funktioniert std :: sort für eine Liste von Paaren?

Question

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

Arbeit als gedacht? Ausgang:

1 
2 
2 
5 
6 

Wie std::sort bekommt, wie meine int-string Paare sortieren? Wie mache ich das für eine Klasse von mir als Paar first? Gibt es eine Möglichkeit, nach second mit std::sort zu sortieren?

Answer 1

Da operator< definiert für std::pair und basiert auf std::pair::first und dann std::pair::second (lexikographischer), so dass Ihr Code als Standard arbeiten. Um die Suchergebnisse basierend auf dem zweiten Teil des std::pair können Sie dies versuchen:

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

Es gibt eine „offensichtlich“ Ordnung der Produkttypen, die von den jeweiligen Anordnungen der Komponenten induziert, und das ist lexicographical order:

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

Dies ist die von operator< von std::pair verwendete Reihenfolge. Da in Ihrem Beispiel alle ersten Komponenten unterschiedlich sind, entspricht die Reihenfolge der Reihenfolge der ersten Komponente. Interessanter wird es, wenn in der ersten Komponente mehrere Instanzen desselben Werts vorkommen, in denen die zweite Komponente zum Brechen von Bindungen verwendet wird.

Wie mache ich es so für eine Klasse von mir als Paar zuerst?

Sie müssen nur operator< für Ihren Typ definieren. Beachten Sie jedoch, dass die zweite Komponente bei Bedarf berücksichtigt werden kann und Sie diesen Overhead möglicherweise nicht möchten.

Gibt es eine Möglichkeit, nach second mit std::sort zu sortieren?

Ja, verwenden Sie einfach eine custom comparator functor. Sie können das immer tun, wenn Sie nicht den Standard operator< zum Sortieren verwenden möchten.