Wie platziert man Objekte, die in einem C++ std :: set nicht vergleichbar zu sein scheinen?

Question

Angenommen, ich möchte Objekte, die einen Server identifizieren, in eine stl set einfügen. Dann würde ich dafür sorgen, dass ich auch umzusetzen operator< für diese Objekte sonst würde ich in einen Compiler-Fehler führen:

struct ServerID 
{ 
    std::string name; // name of the server 
    int port; 
}; 

std::set<ServerID> servers; // compiler error, no operator< defined 

Dies ist nur ein Beispiel für ein weit verbreitetes Problem ist, wo ich eine Aufgabe vergleichbar machen will.

Meine aktuelle Lösung geht in der Regel wie folgt aus:

bool operator< (const ServerID & lhs, const ServerID & rhs) 
{ 
    if (lhs.name != rhs.name) 
    { 
    return lhs.name < rhs.name; 
    } 
    else 
    { 
    return lhs.port < rhs.port; 
    } 
} 

Dies ist nur eine Lösung, die ich mir selbst gefunden. Aber ich vermute, dass dieses Problem auch in der Informatik erkannt wurde. Wenn ich Glück habe, gibt es dafür eine bessere Lösung. Kann mir jemand dazu sagen?

Answer 1

Ich würde empfehlen, nicht als Operator < implementieren, um mögliche Verwirrung zu vermeiden, sondern übergeben Sie die Auftragsfunktion als Parameter auf die std :: set Vorlage Argument.

struct server 
{ 
    std::string name; 
    int port; 
}; 
struct name_then_port : public std::binary_function<server,server,bool> 
{ 
    bool operator()(server const & lhs, server const & rhs) { 
     // using litb approach (more efficient as it does not call both < and == on strings: 
     int cmp = lhs.name.compare(rhs.name); 
     return (cmp < 0) || ((cmp==0) && (lhs.port < rhs.port)); 
    } 
}; 
struct port_then_name : public std::binary_function<server,server,bool> 
{ 
    bool operator()(server const & lhs, server const & rhs) { 
     return (lhs.port < rhs.port) || ((lhs.port==rhs.port) && (lhs.name<rhs.name)); 
    } 
}; 
int main() 
{ 
    std::set< server, name_then_port > servers; // or: 
    std::set< server, port_then_name > servers2; 
} 

Über die Frage, ob dieses Problem zuvor identifiziert wurde, hat es. Die allgemeine Lösung ist genau das, was Sie gepostet haben: lexicographical order. Der Begriff wird normalerweise als String-Reihenfolge bezeichnet, die Reihenfolge ist jedoch dieselbe: nimm das erste Element, vergleiche, wenn es keine Reihenfolge definiert, nimm das nächste Datenelement und wiederhole es.

Answer 2

Am Ende des Tages, müssen Sie einfach eine Vergleichsfunktion, die Ihre unmittelbaren Bedürfnisse erfüllt. Dies kann schwierig sein - zum Beispiel, wie würden Sie zwei Bitmaps unterschiedlicher Größe vergleichen?

Answer 3

Ihre ist die kanonische Lösung. Ich bin mir nicht sicher, wie du es vielleicht auf eine bessere Weise machen würdest.

Um dies zu erweitern, wenn Sie n Mitglieder in Ihrer Klasse haben, werden Sie feststellen, dass Sie einige dieser Felder vergleichen müssen, um eine strenge Bestellung zu etablieren. Es gibt keinen wirklichen Weg dahin, obwohl Sie vielleicht finden, dass es möglich ist, die Vergleichsfunktion besser zu machen (in Bezug auf die durchschnittliche Komplexität), wenn Sie die Vergleiche so ordnen, dass diejenigen, die eher zum Erfolg beitragen der Vergleich wird zuerst kommen. Dies hilft, den Vergleich schneller zu beenden.

Eine Möglichkeit, die unter bestimmten Umständen helfen kann (wenn Sie feststellen, dass die Leistung von Vergleichen dominiert wird) ist, einen "Sortierschlüssel" einzurichten - Strings zu vergleichen kann teuer sein. Ein Sortierschlüssel ist eine Ganzzahl, die für einen schnellen Vergleich der Objekte verwendet werden kann. Wenn der Sortierschlüssel weniger als vergleicht, dann würde der String auch tun.

