問題タブ [bitvector]

O(1) 時間で動作する Bitvector32 のビット演算子があるかどうかを知りたかったのです。私は現在、大きなサイズの BitArray を使用しており、O(bitarray のサイズ) で動作する Bitwise And、Or、および Not を使用しています。

これについてインターネットで検索しましたが、答えが見つかりませんでした。ここの人々が助けてくれることを願っています！

大きなビットマップ (数メガバイト) で連続する 0 または 1 のビットをすばやく検索するのに役立つかなり高速なコードはありますか?

「かなり速い」とは、マシンのワードサイズを利用して、恐ろしく遅いビットごとの分析を行う代わりに、ワード全体を一度に比較できることを意味します（ で行うようなvector<bool>）。

たとえば、ボリュームのビットマップで空き領域を検索する場合 (デフラグなど) に非常に便利です。

この質問について考えるとき、私は、std::copy()および/またはstd::fillに特化されている（私は本当に最適化されている）かどうか疑問に思い始めstd::vector<bool>ます。

これはC++標準で必要ですか、それともC ++ stdライブラリベンダーによる一般的なアプローチですか？

簡単に言えば、次のコードがあるかどうか知りたいです。

それよりも優れている/異なる：

非常に厳密に言うと、たとえば、次のようにできます。単一ビットではなく、バイト全体std::fill<std::vector<bool>::iterator>()の内部表現に移動して設定しますか？友達をstd::vector<bool>作ることは図書館のベンダーにとって大きな問題ではないと思いますか？std::fillstd::vector<bool>

[アップデート]

次の関連する質問：私（または他の誰か:)は、まだ専門化されstd::vector<bool>ていない場合、たとえば、そのようなアルゴリズムを専門化できますか？これはC++標準で許可されていますか？これは移植性がないことはわかっていますが、選択した1つの標準C ++ライブラリだけですか？私（または他の誰か）がstd::vector<bool>プライベートパーツに到達する方法を見つけたと仮定します。

現在、ビットベクトルのエンコードにランレングス エンコーディングを使用しており、現在の実行時間は 2log(i) です。ここで、 はランのサイズです。ログ（i）にダウンさせる別の方法はありますか？ありがとう。

stlのビットベクトルとビットセットコンテナの違いは何ですか？説明してください。私の理解では、ビットセットはビットベクトルの概念の実装ですか？私は正しいですか、それとも間違っていますか？ビットベクトルを実装する他の方法は何ですか？

に裏打ちされたビットベクトルを作成しようとしていますint[]。
だから私は次のコードを持っています：

おそらく代わりに使用する必要があったことは知っていますbyte[]が、なぜこのように機能しないのか疑問に思っていました.
アイデアはint、ストリームから渡して下位 16 ビットを保持し、対応するビットを設定済みとしてマークするというものです。したがって、ベクトルを反復処理すると、数値 (下位 16 ビットで示される) が欠落していることがわかります。
しかし、私は間違った結果を得ます。だから私は私の扱いが間違っていると信じています。
何か案は？

更新:
32 ビット整数のストリームがあります。それらを読みながら、下位16ビットを使用してビットベクトルを設定することにより、欠落している数値をマークしようとします（コードが投稿されています）。
また、ストリームをもう一度読み取って、上位 16 ビットが欠落していることを見つけようとします。
したがって、欠落している数値は次のとおりです: 231719592= ( 1101110011111100001010101000) = ( 3535- 49832) ストリームを読み取る49832と、欠落している下位ビットとして取得されませんが、65536

アップデート2:

私は得る：

BitVector32 の動作に少し困惑しています。テストを参照してください。

これはパスします。つまり、最初のビットは 1 に設定されます (テストによると)。ただし、ToString メソッドを実行すると、「BitVector32{0000000000000000000000000000000}」が返されます。

不足しているものはありますか？

前もって感謝します！

z3を使用して式を削除しようとしています

これはに等しい

このコードによって：

次のような結果を取得したい：

ただし、結果は次のとおりです。

誰かが私を助けてくれませんか？

これは、主にパックされた表現がブール値へのポインタを返すことを妨げるため、標準のコンテナ要件を満たさないことはよく知られています。std::vector<bool>T* x = &v[i]

私の質問は、reference_proxyがaddress-ofをオーバーロードしoperator&てpointer_proxyを返すときに、これを修正/軽減できるかどうかです。

ポインタプロキシには、ほとんどの実装でreference_proxyと同じデータ、つまり、パックされたデータへのポインタと、ポイントされたブロック内の特定のビットを分離するためのマスクを含めることができます。次に、pointer_proxyを間接参照すると、reference_proxyが生成されます。基本的に、両方のプロキシは「ファット」ポインタですが、ディスクベースのプロキシコンテナと比較すると、依然としてかなり軽量です。

代わりに、T* x = &v[0]を実行してauto x = &v[0]、問題なく使用できxますif(*x)。私も書けるようになりたいですfor(auto b: v) { /* ... */ }

質問：そのようなマルチプロキシアプローチはSTLのアルゴリズムで機能しますか？xまたは、一部のアルゴリズムは、実際に必要な要件に本当に依存していますbool*か？または、これが機能しないようにするために必要な連続したユーザー定義の変換が多すぎますか？上記の実装スケッチを完全に完成させる前に、そのような障害のいずれかを知りたいと思います。

更新（@HowardHinnantの回答とcomp.std.c ++に関するこの古代の議論に基づく）

組み込みのタイプをほぼ模倣するのに長い道のりがあります。任意のタイプTについて、reference_proxy :: operator＆（）とiterator_proxy :: operator *という意味で、プロキシのペア（reference_proxyとiterator_proxyなど）を相互に整合させることができます。 （）はお互いの逆です。

ただし、ある時点で、プロキシオブジェクトをマップしてT *またはT＆のように動作させる必要があります。イテレータプロキシの場合、すべての機能を再実装せずに、operator->（）をオーバーロードして、テンプレートTのインターフェイスにアクセスできます。ただし、参照プロキシの場合は、operator。（）をオーバーロードする必要があります。これは、現在のC ++では許可されていません（ただし、SebastianRedlはBoostCon2013でそのような提案を提示しました）。参照プロキシ内の.get（）メンバーのように詳細な回避策を作成するか、参照内にTのすべてのインターフェイスを実装できます（これはvector :: bit_referenceに対して行われることです）が、これにより組み込み構文が失われます。または、型変換のセマンティクスが組み込まれていないユーザー定義の変換を導入します（引数ごとに最大で1つのユーザー定義の変換を行うことができます）。

おそらくご存知のとおり、C ++ 98vector<bool>スペシャライゼーションは、ブール値をブール変数ではなくビットとして格納します。vector<bool>C ++にはビットへのポインタと参照がないため、の要素はアドレス指定できません。これに対する回避策はありますか、明らかな落とし穴（私は気づいていないようです）があり、そうしようとしても実用的ですか？