Mappa non ordinata (hash) da bitset a bitset su boost

Question

Desidero utilizzare una cache, implementata da boost unordered_map, da dynamic_bitset a dynamic_bitset. Il problema, naturalmente, è che non esiste una funzione hash predefinita dal bitset. Non sembra essere un problema concettuale, ma non so come elaborare gli aspetti tecnici. Come dovrei farlo?

Answer 1

Ho trovato una soluzione inaspettata. Si scopre che boost ha un'opzione per #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS. Quando questo viene definito, i membri privati ​​incluso m_bits diventano pubblici (penso che sia lì per gestire vecchi compilatori o qualcosa del genere).

Così ora posso usare @ risposta di KennyTM, ha cambiato un po ':

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'è la funzione to_block_range che copia le parole che il bitset consiste in un buffer. Per evitare la copia effettiva, è possibile definire il proprio "output iteratore" che elabora solo singole parole e calcola l'hash da esse. Ri. come calcolare l'hash: vedi ad es. la funzione hash FNV.

Sfortunatamente, il modello di dynamic_bitset è IMHO, braindead perché non consente l'accesso diretto al buffer sottostante (nemmeno come const).

Answer 3

È un feature request.

Si potrebbe implementare un hash univoco non-così-efficiente convertendo il bitset ad un vettore temporanea:

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

Non possiamo calcolare direttamente l'hash perché i dati sottostanti dynamic_bitset è privato (m_bits)

Ma possiamo facilmente passato finezza (sovvertire!) il C++ sistema di specifica di accesso senza né

• l'hacking al codice o
• fingendo il compilatore è non conforme (BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS)

La chiave è la funzione template to_block_range che è un friend a dynamic_bitset. Le specializzazioni di questa funzione, quindi, hanno anche accesso ai suoi dati privati ​​(ad esempio m_bits).

Il codice risultante non potrebbe essere più semplice

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 soluzione proposta genera lo stesso hash nella seguente situazione.

#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 soluzione proposta a volte non è corretta per la mappa hash.

Ho letto il codice sorgente di dynamic_bitset perché è successo e ho capito che dynamic_bitset memorizza un bit per valore come a vector<bool>. Ad esempio, si chiama dynamic_bitset<> test(1, false), quindi dynamic_bitset inizialmente assegna 4 byte con zero e contiene la dimensione dei bit (in questo caso, la dimensione è 1).Notare che se la dimensione dei bit diventa maggiore di 32, assegna nuovamente 4 byte e reinseriscili in dynamic_bitsets<>::m_bits (quindi m_bits è un vettore di 4 byte-blocchi).

Se chiamo test.push_back(x), essa imposta il secondo bit di x ed aumenta la dimensione di bit da 2. Se x è falso, allora m_bits[0] non cambia affatto! Per calcolare correttamente l'hash, dobbiamo prendere m_num_bits nel calcolo dell'hash.

Quindi, la domanda è come?

1: Usa boost::hash_combine Questo approccio è semplice e diretto. Non ho controllato questa compilazione 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: lanciare m_num_bits% bit_per_block th bit. capovolgi un bit in base alla dimensione del bit. Credo che questo approccio è più veloce di 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; 
    } 
}