In Ihrem Fall könnte ein einfacher Sortierschlüssel die Binärdarstellung der Zeichenfolgen als Ganzzahlen behandeln - dies hat übrigens viele Fehler - und dann die ganzen Zahlen anstelle der Zeichenfolgen vergleichen.

In Windows kann die LCMapString-Funktion verwendet werden, um auf diese Weise einen Sortierschlüssel für Zeichenfolgen zu erstellen. Ich denke, dass Sie dann eine schnelle Funktion wie memcmp verwenden können, um die Zeichenfolgen anstelle eines langsameren Zeichenfolgenvergleichs zu vergleichen. Dies ist sinnvoller, wenn Sie Vergleiche ohne Berücksichtigung der Groß- und Kleinschreibung oder die Verwendung aller Unicode-Zeichen durchführen und nach ihren Regeln korrekte Vergleiche durchführen möchten.

Answer 4

Wenn alles, was Sie brauchen, eine gute Ordnung ist, und Ihnen egal ist, was die Reihenfolge ist, dann ist Ihre Lösung in Ordnung.

Answer 5

Ich schreibe es in der Regel als:

return x.name < y.name || 
     x.name == y.name && x.port < y.port; 

..., die Sie auch weiterhin für so viele Mitgliedsvariablen erweitern Sie haben. Diese Lösung wird so schnell wie möglich kurzgeschlossen und eliminiert Verzweigungen.

Beachten Sie, dass hierfür operator< für jede der Mitgliedsvariablen definiert werden muss, was eine gute Sache ist, die sowieso außerhalb dieser Routine implementiert wurde.

Answer 6

Ich neige dazu, den Operator < innerhalb der Struktur zu setzen, um die Dinge sauberer zu halten, aber sonst haben Sie genau das, was ich habe.

Answer 7

In diesem Fall, wenn die Reihenfolge keine Rolle spielt, möchten Sie möglicherweise den Port vor der Zeichenfolge aufgrund der Kosten eines Zeichenfolgenvergleichs vergleichen.

Answer 8

Ihre Lösung ist so ziemlich der richtige Weg. Ihre Vergleichsfunktion sollte so eingerichtet sein, dass sie jeden Server eindeutig identifiziert (was das tatsächlich bedeutet, hängt von Ihrem Anwendungsfall ab), daher ist der Vergleich von Name/Port wahrscheinlich ausreichend.

Wenn Sie wissen, dass Sie nicht zwei Server mit demselben Namen, aber anderen Ports haben (oder Sie möchten diese gleich behandeln), können Sie diesen Teil Ihrer Vergleichsfunktion löschen. Ein realistischeres Beispiel wäre, wenn Sie mehr Mitglieder in Ihrem Server-Objekt hätten, die nicht mit der Identität des Servers selbst zu tun hätten (z. B. ein "Last-Request" -Cache); In diesem Fall möchten Sie wahrscheinlich nicht, dass Ihr Set anhand dieses Felds unterscheidet, also würden Sie es nicht in Ihre Vergleichsfunktion aufnehmen. OTOH, das ist vielleicht nicht das beste Design für das Serverobjekt.

Wenn Sie die Frage "Wann sollten zwei Server (Objekte) als identisch betrachtet werden?" dann brauchst du vielleicht gar kein Set mehr.

Answer 9

würde ich string::compare

bool operator< (const ServerID & lhs, const ServerID & rhs) { 
    int lcr = lhs.name.compare(rhs.name); 
    return lcr < 0 || (lcr == 0 && lhs.port < rhs.port); 
} 

verwenden, wenn es keinen Sinn macht Sie es vergleichbar haben, und die einzige Verwendung, das wäre es in die set zu stopfen, können Sie einen Funktor verwenden

struct ServerIdCompare { 
    bool operator()(const ServerID & lhs, const ServerID & rhs) const { 
    int lcr = lhs.name.compare(rhs.name); 
    return lcr < 0 || (lcr == 0 && lhs.port < rhs.port); 
    } 
}; 

std::set<ServerID, ServerIdCompare> servers; 

Wenn Sie den Operator jedoch eine unabhängige (nicht functor verwenden) wie oben, dann stellen auch <=, ==, >= und != es konsistent zu halten.