Operator< für eine Struktur definieren

Lesezeit: 5 Minuten

Ich benutze manchmal klein structs als Schlüssel in Karten, und so muss ich eine definieren operator< für Sie. Normalerweise sieht das am Ende so aus:

struct MyStruct
{
    A a;
    B b;
    C c;

    bool operator<(const MyStruct& rhs) const
    {
        if (a < rhs.a)
        {
           return true;
        }
        else if (a == rhs.a)
        {
            if (b < rhs.b)
            {
                return true;
            }
            else if (b == rhs.b)
            {
                return c < rhs.c;
            }
        }

        return false;
    }
};

Dies scheint furchtbar ausführlich und fehleranfällig zu sein. Gibt es einen besseren Weg oder einen einfachen Weg, um die Definition von zu automatisieren? operator< Für ein struct oder class?

Ich weiß, dass einige Leute einfach so etwas wie verwenden memcmp(this, &rhs, sizeof(MyStruct)) < 0aber dies funktioniert möglicherweise nicht richtig, wenn Füllbytes zwischen den Mitgliedern vorhanden sind oder wenn vorhanden sind char String-Arrays, die nach den Null-Terminatoren Müll enthalten können.

  • Sie können Kürze haben, die nicht wesentlich fehleranfälliger ist: return (a < rhs.a || (a == rhs.a && (b < rhs.b || (b == rhs.b && c < rhs.c))));

    – Jon Purdy

    7. Oktober 2010 um 14:23 Uhr

  • Übrigens. seit deinem ersten if -Klausel tatsächlich zurückkehrt, es besteht keine Notwendigkeit für a else Stichwort. Gleiches gilt für den inneren Codeblock. Sie können das Wort einfach fallen lassen else in beiden Fällen.

    – Andrew Truckle

    16. Februar um 15:18 Uhr

Dies ist eine ziemlich alte Frage und folglich sind alle Antworten hier veraltet. C++11 ermöglicht eine elegantere und effizientere Lösung:

bool operator <(const MyStruct& x, const MyStruct& y) {
    return std::tie(x.a, x.b, x.c) < std::tie(y.a, y.b, y.c);
}

Warum ist das besser als zu verwenden boost::make_tuple? weil make_tuple erstellt Kopien aller Datenelemente, was kostspielig sein kann. std::tieerstellt im Gegensatz dazu nur einen dünnen Wrapper von Referenzen (den der Compiler wahrscheinlich vollständig wegoptimieren wird).

Tatsächlich sollte der obige Code nun als die idiomatische Lösung zum Implementieren eines lexikografischen Vergleichs für Strukturen mit mehreren Datenelementen betrachtet werden.

  • Erwähnenswert ist, dass der obige Code nicht funktioniert – der Operator < akzeptiert nur ein Argument. operator<(const MyStruct& rhs)

    – Aufstand

    1. Februar 2014 um 2:35 Uhr


  • @Riot Nein, der Code funktioniert einwandfrei. Es muss jedoch außerhalb definiert werden MyStruct – das ist ohnehin Best Practice.

    – Konrad Rudolf

    1. Februar 2014 um 12:11 Uhr


  • Mit large struct und c++1y können Sie eine Funktion hinzufügen auto AsTuple(const MyStruct & s) { return std::tie(s.x, s.y); }. Dadurch wird vermieden, dass die Felder der Struktur in der wiederholt werden operator<…. leider habe ich sowieso nicht gesehen, es in c++11 zu tun.

    – Renaud

    24. Juni 2015 um 12:32 Uhr


  • @Renaud In C ++ 11 können Sie ein Lambda (auto as_tuple = [](MyStruct const& s) {return std::tie(s.x, s.y);};), da dadurch der Rückgabetyp abgeleitet werden kann.

    – Konrad Rudolf

    24. Juni 2015 um 15:16 Uhr

  • @fcatho Mein Code implementiert einen lexikografischen Vergleich. Und der lexikografische Vergleich ist eine strenge schwache Ordnung, die ist antisymmetrisch und transitiv.

    – Konrad Rudolf

    28. November 2019 um 14:26 Uhr


Benutzer-Avatar
Mike Seymour

Andere haben erwähnt boost::tuple, die Ihnen einen lexikographischen Vergleich bietet. Wenn Sie es als Struktur mit benannten Elementen behalten möchten, können Sie temporäre Tupel zum Vergleich erstellen:

bool operator<(const MyStruct& x, const MyStruct& y)
{
    return boost::make_tuple(x.a,x.b,x.c) < boost::make_tuple(y.a,y.b,y.c);
}

In C++0x wird daraus std::make_tuple().

UPDATE: Und jetzt ist C++11 da, es wird std::tie(), um ein Tupel von Referenzen zu erstellen, ohne die Objekte zu kopieren. Einzelheiten finden Sie in der neuen Antwort von Konrad Rudolph.

  • Ich frage mich, wie sehr sich das Erstellen dieser Tupelobjekte auf die Leistung auswirkt.

    –Timo

    7. Oktober 2010 um 14:30 Uhr

  • @Timo: Der Aufbau und Vergleich sollen Inline sein, also wäre ich überrascht, wenn es langsamer wäre als der direkte Vergleich der Werte. Aber der einzige Weg, um sicher zu sein, ist es zu messen.

    – Mike Seymour

    7. Oktober 2010 um 14:38 Uhr

  • Dies ist immer noch gut, wenn Sie vergleichen müssen x.geta(), x.getb(), x.getc() oder andere Funktionen, die Referenzen zurückgeben. Konnte dafür keine Krawatte verwenden.

    – Johan Lundberg

    5. September 2019 um 20:06 Uhr

