Operatorüberladung von C++ STL-Map mit benutzerdefinierten Klassen

Question

Ich habe Zweifel hinsichtlich der Verwendung von STL-Map in C++. Ich weiß, dass ich Map mit benutzerdefinierten Klassen verwende. Ich muss den Operator "<" überladen, um die Map zu erstellen. Aber wie definiere ich es sinnvoll? Zum Beispiel habe ich den folgenden Code

#include <iostream> 
#include <map> 
using namespace std; 

struct box{ 
    int e,s,w; 
    box(): e(-1), s(-2), w(-3) 
    {} 

     bool operator< (const box& lhs) const 
     { 
      return e < lhs.e; 
     } 

}; 

int main() { 
    // your code goes here 
    map<box, int> hashtable; 
    box b; 
    hashtable[b] = 1; 
    return 0; 
} 

Hier habe ich die sehr trivialer < Betreiber überlastet. Ich könnte es auch wie folgt überladen haben

bool operator< (const box& lhs) const 
{ 
    return w+s+e < lhs.e+lhs.s+lhs.w; 
} 

Und es gibt andere Möglichkeiten auch. Also meine Frage ist, hat dies die Überlastung von < Operator, beeinflussen Sie die Suche, löschen Sie den Zeitpunkt des Zugriffs auf die Elemente in der Karte. Ich meine, wirkt sich das auf Hashing eines Teils der Karten aus. Wenn ja, was ist der beste Weg, um < Betreiber zu überlasten.

Mein einziges Motiv ist hier, Paare von Box und int (siehe in der Hauptfunktion) zu speichern, so dass ich sie in O (log (n)) Zeit zugreifen kann.

UPDATE

ich dachte, dass ein beschissenes Komparator hat keinen Einfluss auf den Zugriff, die Zeit der Karten löschen, sondern eine Auswirkung auf die Tasten in der Karte vorhanden sind. Zum Beispiel, wenn mein Komparator wurde nach dem

bool operator< (const box& lhs) const 
{ 
    return e < lhs.e; 
} 

und läßt nun sagen, dass mir zwei Tupel (e, s, w) als (1,2,3) und (1,3,4). Ich möchte es in die obige Karte einfügen. Jetzt, weil ich Komparator habe, der ausschließlich auf der Grundlage des Wertes von "e" bestimmt, wird es das zweite Tupel ablehnen. Also wird die Map endlich die (1,2,3) und nicht die anderen Tupel enthalten.

Der beste Weg, um einen Komparator zu schreiben, ist std::tie, wie von @edgar in der angenommenen Antwort vorgeschlagen.

bool operator< (const box& lhs) const 
{ 
    return std::tie(e,w,s) < std::tie(lhs.e,lhs.w,lhs.s); 
} 

In dieser zwei Tupel sind unterschiedlich, auch wenn die Tupel unterschiedliche Reihenfolge haben. Das hatte ich in meiner Frage gefordert. Zum Beispiel (1,2,3) ist anders als (2,1,3). Hätte ich mit dem Komparator folgenden

bool operator< (const box& lhs) const 
{ 
    return e+w+s < lhs.e+lhs.w+lhs.s; 
} 

Wieder nur das erste Tupel es gemacht hätte, weil beide diese Tupel gleiche Summe, also wieder keinen guter Komparator.

Answer 1

Also meine Frage ist, tut dies, von < Betreiber Überlastung, Einfluss auf die suchen, löschen Zeit der Elemente in der Karte zugreifen.

Nein, es ist garantiert, dass Such-, Lösch- und Zugriffselemente in logarithmischer Zeit ausgeführt werden.

Ich meine, hat es Einfluss Hashing Teil der Karten.

std :: map ist nicht std :: unordered_map, so gibt es hier kein Hashing.

Wenn ja, was ist der beste Weg zur Überlastung < Betreiber.

Ich nehme an, dass der normale Weg, jetzt ist std::tie zu verwenden:

bool operator<(const box& lhs) const 
{ 
    return std::tie(e, s, w) < std::tie(lhs.e, lhs.s, lhs.w); 
} 

Answer 2

std::map ist keine Hash-Map, es ist ein Binärbaum.

operator< wird jedesmal aufgerufen, wenn auf den Baum zugegriffen wird, einmal für jeden Suchschritt. Daher beeinflusst offensichtlich die Komplexität davon die Leistung (Overhead beiseite, die Kosten von beispielsweise einem Lookup in einem std::map sind proportional zu den Kosten von operator<).

std::unordered_map ist eine Hash-Map. Aber dafür müssen Sie und std::equal_to<box> implementieren (Hashing und Gleichheitsfunktionen). operator< wird in diesem Fall nicht verwendet.