Các bác có ai giải thích cho e mấy dòng code sau đây đc ko ạ :3
struct HASH{
size_t operator()(const pair<int,int>&x)const{
return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
}
};
unordered_map<pair<int,int>,int,HASH>mp;
Nếu được thì ai cho e tài liệu cx được ạ :3 đa tạ các bác trước
This post was flagged by the community and is temporarily hidden.
trong unordered_map<key_t, value_t> thì mỗi key được chuyển thành 1 số, quá trình chuyển này gọi là hash. Giá trị hash này sẽ xác định vị trí của cặp (key,value) trong unordered_map.
mp như code trên thì kiểu dữ liệu của key là pair<int,int>, mà C++ ko có hàm hash cho pair<int,int>, nên phải viết hàm hash riêng.
struct HASH được gọi là functor, vì nó chỉ có nhiệm vụ như 1 hàm:
HASH h;
size_t hashValue = h(pair);
và để struct HASH “bắt chước” như 1 hàm thì ta overload toán tử (). Mở ngoặc đóng ngoặc trong C++ cũng là 1 toán tử, giống như toán tử cộng trừ nhân chia vậy.
size_t operator()(const pair<int,int>&)const
toán tử overload: operator()
kiểu trả về: size_t, là số nguyên không dấu, 4 bytes hay 8 bytes tùy môi trường.
tham số: const pair<int,int>&, là pair<int,int> mà chúng ta cần hash
const cuối khai báo là để sử dụng operator() được ngay cả khi object gọi nó là hằng hay r-value
C++ ko có hash cho pair<int,int>, nhưng có hash đầy đủ cho các kiểu số nguyên như char, short, int, long long. Với kiểu int thì đa số là số nguyên 4 bytes, còn long long đa số là số nguyên 8 bytes. Như vậy với pair<int,int>, ta có thể ghép 2 số nguyên 4 bytes lại thành 1 số nguyên 8 bytes, rồi gọi std::hash<long long> cho số nguyên 8 bytes này là được. Cách ghép thì đơn giản dịch bit của số nguyên 4 bytes thứ hai sang trái 32 bit, rồi XOR cho số nguyên 4 byte đầu tiên. Bit 0-31 của số nguyên thứ nhất trở thành bit 0-31 của số nguyên 8 bytes, bit 0-31 của số nguyên thứ hai trở thành bit 32-63 của số nguyên 8 bytes. Ghép như vậy để tránh trùng hash value, ví dụ (1,10) với (10,1) nếu lấy hash là tổng 2 số nguyên thì 2 cặp này có hash giống hệt nhau, ko ổn lắm. Với cách ghép dịch bit kia thì 2 số nguyên ko số nào đụng số nào, bảo đảm nếu cặp số khác nhau thì giá trị long long ghép được sẽ khác nhau.
có được functor xử lý hash cho pair<int,int> rồi thì chỉ còn bỏ nó vào khai báo kiểu cho mp thôi. Nếu ko thích hash kiểu ghép dịch bit thì bạn có thể chế ra cách khác, ví dụ chuyển cặp số thành std::string rồi gọi hash cho string cũng được, nhưng chuyển thành chuỗi lâu hơn là ghép dịch bit.
This post was flagged by the community and is temporarily hidden.
đúng rồi đó. Đơn giản là vậy. Mình viết dông dài quá 
giải thích đến tận lông luôn :v
Thường thì người ta sẽ viết với template nữa.
xl h e mới rep đc ạ :’( tks các đại ca :3
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?