Benutzer-Avatar
Benoit

Ich würde dies tun:

#define COMPARE(x) if((x) < (rhs.x)) return true; \
                   if((x) > (rhs.x)) return false;
COMPARE(a)
COMPARE(b)
COMPARE(c)
return false;
#undef COMPARE

  • Genau die Art von Dingen, die nicht durch Vorlagen ersetzt werden können, weil Sie von der einschließenden Funktion zurückkehren müssen. Ein Vorschlag: ersetzen (x) > (rhs.x) mit (rhs.x) < (x) sich nur darauf verlassen operator< auf die Mitglieder. Ich denke auch, dass die Klammern überflüssig sind, ich kann nicht sehen, wie dieses Makro mit Eingaben, die sie erforderten, richtig funktionieren würde.

    – Markieren Sie Lösegeld

    7. Oktober 2010 um 15:41 Uhr

  • Ich würde das Finale ersetzen COMPARE(c); return false; mit return c < rhs.cum den irrelevanten > Vergleich zu vermeiden.

    – Christoph Johnson

    7. Oktober 2010 um 17:13 Uhr

  • Sie haben Recht. Es ist eine Frage des Kompromisses zwischen einfacher Lesbarkeit und Effizienz.

    – Benoît

    7. Oktober 2010 um 18:30 Uhr

  • wenn Ihnen die Lesbarkeit egal ist, warum dann das wenn? COMPARE(X,def) (!(rhs.x < x) && (x < rhs.x)) && def; return COMPARE(a,COMPARE(b,COMPARE(c,true))); Aber andererseits warum versuchen zu erraten, was schneller ist. Code, kompilieren, Zeit und dann möglicherweise Optimieren und lesbarer Code ist so viel einfacher zu optimieren

    – Rune FS

    8. Oktober 2010 um 8:27 Uhr

In diesem Fall können Sie verwenden boost::tuple<int, int, int> – es ist Betreiber< funktioniert genau so, wie Sie es wollen.

Ich denke, der einfachste Weg ist, bei allen Vergleichen beim <-Operator zu bleiben und > oder == nicht zu verwenden. Unten ist das Muster, dem ich folge, und Sie können für alle Ihre Strukturen folgen

typedef struct X
{
    int a;
    std::string b;
    int c;
    std::string d;

    bool operator <( const X& rhs ) const
    {
        if (a < rhs.a) { return true; }
        else if ( rhs.a < a ) { return false; }

        // if neither of the above were true then 
        // we are consdidered equal using strict weak ordering
        // so we move on to compare the next item in the struct

        if (b < rhs.b) { return true; }
        if ( rhs.b < b ) { return false; }

        if (c < rhs.c) { return true; }
        if ( rhs.c < c ) { return false; }

        if (d < rhs.d) { return true; }
        if ( rhs.d < d ) { return false; }

        // if both are completely equal (based on strict weak ordering)
        // then just return false since equality doesn't yield less than
        return false;
    }
};

  • Wozu brauchst du die Else?

    – Quittung

    5. Mai 2011 um 8:26 Uhr

  • Wirklich wie die Idee, dass der Operator < in Bezug auf sich selbst definiert werden muss.

    – ceorron

    11. August 2016 um 17:29 Uhr

Benutzer-Avatar
Gemeinschaft

Der beste Weg, den ich kenne, ist die Verwendung von a Boost-Tupel. Es bietet unter anderem einen eingebauten Vergleich und Konstruktoren.

#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_comparison.hpp>

typedef boost::tuple<int,int,int> MyStruct;

MyStruct x0(1,2,3), x1(1,2,2);
if( x0 < x1 )
   ...

Ich mag auch Mike Seymors Vorschlag, temporäre Tupel über make_tuple von boost zu verwenden

  • Wozu brauchst du die Else?

    – Quittung

    5. Mai 2011 um 8:26 Uhr

  • Wirklich wie die Idee, dass der Operator < in Bezug auf sich selbst definiert werden muss.

    – ceorron

    11. August 2016 um 17:29 Uhr

Normalerweise implementiere ich die lexikografische Ordnung auf diese Weise:

bool operator < (const MyObject& obj)
{
    if( first != obj.first ){
        return first < obj.first;
    }
    if( second != obj.second ){
        return second < obj.second;
    }
    if( third != obj.third ){
        return third < obj.third
    }
    ...
}

Wohlgemerkt, Gleitkommawerte (G++-Warnungen) müssen besonders berücksichtigt werden, für diese wäre so etwas besser:

bool operator < (const MyObject& obj)
{
    if( first < obj.first ){
        return true;
    }
    if( first > obj.first ){
        return false;
    }
    if( second < obj.second ){
        return true;
    }
    if( second > obj.second ){
        return false;
    }
    ...
}

1012320cookie-checkOperator< für eine Struktur definieren

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

Privacy policy