Desordenada (hash) map from bitset to bitset on boost

Question

Quiero usar una memoria caché, implementada por boost unordered_map, desde dynamic_bitset hasta dynamic_bitset. El problema, por supuesto, es que no hay una función hash predeterminada del conjunto de bits. No parece ser un problema conceptual, pero no sé cómo resolver los aspectos técnicos. ¿Cómo debo hacer eso?

Answer 1

He encontrado una solución inesperada. Resulta que boost tiene una opción para #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS. Cuando esto se define, los miembros privados que incluyen m_bits se hacen públicos (creo que está ahí para tratar con compiladores antiguos o algo así).

Así que ahora puedo utilizar @ respuesta de KennyTM, cambiado un poco:

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

Hay to_block_range función que copia las palabras que el conjunto de bits consiste en un búfer. Para evitar la copia real, puede definir su propio "iterador de salida" que solo procesa palabras individuales y calcula el hash de ellas. Re. cómo calcular el hash: ver p. la función hash FNV.

Desafortunadamente, el diseño de dynamic_bitset es en mi humilde opinión, braindead porque no le da acceso directo al búfer subyacente (ni siquiera como const).

Answer 3

Es un feature request.

Se podría implementar un control único, no tan eficiente mediante la conversión de la bitset a un vector temporal:

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

No podemos calcular directamente el hash debido a que los datos subyacentes en dynamic_bitset es privada (m_bits)

Pero podemos fácilmente pasado finura (subvertir!) ++ c sistema de especificación de acceso sin que ninguna de

• la piratería en el código o
• pretendiendo que el compilador no es conforme (BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS)

La clave es la función de plantilla to_block_range que es un friend a dynamic_bitset. Las especializaciones de esta función, por lo tanto, también tienen acceso a sus datos privados (es decir, m_bits).

El código resultante no puede ser más sencillo

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

la solución propuesta genera el mismo hash en la siguiente situación.

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

la solución propuesta a veces es incorrecta para el hash map.

Leí el código fuente de dynamic_bitset por qué sucedió esto y me di cuenta de que dynamic_bitset almacena un bit por valor igual que vector<bool>. Por ejemplo, llame al dynamic_bitset<> test(1, false), luego dynamic_bitset inicialmente asigna 4 bytes con todo cero y contiene el tamaño de bits (en este caso, el tamaño es 1).Tenga en cuenta que si el tamaño de los bits pasa a ser mayor que 32, entonces asigna 4 bytes nuevamente y lo vuelve a insertar en dynamic_bitsets<>::m_bits (entonces m_bits es un vector de 4 bloques de bytes).

Si llamo a test.push_back(x), establece el segundo bit en x y aumenta el tamaño de los bits a 2. Si x es falso, entonces m_bits[0] no cambia en absoluto! Para calcular correctamente hash, necesitamos tomar m_num_bits en cálculo hash.

Entonces, la pregunta es ¿cómo?

1: Use boost::hash_combine Este enfoque es simple y directo. No revisé esta compilación o no.

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 bit. voltear un poco según el tamaño del bit. Creo que este enfoque es más rápido que 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; 
    } 
}