eine unordered_map mit Arrays als Schlüssel

Question

Ich verstehe nicht verwenden, warum ich nicht ein unordered_map mit einem array<int,3> als Schlüsseltyp haben:

#include <unordered_map> 

using namespace std; 

int main() { 

    array<int,3> key = {0,1,2}; 

    unordered_map< array<int,3> , int > test; 
    test[key] = 2; 

    return 0; 
} 

ich einen langen Fehler, die relevantesten Teil

sein

main.cpp:11:9: error: no match for ‘operator[]’ (operand types are std::unordered_map<std::array<int, 3ul>, int>’ and ‘std::array<int, 3ul>’) 
test[key] = 2; 
    ^

Sind Arrays nicht für Schlüssel geeignet, weil sie einige Anforderungen nicht erfüllen?

Answer 1

Warum?

erwähnt Wie in http://www.cplusplus.com/reference/unordered_map/unordered_map/

Internally, the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values (with a constant average time complexity on average).

Jetzt wie pro Ihre Frage, die wir hash ein Array benötigen, die in Standard-C-intern nicht implementiert wurde ++.

Wie komme ich damit klar?

So möchten, wenn Sie einen array auf einen Wert ordnen Sie Ihre eigenen std implementieren müssen :: Hash http://en.cppreference.com/w/cpp/utility/hash, für die Sie etwas Hilfe von C++ how to insert array into hash set? bekommen könnte.

Einige arbeiten um

Wenn Sie frei sind zu verwenden boost dann kann es Ihnen mit Hashing von Arrays und viele andere Arten zur Verfügung stellen. Es verwendet im Wesentlichen hash_combine Methode, für die Sie http://www.boost.org/doc/libs/1_49_0/boost/functional/hash/hash.hpp betrachten können.

Answer 2

Der entsprechende Fehler ist

error: no match for call to '(const std::hash<std::array<int, 3ul> >) (const std::array<int, 3ul>&)'

Die unordered_map einen Hash des Schlüssels muss, und es sieht für eine Überlastung von std::hash, das zu tun. Sie können die namespace std mit einer geeigneten Hash-Funktion erweitern.

Answer 3

mit msvc14 Zusammengestellt gibt den folgenden Fehler:

"The C++ Standard doesn't provide a hash for this type."

Ich denke, das ist selbsterklärend.

Answer 4

Sie müssen einen Hash implementieren. Hashtabellen abhängig vom Hashing des Schlüssels, um einen Bucket zu finden, in den sie eingefügt werden können. C++ weiß nicht, wie man jeden Typ hasht, und in diesem speziellen Fall weiß es nicht, wie man standardmäßig ein Array von 3 Ganzzahlen hasht.

struct ArrayHasher { 
    std::size_t operator()(const std::array<int, 3>& a) { 
     std::size_t h = 0; 

     for (auto e : a) { 
      h ^= std::hash<int>{}(e) + 0x9e3779b9 + (h << 6) + (h >> 2); 
     } 
     return h; 
    } 
}; 

Und dann verwenden: Sie können eine einfache Hash-Struktur wie folgt implementieren

unordered_map< array<int,3> , int, ArrayHasher > test; 

Edit: ich die Funktion geändert für von Boost verwendet Hashes von einem naiven xor, auf die Funktion Kombination für dieser Zweck: http://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_combine_id241013.html. Dies sollte robust genug sein, um tatsächlich zu verwenden.