Bản đồ không có thứ tự (băm) từ bitet tới bitet khi tăng

Question

Tôi muốn sử dụng bộ nhớ cache, được thực hiện bởi số unordered_map của boost, từ dynamic_bitset đến dynamic_bitset. Vấn đề, tất nhiên, là không có hàm băm mặc định từ bitet. Nó không có vẻ giống như một vấn đề khái niệm, nhưng tôi không biết làm thế nào để làm việc ra các technicalities. Tôi nên làm như thế nào?

Answer 1

Tôi tìm thấy một giải pháp bất ngờ. Nó chỉ ra tăng có một tùy chọn để #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS. Khi điều này được xác định, các thành viên riêng bao gồm m_bits trở thành công khai (tôi nghĩ rằng nó có để đối phó với trình biên dịch cũ hoặc một cái gì đó).

Vì vậy, bây giờ tôi có thể sử dụng @ câu trả lời KennyTM của, thay đổi một chút:

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {    
     return boost::hash_value(bs.m_bits); 
    } 
} 

Answer 2

Có to_block_range chức năng các bản sao ra các từ mà bitet bao gồm trong một số bộ đệm. Để tránh sao chép thực tế, bạn có thể định nghĩa "trình lặp đầu ra" của riêng bạn mà chỉ xử lý các từ riêng lẻ và tính toán băm từ chúng. Re. cách tính băm: xem ví dụ hàm băm FNV.

Thật không may, thiết kế dynamic_bitset là IMHO, braindead vì nó không cho phép bạn truy cập trực tiếp vào bộ đệm cơ bản (không phải là const).

Answer 3

Đây là số feature request.

Người ta có thể thực hiện một băm độc đáo không mấy hiệu quả bằng cách chuyển đổi các bitset để một vector tạm thời:

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) { 
     std::vector<B, A> v; 
     boost::to_block_range(bs, std::back_inserter(v)); 
     return boost::hash_value(v); 
    } 
} 

Answer 4

Chúng tôi không thể trực tiếp tính toán băm vì dữ liệu cơ bản trong dynamic_bitset là tin (m_bits)

Nhưng chúng ta có thể dễ dàng vượt qua quá khứ (lật đổ!) hệ thống đặc tả truy cập C++ mà không cần

• hack vào mã hoặc
• giả vờ trình biên dịch của bạn không phù hợp (BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS)

Điều quan trọng là mẫu chức năng to_block_range mà là một friend để dynamic_bitset. Do đó, các chuyên ngành của chức năng này cũng có quyền truy cập vào dữ liệu cá nhân của nó (ví dụ: m_bits).

Các mã kết quả không thể đơn giản hơn

namespace boost { 


// specialise dynamic bitset for size_t& to return the hash of the underlying data 
template <> 
inline void 
to_block_range(const dynamic_bitset<>& b, size_t& hash_result) 
{ 
    hash_result = boost::hash_value(bs.m_bits); 
} 

std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) 
{    
    size_t hash_result; 
    to_block_range(bs, hash_result); 
    return hash_result; 
} 
} 

Answer 5

các giải pháp đề xuất tạo ra băm cùng trong tình huống sau đây.

#define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS 

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) {    
     return boost::hash_value(bs.m_bits); 
    } 
} 

boost::dynamic_biset<> test(1,false); 

auto hash1 = boost::hash_value(test); 

test.push_back(false); 

auto hash2 = boost::hash_value(test); 

// keep continue... 

test.push_back(false); 

auto hash31 = boost::hash_value(test); 

// magically all hash1 to hash31 are the same! 

giải pháp được đề xuất đôi khi không phù hợp với bản đồ băm.

Tôi đọc mã nguồn của dynamic_bitset tại sao điều này xảy ra và nhận ra rằng dynamic_bitset lưu trữ một bit cho mỗi giá trị giống như vector<bool>. Ví dụ, bạn gọi dynamic_bitset<> test(1, false), sau đó dynamic_bitset ban đầu phân bổ 4 byte với tất cả số không và nó giữ kích thước của các bit (trong trường hợp này, kích thước là 1).Lưu ý rằng nếu kích thước của các bit lớn hơn 32, thì nó phân bổ 4 byte một lần nữa và đẩy nó trở lại vào dynamic_bitsets<>::m_bits (vì vậy m_bits là một vectơ của 4 khối byte).

Nếu tôi gọi test.push_back(x), nó đặt bit thứ hai thành x và tăng kích thước bit thành 2. Nếu x là sai, thì m_bits[0] không thay đổi gì cả! Để tính toán băm chính xác, chúng ta cần lấy m_num_bits trong tính toán băm.

Sau đó, câu hỏi là như thế nào?

1: Sử dụng boost::hash_combine Cách tiếp cận này đơn giản và dễ hiểu. Tôi không kiểm tra biên dịch này hay không.

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) { 
     size_t tmp = 0; 
     boost::hash_combine(tmp,bs.m_num_bits);   
     boost::hash_combine(tmp,bs.m_bits); 
     return tmp; 
    } 
} 

2: flip m_num_bits% bits_per_block bit thứ. lật một chút dựa trên kích thước bit. Tôi tin rằng phương pháp này nhanh hơn 1.

namespace boost { 
    template <typename B, typename A> 
    std::size_t hash_value(const boost::dynamic_bitset<B, A>& bs) { 
     // you may need more sophisticated bit shift approach. 
     auto bit = 1u << (bs.m_num_bits % bs.bits_per_block); 
     auto return_val = boost::hash_value(bs.m_bits); 

     // sorry this was wrong 
     //return (return_val & bit) ? return_val | bit : return_val & (~bit); 
     return (return_val & bit) ? return_val & (~bit) : return_val | bit; 
    } 
}