30/09/2018, 22:32
Hỏi về code C++ như bao lần khác @@
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
Bài liên quan
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.mpnhư code trên thì kiểu dữ liệu của key làpair<int,int>, mà C++ ko có hàm hash chopair<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:
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.
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 hashconstcuối khai báo là để sử dụngoperator()được ngay cả khi object gọi nó là hằng hay r-valueC++ 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ểuintthì đa số là số nguyên 4 bytes, cònlong longđa số là số nguyên 8 bytes. Như vậy vớipair<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ọistd::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 longghé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 chompthô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ànhstd::stringrồ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