Operator< und strenge schwache Ordnung

Lesezeit: 1 Minute

Operator und strenge schwache Ordnung
Konstantin

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.

  • Bitte klären Sie: Sie sprechen davon, operator<() zu definieren, um n-Tupel miteinander zu vergleichen, und nicht innerhalb eines n-Tupels zu bestellen? Und warum können Sie boost::tuple nicht verwenden?

    – Pontus-Gagge

    11. Juni 2009 um 7:50 Uhr

1647130207 486 Operator und strenge schwache Ordnung
Martin York

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.

  • Die beste Erklärung für Strict Weak Ordering, die ich gelesen habe. Ich finde es toll, dass Sie es sehr deutlich gemacht haben, indem Sie alle Fälle ausführlich erklärt haben

    – DollarAkshay

    13. Juli 2019 um 21:56 Uhr

  • Was mir besonders geholfen hat zu verstehen, wie man eine strenge schwache Ordnung festlegt, ist, wie die Äquivalenz bestimmt wird a und b niemals weniger als der andere. Genau hier lag der Fehler in meinem Komparator-Prädikat.

    – Sean

    5. August 2020 um 1:39 Uhr

1647130207 944 Operator und strenge schwache Ordnung
Peterchen

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;

...

  • Dies setzt voraus, dass es bei der Frage um die Bestellung innerhalb des Tupels geht und nicht um die Bestellung zwischen Tupeln.

    – Pontus-Gagge

    11. Juni 2009 um 7:49 Uhr

  • OK, bearbeiteter Code vergleicht und ordnet zwischen Tupeln und nicht innerhalb. Ich vermute!

    – Pontus-Gagge

    11. Juni 2009 um 10:54 Uhr

  • Ja, ich habe einen Kommentar zu dem Effekt hinzugefügt, aber es ist nicht angekommen. Der ursprüngliche Code war wirklich d’oh. Ich könnte behaupten, dass es das Prinzip gezeigt hat, ohne tatsächlich etwas Nützliches zu tun, aber ….

    – Peterchen

    11. Juni 2009 um 11:37 Uhr

  • Wenn Sie jedoch Iteratoren wie in Ihrem Vektorbeispiel haben, verwenden Sie einfach std::lexographical_compare.

    – Aschepler

    7. Juni 2013 um 12:19 Uhr

  • Dies ist die Umsetzung von Lexikographische Ordnung – die eine von vielen möglichen strengen schwachen Ordnungen auf n-Tupel.

    – ks1322

    7. Dezember 2014 um 13:59 Uhr

…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_);
}

  • Ich habe mehr Details darüber, wie man ein Mitglied verwendet tie() Funktion, um in dieser Antwort prägnante und konsistente Versionen mehrerer Operatoren zu unterstützen – aber um es zusammenzufassen auto My_Struct::tie() const { return std::tie(a_, b_, c_); } dann zB bool operator<(const My_Struct& lhs, const My_Struct& rhs) { return lhs.tie() < rhs.tie(); } (wiederholen für <=, == etc.). Natürlich fügt C++ hinzu 3-Wege-Vergleichwas eine noch bessere Alternative ist.

    – Toni Delroy

    20. April 2020 um 17:10 Uhr


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.

Operator und strenge schwache Ordnung
Motti

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.

995450cookie-checkOperator< und strenge schwache Ordnung

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy