Korzystanie unordered_map z tablicami jak klucze

Question

Nie rozumiem, dlaczego nie mogę mieć unordered_map z array<int,3> jako typ klucza:

#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; 
} 

Dostaję dużo błędów, najbardziej istotna część bycia

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; 
    ^

Czy tablice nie są kluczami, ponieważ nie spełniają pewnych wymagań?

Answer 1

Dlaczego?

Jak wspomniano w 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).

Teraz jak na swoje pytanie, musimy hash przez tablicę, która nie został wdrożony wewnętrznie w standardowej C++.

Jak z tym skończyć?

Więc jeśli chcesz mapować array do wartości trzeba zaimplementować własną std :: hash http://en.cppreference.com/w/cpp/utility/hash, dla których można uzyskać pomoc od C++ how to insert array into hash set?.

Niektóre prace wokół

Jeśli jesteś wolny, aby korzystać z boost to może dostarczyć mieszaja tablic i wielu innych typów. Zasadniczo stosuje się metodę hash_combine, dla której można spojrzeć na http://www.boost.org/doc/libs/1_49_0/boost/functional/hash/hash.hpp.

Answer 2

Odpowiedni błąd jest

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

unordered_map potrzebuje hash klucza, i wygląda na przeciążenia std::hash to zrobić. Możesz przedłużyć namespace std za pomocą odpowiedniej funkcji skrótu.

Answer 3

Zestawione z msvc14 daje następujący błąd:

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

to chyba oczywiste.

Answer 4

Musisz zaimplementować skrót. Tabele skrótu w zależności od hashowania klucza, aby znaleźć łyżkę do wstawienia. C++ nie magicznie wie, jak zaszyfrować każdy typ, aw tym konkretnym przypadku nie wie, jak zaszyfrować tablicę 3 liczb całkowitych domyślnie. Można zaimplementować prostego skrótu struct tak:

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; 
    } 
}; 

a następnie użyć go:

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

Edit: Zmieniłem funkcję łączenia mieszań od naiwnej xor, do funkcji używanych przez impuls dla w tym celu: http://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_combine_id241013.html. Powinno to być wystarczająco mocne, aby można było z niego korzystać.