Sử dụng một unordered_map với mảng như phím

Question

Tôi không hiểu tại sao tôi không thể có một unordered_map với một array<int,3> như các loại chính:

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

tôi nhận được một lỗi dài, phần liên hệ nhất là

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

Các mảng không đủ điều kiện làm khóa vì chúng thiếu một số yêu cầu?

Answer 1

Tại sao?

Như đã đề cập trong 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).

Bây giờ theo câu hỏi của bạn, chúng tôi cần phải hash một mảng mà chưa được thực hiện trong nội bộ theo tiêu chuẩn C++.

Làm cách nào để vượt qua nó?

Vì vậy, nếu bạn muốn ánh xạ một array đến một giá trị mà bạn phải thực hiện std của riêng bạn :: băm http://en.cppreference.com/w/cpp/utility/hash mà bạn có thể nhận được một số sự giúp đỡ từ C++ how to insert array into hash set?.

Một số công trình xung quanh

Nếu bạn có thể tự do sử dụng boost sau đó nó có thể cung cấp cho bạn với băm của mảng và nhiều loại khác. Về cơ bản nó sử dụng phương pháp hash_combine mà bạn có thể xem http://www.boost.org/doc/libs/1_49_0/boost/functional/hash/hash.hpp.

Answer 2

Các lỗi liên quan là

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

Các unordered_map cần một hash của chìa khóa, và nó sẽ tìm kiếm một tình trạng quá tải của std::hash để làm điều đó. Bạn có thể mở rộng namespace std bằng hàm băm phù hợp.

Answer 3

Biên soạn với msvc14 cung cấp cho các lỗi sau:

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

Tôi đoán đây là tự giải thích.

Answer 4

Bạn phải triển khai băm. Các bảng băm tùy thuộc vào việc băm khóa, để tìm một thùng để đặt chúng vào. C++ không kỳ diệu biết cách băm tất cả các loại, và trong trường hợp cụ thể này, nó không biết cách băm một mảng 3 số nguyên theo mặc định. Bạn có thể thực hiện một cấu trúc băm đơn giản như thế này:

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

Và sau đó sử dụng nó:

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

Edit: Tôi đã thay đổi chức năng để kết hợp băm từ một xor ngây thơ, với chức năng được sử dụng bởi tăng cho mục đích này: http://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_combine_id241013.html. Điều này phải đủ mạnh để thực sự sử dụng.