unordered_map với cặp là khóa - không biên dịch

Question

Tôi đang cố gắng tạo một unordered_map để ánh xạ cặp với số nguyên.

#include <unordered_map> 

using namespace std; 
using Vote = pair<string, string>; 
using Unordered_map = unordered_map<Vote, int>; 

Tôi có một lớp học mà tôi đã khai báo Unordered_map là thành viên riêng tư.

Tuy nhiên, tôi nhận được lỗi này khi tôi cố gắng biên dịch:

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: Implicit instantiation of undefined template 'std::__1::hash<std::__1::pair<std::__1::basic_string<char>, std::__1::basic_string<char> > >' 

tôi không nhận được lỗi này nếu tôi sử dụng một bản đồ thông thường như map<pair<string, string>, int> thay vì một unordered_map.

Không thể sử dụng pair làm khóa trong bản đồ không có thứ tự?

Answer 1

Bạn cần cung cấp một hàm băm phù hợp cho loại khóa của bạn. Một ví dụ đơn giản:

#include <unordered_map> 
#include <functional> 
#include <string> 
#include <utility> 

// Only for pairs of std::hash-able types for simplicity. 
// You can of course template this struct to allow other hash functions 
struct pair_hash { 
    template <class T1, class T2> 
    std::size_t operator() (const std::pair<T1,T2> &p) const { 
     auto h1 = std::hash<T1>{}(p.first); 
     auto h2 = std::hash<T2>{}(p.second); 

     // Mainly for demonstration purposes, i.e. works but is overly simple 
     // In the real world, use sth. like boost.hash_combine 
     return h1^h2; 
    } 
}; 

using namespace std; 
using Vote = pair<string, string>; 
using Unordered_map = unordered_map<Vote, int, pair_hash>; 

int main() { 
    Unordered_map um; 
} 

này sẽ làm việc, nhưng không có các hash-thuộc tính tốt nhất ^†. Bạn có thể muốn xem một cái gì đó như boost.hash_combine để có kết quả chất lượng cao hơn khi kết hợp các băm.

Để sử dụng trong thế giới thực: Boost cũng cung cấp chức năng thiết lập hash_value đã cung cấp hàm băm cho std::pair, cũng như std::tuple và hầu hết các vùng chứa tiêu chuẩn.

---

^† Chính xác hơn, nó sẽ tạo ra quá nhiều xung đột. Ví dụ: mọi cặp đối xứng sẽ băm thành 0 và các cặp khác nhau chỉ bằng cách hoán vị sẽ có cùng giá trị băm. Điều này có lẽ là tốt cho bài tập lập trình của bạn, nhưng có thể làm tổn thương nghiêm trọng hiệu suất của mã thế giới thực.

Answer 2

Khi lỗi biên dịch của bạn cho biết, không có phiên âm hợp lệ của std::hash<std::pair<std::string, std::string>> trong không gian tên std của bạn.

Theo biên dịch của tôi:

Lỗi C2338 C++ chuẩn không cung cấp một hash cho loại này. c: \ program files (x86) \ visual studio microsoft 14.0 \ vc \ include \ xstddef 381

Bạn có thể cung cấp chuyên môn của riêng bạn cho std::hash<Vote> như sau:

#include <string> 
#include <unordered_map> 
#include <functional> 

using namespace std; 
using Vote = pair<string, string>; 
using Unordered_map = unordered_map<Vote, int>; 

namespace std 
{ 
    template<> 
    struct hash<Vote> 
    { 
     size_t operator()(Vote const& v) const 
     { 
      // ... hash function here ... 
     } 
    }; 
} 

int main() 
{ 
    Unordered_map m; 
} 

Answer 3

Cách ưa thích của tôi để giải quyết vấn đề này là xác định hàm key biến đổi cặp của bạn thành một số nguyên duy nhất (hoặc bất kỳ loại dữ liệu có thể băm nào). Khóa này không phải là khóa băm. Đây là ID duy nhất của cặp dữ liệu sau đó sẽ được băm tối ưu theo số unordered_map. Ví dụ, bạn muốn xác định một unordered_map loại

unordered_map<pair<int,int>,double> Map; 

Và bạn muốn sử dụng Map[make_pair(i,j)]=value hoặc Map.find(make_pair(i,j)) để hoạt động trên bản đồ. Sau đó, bạn sẽ phải thông báo cho hệ thống cách băm một cặp số nguyên make_pair(i,j).Thay vào đó, chúng ta có thể xác định

inline size_t key(int i,int j) {return (size_t) i << 32 | (unsigned int) j;} 

và sau đó thay đổi các loại bản đồ để

unordered_map<size_t,double> Map; 

Bây giờ chúng ta có thể sử dụng Map[key(i,j)]=value hoặc Map.find(key(i,j)) để hoạt động trên bản đồ. Mỗi make_pair giờ đây sẽ gọi hàm nội tuyến key.

Phương pháp này đảm bảo rằng khóa sẽ được băm tối ưu, vì bây giờ phần băm được thực hiện bởi hệ thống, sẽ luôn chọn kích thước bảng băm bên trong là nguyên tố để đảm bảo mỗi nhóm đều có khả năng giống nhau. Nhưng bạn phải đảm bảo 100% chắc chắn rằng key là duy nhất cho mỗi cặp, nghĩa là, không có hai cặp riêng biệt nào có thể có cùng một khóa hoặc có thể có các lỗi rất khó tìm.

Answer 4

Đối với cặp khóa, chúng tôi có thể sử dụng chức năng thúc đẩy cặp băm:

#include <iostream> 
#include <boost/functional/hash.hpp> 
#include <unordered_map> 
using namespace std; 

int main() { 
    unordered_map<pair<string, string>, int, boost::hash<pair<string, string>>> m; 

    m[make_pair("123", "456")] = 1; 
    cout << m[make_pair("123", "456")] << endl; 
    return 0; 
} 

Tương tự như vậy chúng ta có thể sử dụng tăng băm cho vectơ,

#include <iostream> 
#include <boost/functional/hash.hpp> 
#include <unordered_map> 
#include <vector> 
using namespace std; 

int main() { 
    unordered_map<vector<string>, int, boost::hash<vector<string>>> m; 
    vector<string> a({"123", "456"}); 

    m[a] = 1; 
    cout << m[a] << endl; 
    return 0; 
}