Multi-Key Benutzerdefinierte Sortierung in C++

Question

Problem Statement:

Ich mag ein std::vector eine Struktur mit meinem benutzerdefinierten Sortierkriterien sortieren.

Die Struktur ist:

struct Node 
{ 
    int x; 
    int y; 
    float value; 
} 

Ich habe einen Vektor

std::vector<Node> vec;

Meine benutzerdefinierten Kriterien Sortierung besteht darin, dass der Vektor sollte zuerst von x von y und dann sortiert werden. (Wie in Microsoft Excel)

Beispiel:

Eingang

x y 

5 6 
2 4 
1 1 
1 0 
8 10 
4 7 
7 1 
5 4 
6 1 
1 4 
3 10 
7 2 

Output:

x y 

1 0 
1 1 
6 1 
7 1 
7 2 
1 4 
2 4 
5 4 
5 6 
4 7 
3 10 
8 10 

kann die oben durch eine erreicht werden genannte Sortier die Sortierfunktionen der C++ Standard Library ? Wenn nicht, gibt es dann noch eine andere Bibliothek, die ich benutzen kann?

Answer 1

Ja, Sie können es tun, indem std::sort eine Vergleichsfunktion.

bool comparison(const Node& node1, const Node& node2) 
{ 
    if (node1.y < node2.y) return true; 
    if (node1.y == node2.y) return node1.x < node2.x; 

    return false; 
} 

int main() { 
    std::sort(vec.begin(), vec.end(), comparison); 
} 

Answer 2

std::sort übernimmt eine benutzerdefinierte Vergleichsfunktion. Ich habe nicht getestet, aber bei Ihnen vielleicht etwas wie folgt aussehen:

bool cmp (const Node& lhs, const Node& rhs) 
{ 
    if (lhs.y < rhs.y) return true; 
    else if (lhs.y == rhs.y) return (lhs.x < rhs.x); 
    else return false; 
} 

Answer 3

Im allgemeinen Implementierung Vergleichsoperator (und Funktionen) für mehrere Felder sind deutlicher in Bezug auf tie ausgedrückt, wenn lexikographischen Bestellung erforderlich ist.

static bool compare(Node const& l, Node const& r) { 
    // Note the alignment so that both expressions only differ in their `l` and `r` ? 
    return std::tie(l.y, l.x) 
     < std::tie(r.y, r.x); 
} 

Aber selbst das lässt einige Duplizierung und Route für Inkonsistenz. Der folgende Helfer sieht zu, dass:

static std::tuple<int&,int&> tuplize(Node const& n) { return std::tie(n.y, n.x); } 

, die dann einfach angewendet werden kann:

static bool compare(Node const& l, Node const& r) { 
    return tuplize(l) < tuplize(r); 
} 

Taaadaaam :)