Unordered (hash map) from bit set to bit set with increasing

Question

I want to use the cache implemented by boost unordered_map, from dynamic_bitsetto dynamic_bitset. The problem, of course, is that there is no default hash function from the bit set. This does not seem like a conceptual problem, but I do not know how to develop a technique. How should I do it?

Answer 1

I found an unexpected solution. It turns out boost has the ability #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS. When this is determined, private members, including those m_bitsbecome publicly available (I think that there is an issue with old compilers or something like that).

, @KennyTM, :

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

to_block_range, , . , " ", . : ., , - FNV.

, dynamic_bitset - IMHO, braindead, ( const).

Answer 3

.

, :

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

, dynamic_bitset (m_bits)

(!) ++

• , (BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS)

to_block_range, friend dynamic_bitset. , (.. m_bits).

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

.

#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!

-.

dynamic_bitset, , , dynamic_bitset vector<bool>. , dynamic_bitset<> test(1, false), dynamic_bitset 4 ( 1). : 32, 4 dynamic_bitsets<>::m_bits ( m_bits - 4 ).

test.push_back(x), x 2. x - false, m_bits[0] ! , m_num_bits -.

: ?

1: use boost::hash_combine This approach is simple and simple. I did not check this compiler or not.

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 th bits. flip the bits according to the size of the bits. I believe this approach is faster than 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;
    }
}