1

C++ でユーザー定義キーを使用したいと考えていますstd::map。キーは、最大値を持つ整数セットのバイナリ表現である2^Vため、すべての2^V可能な値を表すことはできません。これは、効率的なバイナリ セット表現、つまり の配列を使用して行いuint64_tます。

ここでの問題は、このユーザー定義のビットセットを のキーとして配置するにはstd::map、ビットセット値間の有効な比較を定義する必要がありますが、たとえば の最大サイズがある場合、V=1000比較できる数値を取得できないことです。それらをすべて集約するだけで2^1000は表現できません。

したがって、私の質問は、(ビットセット表現で正しいビットを設定することによって) 2 つの異なるセットがあり、オーバーフローするため最終的な数値を表すことができないとします。

id_1 = 2^0 + 2^1 + ... + 2^V

id_2 = 2^0 + 2^1 + ... + 2^V

比較できる値につながる適切な変換はありますか? id_1 < id_2指数関数の合計を表現可能な値に変換したいが、「未満」の不変式を維持したいと言える必要があります。たとえば、対数変換を巧妙な方法で適用して「未満」を維持するなどの方針に沿って考えていました。

次に例を示します。

set_1 = {2,3,4}; set_2 = {8}

id(set_1) = 2^2 + 2^3 + 2^4 = 28; id(set_2) = 2^8 = 256

id(set_1) < id(set_2)

完全！を持つことができる一般的なセット{1,...,V}、したがって2^V可能なサブセットはどうですか?

4

1 に答える 1

4

これは、効率的なバイナリ セット表現、つまり uint64_t の配列を使用して行います。

この配列がraキー type のデータ メンバーを介してアクセスされKey、両方の配列の長さが であると仮定するとN、次のようなコンパレータが必要になります。

bool operator<(const Key &lhs, const Key &rhs) {
    return std::lexicographical_compare(lhs.ra, &lhs.ra[N], rhs.ra, &rhs.ra[N]);
}

これは、配列がビッグエンディアンであると暗黙的に見なします。つまり、最初uint64_tのものが最も重要です。それが気に入らない場合は、Vビットを配列に格納した順序の相対的な重要性をすでに念頭に置いている可能性があるため、それで十分です。に大きな謎はないので、実装例lexicographical_compareを見て、必要に応じて変更してください。

これを「辞書順」と呼びます。uint64_t代わりに使用した事実charと、両方の配列が同じ長さであることを除けば、文字列の比較方法です[*] - 実際、の使用は重要ではありません。比較の代わりにコンパレーターでuint64_t使用できますstd::memcmp64 ビット チャンク。operator<文字列全体を整数に変換しても文字列の場合は機能しません。また、コンパレータも機能しません。

[*] ロケール固有の照合規則を導入するまで。

于 2012-10-04T10:29:40.783 に答える