Operator< und strenge schwache Ordnung

Wie zu definieren operator< auf n-Tupel (zum Beispiel auf 3-Tupel), damit es erfüllt strikte schwache Ordnung Konzept ? Ich weiß, dass die Boost-Bibliothek eine Tupelklasse mit korrekt definierter hat operator< aber aus irgendwelchen Gründen kann ich es nicht verwenden.

strikte schwache Ordnung

Dies ist ein mathematischer Begriff, um eine Beziehung zwischen zwei Objekten zu definieren.
Seine Definition ist:

Zwei Objekte x und y sind äquivalent, wenn sowohl f(x, y) als auch f(y, x) falsch sind. Beachten Sie, dass ein Objekt immer (durch die Irreflexivitätsinvariante) äquivalent zu sich selbst ist.

In Bezug auf C++ bedeutet dies, dass Sie, wenn Sie zwei Objekte eines bestimmten Typs haben, die folgenden Werte im Vergleich zum Operator < zurückgeben sollten.

X    a;
X    b;

Condition:                  Test:     Result
a is equivalent to b:       a < b     false
a is equivalent to b        b < a     false

a is less than b            a < b     true
a is less than b            b < a     false

b is less than a            a < b     false
b is less than a            b < a     true

Wie Sie gleichwertig/weniger definieren, hängt vollständig von der Art Ihres Objekts ab.

Formale Definition:
Streng schwache Bestellung

Informatik:
Strikte schwache Ordnung

Wie es sich auf Operatoren bezieht:
Komparator

Als Randnotiz können wir strikte schwache Ordnungen manuell implementieren. Aber wir können es einfach mit dem tun std::tuple die es für Sie umgesetzt hat. Sie müssen lediglich ein Tupel erstellen, ohne die Objekte zu kopieren.

struct S
{
     ThingA   a;
     ThingB   b;
};
bool operator<(S const& lhs, S const& rhs)
{
    return std::tie(lhs.a, lhs.b) < std::tie(rhs.a, rhs.b);
}

Hinweis: Dies setzt voraus thingA und thingB implementieren bereits selbst eine strenge schwache Ordnung.

Wir können auch die Gleichheit auf die gleiche Weise implementieren:

bool operator==(S const& lhs, S const& rhs)
{
    return std::tie(lhs.a, lhs.b) == std::tie(rhs.a, rhs.b);
}

Beachte noch einmal: Dies setzt das voraus thingA und thingB Gleichstellung bereits umsetzen.

if (a1 < b1)
  return true;
if (b1 < a1)
  return false;

// a1==b1: continue with element 2
if (a2 < b2)
  return true;
if (b2 < a2)
  return false;

// a2 == b2: continue with element 3
if (a3 < b3)
  return true;
return false; // early out

Dies ordnet die Elemente, indem a1 am signifikantesten und a3 am wenigsten signifikant ist.

Dies lässt sich endlos fortsetzen, man könnte es zB auch auf einen Vektor von T anwenden, indem man über Vergleiche von a iteriert[i] < a[i+1] / ein[i+1] < a[i]. Ein alternativer Ausdruck des Algorithmus wäre "überspringen, solange gleich, dann vergleichen":

while (i<count-1 && !(a[i] < a[i+1]) && !(a[i+1] < a[i])
  ++i;
return i < count-1 && a[i] < a[i+1];

Wenn der Vergleich teuer ist, möchten Sie das Vergleichsergebnis natürlich zwischenspeichern.

[edit] falschen Code entfernt

[edit] wenn mehr als nur operator< verfügbar ist, neige ich dazu, das Muster zu verwenden

if (a1 != b1)
  return a1 < b1;

if (a2 != b2)
  return a2 < b2;

...

…eine neue Antwort auf eine sehr alte Frage, aber die vorhandene Antwort verfehlt die einfache Lösung von C++11…

C++11-Lösung

C++11 und höher bietet std::tuple<T...>in der Sie Ihre Daten speichern können. tuples haben eine passende operator< Das vergleicht zunächst das Element ganz links und arbeitet dann entlang des Tupels, bis das Ergebnis klar ist. Das ist geeignet für die Bereitstellung der strikte schwache Ordnung erwartet von zB std::set und std::map.

Wenn Sie Daten in einigen anderen Variablen haben (z. B. Felder in a struct), können Sie sogar verwenden std::tie() to erstellt ein Tupel von Referenzen, die dann mit einem anderen solchen Tupel verglichen werden können. Das macht es einfach zu schreiben operator< für bestimmte Mitgliedsdatenfelder in einem benutzerdefinierten class/struct Art:

struct My_Struct
{
    int a_;
    double b_;
    std::string c_;
};

bool operator<(const My_Struct& lhs, const My_Struct& rhs)
{
    return std::tie(lhs.a_, lhs.b_, lhs.c_) < std::tie(rhs.a_, rhs.b_, rhs.c_);
}

Sie könnten einfach dreielementige Vektoren verwenden, für die bereits operator<() entsprechend definiert ist. Dies hat den Vorteil, dass es sich auf N-Elemente erstreckt, ohne dass Sie etwas tun müssen.

Der grundlegende Ablauf sollte wie folgt sein: wenn die K-ten Elemente unterschiedlich sind, gib das kleinere zurück, andernfalls gehe zum nächsten Element. Der folgende Code setzt Sie voraus nicht ein Boost-Tupel haben, das Sie sonst verwenden würden get<N>(tuple) und habe das Problem von vornherein nicht.

if (lhs.first != rhs.first)
    return lhs.first < rhs.first;                
if (lhs.second != rhs.second)
    return lhs.second< rhs.second;
return lhs.third < rhs.third;

Auch wenn Sie die Boost-Version nicht verwenden können, sollten Sie in der Lage sein, den Code zu klauen. Ich habe das von std::pair geklaut – ein 3-Tupel wird ähnlich sein, denke ich.

return (_Left.first < _Right.first ||
        !(_Right.first < _Left.first) && _Left.second < _Right.second);

Bearbeiten: Wie einige Leute darauf hingewiesen haben, wenn Sie Code aus der Standardbibliothek stehlen, um ihn in Ihrem Code zu verwenden, sollten Sie Dinge mit Unterstrichen auf der Vorderseite umbenennen, da diese Namen reserviert sind.