Suchen Sie nach unordered_map-Elementen, indem Sie nach den Werten der Schlüsselstrukturelemente suchen

Question

Meine Anwendung hat eine Karte wie std::unordered_map<my_struct *, std::string> mit Dutzenden von Tausenden Elementen. my_struct hat einige Zeichenketten, Vektoren und andere Arten Mitglieder.

In einem Schritt muss ich ein neues my_struct erstellen und dann nach dem Map-Element suchen, das als Schlüssel my_struct die gleichen Member-Werte wie in meinem neu erstellten Objekt hat.

Nur so konnte ich es funktionierte mit einem zusätzlichen numerischen "ID" Mitglied und std::hash mit benutzerdefinierten Prädikat ersetzen, die es nur von seiner operator() Methode zurückgibt. Dies ist jedoch keine Lösung. Es gibt keine Möglichkeit, diese ID zu erkennen, wenn ich nach einem Element der Karte suche.

Dies ist der Testcode I (test_key = my_struct) schrieb:

#include <unordered_map> 
#include <string> 
#include <iostream> 

struct test_key 
{ 
     std::size_t id; //can't exist in my application 
     std::string test_str1; 
     std::string test_str2; 
     unsigned int test_uint; 

     test_key(std::size_t id_, std::string test_str1_, std::string test_str2_, unsigned int test_uint_) 
       : id(id_), test_str1(test_str1_), test_str2(test_str2_), test_uint(test_uint_) 
     {} 
}; 

struct test_key_hasher 
{ 
     std::size_t operator() (test_key* const& tst_k) const 
     { 
       return tst_k->id; 
     } 
}; 


int main() 
{ 
     std::unordered_map<test_key *, std::string, test_key_hasher> values; 
     test_key *tst_k1, *tst_k2, *tst_k3, *tst_k4, *tst_lk; 

     tst_k1 = new test_key(1, "something 11", "something 12", 1112); 
     tst_k2 = new test_key(2, "something 21", "something 22", 2122); 
     tst_k3 = new test_key(3, "something 31", "something 32", 3132); 
     tst_k4 = new test_key(4, "something 41", "something 42", 4142); 

     values.emplace(tst_k1, "first thing"); 
     values.emplace(tst_k2, "second thing"); 
     values.emplace(tst_k3, "third thing"); 
     values.emplace(tst_k4, "fourth thing"); 

     tst_lk = new test_key(3, "something 31", "something 32", 3132); //there is no way I could know ID 3 here 

     std::cout << values[tst_lk] << std::endl; //Expected output: third thing 

     delete tst_k1; 
     delete tst_k2; 
     delete tst_k3; 
     delete tst_k4; 
     delete tst_lk; 
} 

ich auch, dass es key_equal für mein eigenes Prädikat ersetzen auf unordered_map Konstruktor dachte lösen könnte, aber das funktioniert auch nicht (I keine Werte der Karte als Ausgabe erhalten). Der key_equal Ersatz Prädikat ich geschrieben habe, ist:

struct test_key_comp 
{ 
     bool operator() (test_key* const& tst_k1, test_key* const& tst_k2) const 
     { 
       //debug 
       std::cout << tst_k1->test_str1 << " == " << tst_k2->test_str1 << " ?" << std::endl; 

       return tst_k1->test_str1 == tst_k2->test_str1 
         && tst_k1->test_str2 == tst_k2->test_str2 
         && tst_k1->test_uint == tst_k2->test_uint; 
     } 
}; 

Dann meine Karte wie std::unordered_map<test_key *, std::string, std::hash<test_key *>, test_key_comp> aussah.

Der obige Code gibt mir Ausgabe folgende wenn test_key_comp anstelle von Standard mit key_equal:

something 21 == something 11 ? 
something 31 == something 11 ? 

Sieht aus wie es auf den ersten Element stoppt ...

erste Ausgangsleitung ist sehr seltsam, wie es scheint auch wenn ich nicht versuche, irgendein Element zu finden oder darauf zuzugreifen (Kommentar std::cout Zeile auf main()).

Ich habe auch versucht, find() Methode, aber das Ergebnis ist das gleiche wie operator[] und at().

Frage: Irgendwelche Ratschläge, warum es nicht funktioniert und wie soll ich es kodieren, um das zu bekommen, was ich schnell und effizient machen will?

Ich möchte vermeiden, durch alle Elemente zu durchlaufen, weil es viele von ihnen (Dutzende von Tausenden ...) haben wird, und das scheint nicht der effizienteste und schnellste Weg zu sein.

Zusätzliche Frage: Vielleicht sollte ich eine Zeichenfolge aus test_key Mitglieder Werte als der Schlüssel für die Karte verwenden? Ich weiß, dass das einfacher zu programmieren wäre, aber wäre es effizienter und schneller? Reale Implementierung von test_key/my_struct haben std::map<std::string, std::string> s, std::vector<std::string> s und viele Mitglieder anderer Typen (bereits viel Arbeit, um zwei dieser Strukturen zu vergleichen) und alles in eine einzige Zeichenfolge setzen wäre schwer zu bauen und zu analysieren .. Ich weiß, dass ich es benchmarken muss, aber ich würde gerne ein paar Hinweise bekommen.

Answer 1

Sie möchten etwas in einer Hash-Karte effizient nach etwas anderem als dem Hash suchen? So arbeiten sie nicht.

Sie müssen eine andere Datenstruktur auswählen - eine, die nach etwas sortieren kann, nach dem Sie suchen möchten.Es könnte entweder eine eigenständige Datenstruktur sein oder eine parallele Datenstruktur - möglicherweise zu Ihrer ungeordneten_Map, aber Sie müssen etwas haben, das nach dem organisiert ist, nach dem Sie suchen möchten, oder Sie werden eine erschöpfende Suche durchführen.