Использование неупорядоченной карты с массивами в качестве ключей

Я не понимаю, почему я не могу иметь unordered_map с array<int,3> в качестве типа ключа: 

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

Я получаю длинную ошибку, наиболее уместной частью которой является 

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

Массивы не могут быть ключами, потому что они пропускают некоторые требования?

4 8
c++ c++11 unordered-map

4 ответа:

Но почему?

Как упоминалось в http://www.cplusplus.com/reference/unordered_map/unordered_map/

Внутри, элементы в unordered_map не сортируются ни в одном определенный порядок относительно их ключевых или отображенных значений, но организованы в ведра в зависимости от их хэш-значений, чтобы обеспечить быстрый доступ к отдельным элементам непосредственно по их ключевым значениям (с постоянная средняя временная сложность в среднем).

Теперь в соответствии с вашим вопросом нам нужно hash массив, который не был реализован внутренне в стандартном c++.

Как с этим покончить?

Поэтому, если вы хотите сопоставить array значению, вы должны реализовать свой собственный std:: hash http://en.cppreference.com/w/cpp/utility/hash для чего вы могли бы получить некоторую помощь от C++ как вставить массив в хэш-набор?.

Некоторые обходят

Если вы свободны использовать boost, то он может предоставить вам хеширование массивов и многих других типов. Он в основном использует метод hash_combine, для которого вы можете посмотреть на http://www.boost.org/doc/libs/1_49_0/boost/functional/hash/hash.hpp .

8

Соответствующая ошибка равна

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

unordered_map требуется хэш ключа, и для этого он ищет перегрузку std::hash. Вы можете расширить namespace std с помощью подходящей хэш-функции.

8

Вы должны реализовать хэш. Хэш-таблицы в зависимости от хеширования ключа, чтобы найти ведро, чтобы положить их в него. C++ волшебным образом не знает, как хэшировать каждый тип, и в данном конкретном случае он не знает, как хэшировать массив из 3 целых чисел по умолчанию. Вы можете реализовать простую хэш-структуру следующим образом: 

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

И затем использовать его: 

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

Edit: я изменил функцию для объединения хэшей с наивного xor на функцию, используемую boost для этой цели: http://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_combine_id241013.html. Это должно быть достаточно надежна, чтобы на самом деле использовать.

6

, скомпилированный с msvc14, выдает следующую ошибку:

" стандарт C++ не предоставляет хэш для этого типа."

Я думаю, это само собой разумеется.

2