Rückwärts-Suche in std::unordered_map (C++11)



  • Hallo.

    in einem privaten C++11 Großprojekt (Schach Engine) habe ich aktuell den Fall, dass ich eine bestehende unordered_map quasi rückwärts durchsuchen müsste.
    Das soll heißen, dass ich die Value habe und den Key der unordered_map für diesen einzigartigen Wert brauche.

    Meine Frage ist nun ob es da eine peformantere Lösung gibt als durch die gesammte unordered_map zu iterieren, bis ich den entsprechenden Wert gefunden habe.

    Liebe Grüße

    ZaHaDum1984





  • Eine möglichkeit wäre eine zweite map zu haben, welche das mapping value -> key von der ersten map macht.

    Nachteile sind, das die werte in 2 datenstrukturen gehalten und synchronisiert werden müssen und der mehr an Speicherverbrauch.



  • theta schrieb:

    Boost.Bimap?

    Nein, ganz bestimmt nicht.
    Ich persönlich halte gar nichts von der Boost-Library. Außerdem bietet Boost.Bitmap nicht die konstante Zugriffszeit der std::unordered_map.

    firefly schrieb:

    Eine möglichkeit wäre eine zweite map zu haben, welche das mapping value -> key von der ersten map macht.

    Nachteile sind, das die werte in 2 datenstrukturen gehalten und synchronisiert werden müssen und der mehr an Speicherverbrauch.

    Generell wäre das kein Problem, da die unordered_map konstant ist. Allerdings fände ich diese Lösung, wegen der von dir angeführten Gründe, eher unschön.


  • Mod

    ZaHaDum1984 schrieb:

    theta schrieb:

    Boost.Bimap?

    Nein, ganz bestimmt nicht.
    Ich persönlich halte gar nichts von der Boost-Library.

    Ziemlich blamable Meinung.

    Außerdem bietet Boost.Bitmap nicht die konstante Zugriffszeit der std::unordered_map.

    Siehe http://www.boost.org/doc/libs/1_45_0/boost/bimap/unordered_set_of.hpp.

    PS: Hash tables haben nur armotisiert konstante Zugriffszeit.

    ZaHaDum1984 schrieb:

    Allerdings fände ich diese Lösung, wegen der von dir angeführten Gründe, eher unschön.

    "Unschön" ist völlig subjektiv. Wir haben Vor- und Nachteile für diese Lösung, und die Nachteile sind scheinbar irrelevant. Was ist daran unschön?

    ~
    edit durch SeppJ: Ich habe mal deinen Link repariert.~



  • Arcoth schrieb:

    Siehe http://www.boost.org/doc/libs/1_45_0/boost/bimap/unordered_set_of.hpp.

    unordered_map und unordered_set sind nicht das Gleiche. std::unordered_map hat konstante Zugriffszeit, std::unordered_set eben nicht.
    Außerdem ist die URL unvollständig.

    Arcoth schrieb:

    "Unschön" ist völlig subjektiv. Wir haben Vor- und Nachteile für diese Lösung, und die Nachteile sind scheinbar irrelevant. Was ist daran unschön?

    Kennst du ein alternatives Wort für unschön, dass nicht fälschlicher Weise als Beleidigung verstanden werden könnte? 😉
    Unschön daran ist natürlich, dass ich die gleichen ca. 100 Paare zweimal eingeben muss, nur am effizient in beide Richtungen suchen zu können. Da passt das Aufwand-Nutzen-Verhältnis einfach nicht, ganz abgesehen vom "schlechten Stil".

    Ich finde es jedenfalls sehr bedauerlich, dass die so lang erwarteten Hashtabellen anscheinend die einzigen Container in C++11 sind die keine Möglichkeit zur Rückwärts-Suche besitzen.



  • ZaHaDum1984 schrieb:

    Unschön daran ist natürlich, dass ich die gleichen ca. 100 Paare zweimal eingeben muss, nur am effizient in beide Richtungen suchen zu können. Da passt das Aufwand-Nutzen-Verhältnis einfach nicht, ganz abgesehen vom "schlechten Stil".

    Wiso die paare zwei mal eingeben?
    Man kann die 2. map aus der ersten zur laufzeit generieren lassen (keine garantie das der code übersetzbar ist):

    for (auto& pair: firstMap)
    {
        secondMap.insert(std::make_pair(pair.second, pair.first));
    }
    

  • Mod

    ZaHaDum1984 schrieb:

    Arcoth schrieb:

    Siehe http://www.boost.org/doc/libs/1_45_0/boost/bimap/unordered_set_of.hpp.

    unordered_map und unordered_set sind nicht das Gleiche. std::unordered_map hat konstante Zugriffszeit, std::unordered_set eben nicht.

    Das ist alles falsch. unordered_set ist (in aller Regel, wenn der Programmierer nicht total dumm ist) implementiert als ein Set mit set_key = pair<map_key, map_value> (und einer Hashfunktion, die nur den key-Teil vom pair nimmt). unordered_map hat genausowenig wie unordered_set eine konstante Zugriffszeit, sondern nur eine im Durchschnitt konstante Zugriffszeit. unordered_set hat genau die gleiche Zugriffszeit wie unordered_map.

    Unschön daran ist natürlich, dass ich die gleichen ca. 100 Paare zweimal eingeben muss, nur am effizient in beide Richtungen suchen zu können. Da passt das Aufwand-Nutzen-Verhältnis einfach nicht, ganz abgesehen vom "schlechten Stil".

    Wieso doppelt eingeben? Hast du noch nie zwei Datenstrukturen zu einer gemeinsamen Struktur zusammengefasst?


Anmelden zum Antworten