Wie sortiere ich effizient eine vierfache Strukturen in C++?

Question

Ich habe eine Struktur mit Mitgliedern x, y, z und w. Wie sortiere ich zuerst effizient nach x, dann nach y, nach z und schließlich nach w in C++?

Answer 1

Wenn Sie eine lexikographische Anordnung implementieren möchten, verwenden Sie am einfachsten std::tie, um einen Vergleichsoperator oder -funktor zu implementieren, der kleiner als oder größer ist. Verwenden Sie dann std::sort für eine Auflistung Ihrer Strukturen.

struct Foo 
{ 
    T x, y, z, w; 
}; 

....  
#include <tuple> // for std::tie 

bool operator<(const Foo& lhs, const Foo& rhs) 
{ 
    // assumes there is a bool operator< for T 
    return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w); 
} 

.... 

#include <algorithm> // for std::sort 

std::vector<Foo> v = ....; 
std::sort(v.begin(), v.end()); 

Wenn es keine natürliche Ordnung für Foo ist, könnte es besser sein Vergleich functors zu definieren, anstatt Vergleichsoperatoren zu implementieren. Anschließend können Sie diese Art passieren:

bool cmp_1(const Foo& lhs, const Foo& rhs) 
{ 
    return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w); 
} 

std::sort(v.begin(), v.end(), cmp_1); 

Wenn Sie nicht C++ 11 tuple Unterstützung haben, können Sie diese mit std::tr1::tie (Verwendung Header <tr1/tuple>) implementieren oder mit boost::tie vom boost.tuple library.

Answer 2

Sie können eine Struktur in eine std::tuple mit std::tie drehen, und verwenden Sie den lexikographischen Vergleich std::tuple::operator<. Hier ist ein Beispiel einer Lambda std::sort

#include <algorithm> 
#include <tuple> 
#include <vector> 

struct S 
{ 
    // x, y, z, w can be 4 different types! 
    int x, y, z, w; 
}; 

std::vector<S> v; 

std::sort(std::begin(v), std::end(v), [](S const& L, S const& R) { 
    return std::tie(L.x, L.y, L.z, L.w) < std::tie(R.x, R.y, R.z, R.w); 
}); 

mit diesem Beispiel liefert std:sort mit einem Vergleichsoperator on-the-fly. Wenn Sie immer einen lexikografischen Vergleich verwenden möchten, können Sie ein Nichtmitglied bool operator<(S const&, S const&) schreiben, das automatisch von std::sort oder von assozierten assoziierten Containern wie std::set und std::map ausgewählt wird.

In Bezug auf Effizienz, von einem online reference:

Alle Vergleichsoperatoren kurzgeschlossen sind; Sie greifen nicht auf Tupel Elemente über das hinaus, was notwendig ist, um das Ergebnis des Vergleichs zu bestimmen.

Wenn Sie eine C++ 11-Umgebung haben, bevorzugen Sie std::tie über handschriftliche Lösungen hier gegeben. Sie sind fehleranfälliger und weniger lesbar.

Answer 3

Wenn Sie einen eigenen Vergleichsoperator verwenden, können Sie Objekte frei in std::map s werfen oder std::sort aufrufen. Diese Implementierung ist so konzipiert, dass sie einfach ist, sodass Sie sie bei Bedarf einfach überprüfen und ändern können. Indem Sie nur operator< verwenden, um x, y, z und w zu vergleichen, minimiert es die Anzahl der Operatoren, die Sie möglicherweise implementieren müssen, wenn diese Variablen nicht bereits vergleichbar sind (zB wenn sie Ihre eigenen Strukturen sind anstatt ints, double, std :: Saiten etc.).

bool operator<(const Q& lhs, const Q& rhs) 
{ 
    if (lhs.x < rhs.x) return true; 
    if (rhs.x < lhs.x) return false; 
    if (lhs.y < rhs.y) return true; 
    if (rhs.y < lhs.y) return false; 
    if (lhs.z < rhs.z) return true; 
    if (rhs.z < lhs.z) return false; 
    if (lhs.w < rhs.w) return true; 
    return false; 
} 

Manchmal Typen eine Vergleichsfunktion definieren, die -1, 0 oder 1 liefert weniger als, gleich oder größer als-sowohl als Weg, um anzuzeigen, die Umsetzung des < zu unterstützen, <=, ==, !=>= und > und auch, weil manchmal eine < dann eine != oder > würde eine Menge Arbeit zu tun (in Betracht ziehen lange Textzeichenfolgen vergleichen, wo nur das letzte Zeichen unterscheidet).Wenn x, y, z und w sein solcherart passieren und haben eine höhere Leistungsfunktion vergleichen, können Sie möglicherweise Ihre Gesamtleistung verbessern mit:

bool operator<(const Q& lhs, const Q& rhs) 
{ 
    int c; 
    return (c = lhs.x.compare(rhs.x) ? c : 
      (c = lhs.y.compare(rhs.y) ? c : 
      (c = lhs.z.compare(rhs.z) ? c : 
      lhs.w < rhs.w; 
} 

Answer 4

Diese Lösung hat höchstens 4 Vergleiche pro Element-Vergleich und erfordert keine Konstruktion anderer Objekte:

// using function as comp 
std::sort (quadrupleVec.begin(), quadrupleVec.end(), [](const Quadruple& a, const Quadruple& b) 
{ 
    if (a.x != b.x) 
     return a.x < b.x; 

    if (a.y != b.y) 
     return a.y < b.y; 

    if (a.z != b.z) 
     return a.z < b.z; 

    return a.w < b.w; 
});