std::tr1::unordered_map



  • Hallo!

    Zwei Fragen zur unordered_map.

    1.) Wo genau ist der Unterschied zwischen der std::map und der std::tr1::unordered_map?

    • die std::tr1::unordered_map hat glaube ich schnellere Einfüge-/Suchoperationen, oder?

    2.) Warum kann ich "eigene" String-Klasse nicht verwenden?

    • Ich erhalte beim Einfügen - siehe unten - immer folgenden Fehler: error C2440: 'type cast' : cannot convert from 'const String<T>' to 'size_t'

    Mit std::string geht es.



  • Hallo!

    Also Frage 2 hat sich erledigt. Ich musste einfache eine eigene Hash-Klasse schreiben, die den Operator

    size_t operator()(const _Kty & _Keyval) const
    

    für meinen Typ implementiert.



  • ad 1) eine std::map ist nach Keys geordnet und meist als red-black tree implementiert.
    eine std::tr1::unordered_map dagegen hat keine vorgeschriebene Ordnung, und meist als hash-map implementiert.

    daraus folgt dass ein lookup in einer std::tr1::unordered_map im normalfall O(1) ist, in einer std::map dagegen O(log N). insert kann ich dir nicht auswendig sagen, wird schätze ich bei beiden amortisiert O(log N) sein. kannst du aber alles bei z.b. wikipedia nachlesen, wenn du nach red-black tree und hash-map suchst.

    bzw. guck einfach im standard/tr1 bzw. einer aktuellen C++ referenz nach.



  • HaJo. schrieb:

    Hallo!

    Also Frage 2 hat sich erledigt. Ich musste einfache eine eigene Hash-Klasse schreiben, die den Operator

    size_t operator()(const _Kty & _Keyval) const
    

    für meinen Typ implementiert.

    Ich habe genau das gleiche Problem! Und zwar versuche ich ein std::pair als Key in einer std::unordered_map abzuspeichern. Da meckert der Compiler immer mit

    error C2440: 'Typumwandlung': 'const std::pair<_Ty1,_Ty2>' kann nicht in 'size_t' konvertiert werden

    Kann mir jemand helfen und beispielhaft zeigen wie man so eine Hash-Klasse zeigt.



  • Für eine Hash-Map benötigst du auch eine geeignete Hash-Funktion, die aus den Schlüsseln (in deinem Fall das pair<X,Y>) eine ganze Zahl ermittelt. Ich bin mir nicht sicher, was die Default-Hashfunktion da verwendet, aber offenbar liefert std::pair<> die Info nicht von sich aus.



  • CStoll schrieb:

    Für eine Hash-Map benötigst du auch eine geeignete Hash-Funktion, die aus den Schlüsseln (in deinem Fall das pair<X,Y>) eine ganze Zahl ermittelt. Ich bin mir nicht sicher, was die Default-Hashfunktion da verwendet, aber offenbar liefert std::pair<> die Info nicht von sich aus.

    Kannst du mir auch sagen wie die Signatur dieser Methode aussehen muss?

    Und wo schreibt man die Methode rein? Soll das ein Member von std::pair sein? Von unordered_map? Oder soll sie einfach irgendwo im Programm stehen?

    Steh leider völlig auf dem Schlauch 😞



  • Auf Anhieb kann ich das leider nicht sagen, aber wie ich die STL kenne, kannst du dort einen Funktor zusammenbauen, der sich darum kümmert:

    struct pair_hash : public unary_function<size_t, pair<X,Y> >
    {
      size_t operator() (const pair<Y,X>&) const
      {
        // mach was
      }
    };
    
    unordered_map<pair<X,Y>,wert,pair_hash> my_map;
    

    (ohne Garantie)


Log in to reply