6

unordered_mapブーストの によって実装されたキャッシュをa から adynamic_bitsetに使用したいdynamic_bitset。もちろん問題は、ビットセットからのデフォルトのハッシュ関数がないことです。概念的な問題ではないようですが、技術的な問題を解決する方法がわかりません。どうすればいいですか？

4

5 に答える 5

6

思いがけない解決策を見つけました。ブーストにはオプションがあることがわかりました#define BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS。これが定義されると、private メンバーを含むm_bitspublic になります (古いコンパイラなどに対処するためにあると思います)。

これで、@ 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);
    }
}
于 2010-10-09T17:58:36.347 に答える
3

ビットセットを構成する単語をバッファにコピーto_block_rangeする機能があります。実際のコピーを避けるために、個々の単語を処理してそれらからハッシュを計算するだけの独自の「出力イテレータ」を定義できます。再。ハッシュの計算方法: FNV ハッシュ関数などを参照してください。

残念ながら、の設計dynamic_bitsetは私見であり、下層のバッファーに直接アクセスできないため (としてもconst)、脳死しています。

于 2010-10-09T16:32:10.423 に答える
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);
    }
}
于 2010-10-09T16:32:36.627 に答える
2

dynamic_bitsetの基になるデータは非公開であるため、ハッシュを直接計算することはできません( m_bits)

しかし、どちらも使わずに C++ アクセス仕様システムを簡単に巧みにすり抜ける (覆す!) ことができます。

  • コードのハッキングまたは
  • コンパイラが準拠していないふりをする ( BOOST_DYNAMIC_BITSET_DONT_USE_FRIENDS)

鍵はtoto_block_rangeであるテンプレート関数です。したがって、この関数の特殊化は、そのプライベート データ (つまり ) にもアクセスできます。frienddynamic_bitsetm_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;
}
}
于 2011-11-28T14:29:27.993 に答える
0

提案されたソリューションは、次の状況で同じハッシュを生成します。

#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 が と同じように値ごとに 1 ビットを格納することに気付きましたvector<bool>。たとえば、 を呼び出すdynamic_bitset<> test(1, false)と、dynamic_bitset は最初にすべてゼロの 4 バイトを割り当て、ビットのサイズを保持します (この場合、サイズは 1)。ビットのサイズが 32 を超えると、再度 4 バイトが割り当てられ、プッシュバックされることに注意してくださいdynamic_bitsets<>::m_bits(つまり、m_bits は 4 バイト ブロックのベクトルです)。

を呼び出すとtest.push_back(x)、2 番目のビットが x に設定され、ビットのサイズが 2 に増加します。xが false の場合、m_bits[0]はまったく変化しません! ハッシュを正しく計算するには、ハッシュ計算で m_num_bits を取る必要があります。

では、問題はどのように？

1: 使用するboost::hash_combine このアプローチは単純で簡単です。このコンパイルのチェックはしていません。

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: m_num_bits % bits_per_block 番目のビットを反転します。ビットサイズに基づいてビットを反転します。このアプローチは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;
    }
}
于 2016-07-13T14:43:34.083 に答える