Ungeordnete (Hash) Karte von Bitset zu Bitset auf Boost

Question

Ich möchte einen Cache verwenden, implementiert von Boost unordered_map, von einem dynamic_bitset zu einem dynamic_bitset. Das Problem besteht natürlich darin, dass es vom Bitset keine Standard-Hash-Funktion gibt. Es scheint nicht wie ein konzeptionelles Problem zu sein, aber ich weiß nicht, wie ich die technischen Details ausarbeiten soll. Wie soll ich das machen?

Answer 1

Ich fand eine unerwartete Lösung. Es stellt sich heraus, Boost hat eine Option auf #define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS. Wenn dies definiert ist, werden private Mitglieder einschließlich m_bits öffentlich (ich denke, es ist da, um mit alten Compilern oder etwas zu tun).

So, jetzt ist @ KennyTM Antwort verwenden kann, ein wenig verändert:

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

Es gibt to_block_range Funktion, die Kopien aus den Wörtern, aus denen das Bitset besteht in einige Puffer. Um das tatsächliche Kopieren zu vermeiden, könnten Sie einen eigenen "Ausgabe-Iterator" definieren, der nur einzelne Wörter verarbeitet und daraus Hashwerte berechnet. Re. wie man Hash berechnet: siehe z.B. die FNV-Hash-Funktion.

Leider ist das Design von dynamic_bitset IMHO, braindead, weil es Ihnen keinen direkten Zugriff auf den zugrunde liegenden Puffer gibt (nicht einmal als const).

Answer 3

Es ist ein feature request.

Man könnte eine nicht-so-effizienten eindeutigen Hash-Implementierung durch die bitset auf einen Vektor Konvertierung temporär:

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

Wir können nicht direkt den Hash berechnen, da die zugrunde liegenden Daten in dynamic_bitset privat (m_bits)

Aber wir können leicht Finesse Vergangenheit (unterminieren!) die Zugriffsspezifikationssystem ++ c ohne entweder

• auf den Code-Hacking oder
• vorgibt Ihr Compiler nicht-konforme (BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS)

Der Schlüssel ist die Template-Funktion to_block_range, die eine friend zu dynamic_bitset ist. Spezialisierungen dieser Funktion haben daher auch Zugriff auf ihre privaten Daten (d. H. m_bits).

könnte Der resultierende Code nicht

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

die vorgeschlagene Lösung erzeugt den gleichen Hash in der folgenden Situation einfacher sein.

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

Die vorgeschlagene Lösung ist manchmal für Hash-Karte nicht geeignet.

Ich lese den Quellcode von dynamic_bitset, warum dies passiert ist und erkannte, dass dynamic_bitset ein Bit pro Wert wie vector<bool> speichert. Beispiel: Sie rufen dynamic_bitset<> test(1, false) auf, dann weist dynamic_bitset zunächst 4 Bytes mit Null zu und es enthält die Größe von Bits (in diesem Fall ist die Größe 1).Beachten Sie, dass, wenn die Größe der Bits größer als 32 wird, es erneut 4 Bytes zuweist und es zurück in dynamic_bitsets<>::m_bits (also m_bits ist ein Vektor von 4 Byte-Blöcken) schieben.

Wenn ich test.push_back(x) nennen, setzt es das zweite Bit auf x und erhöht die Größe von Bits 2. Wenn x falsch ist, dann ist m_bits[0] nicht ändern! Um den Hash korrekt zu berechnen, müssen wir m_num_bits in der Hash-Berechnung verwenden.

Dann ist die Frage, wie?

1: Verwenden Sie boost::hash_combine Dieser Ansatz ist einfach und unkompliziert. Ich habe das nicht überprüft oder nicht.

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_bit% bit_per_block th bit. kippen ein Bit basierend auf der Bitgröße. Ich glaube, dieser Ansatz ist schneller als 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; 
    } 
}