12

これは、主にパックされた表現がブール値へのポインタを返すことを妨げるため、標準のコンテナ要件を満たさないことはよく知られています。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つのユーザー定義の変換を行うことができます）。

4

2 に答える 2

7

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

libc++は実際にこれを行います。

#include <vector>
#include <cassert>

int main()
{
    std::vector<bool> v(1);
    std::vector<bool>::pointer pb = &v[0];
    assert(*pb == false);
    *pb = true;
    assert(v[0] == true);
    std::vector<bool>::const_pointer cbp = pb;
    assert(*cbp == true);
    v[0] = false;
    assert(*cbp == false);
}

それは、と同じタイプを模倣する方法で拡張さconst_pointerれます。これは、libc++の非準拠の拡張機能です。ただし、インスタンス化される可能性のあるジェネリックコードを作成すると、コンパイルして正しく動作する可能性がはるかに高くなります。const_referencevector<int>vector<bool>

質問：そのようなマルチプロキシアプローチはSTLのアルゴリズムで機能しますか？または、一部のアルゴリズムは、xが実際のブール値*である必要があるという要件に本当に依存していますか？または、これが機能しないようにするために必要な連続したユーザー定義の変換が多すぎますか？

libc++のすべてのアルゴリズムは。で動作しvector<bool>ます。それらのいくつかは非常に素晴らしいパフォーマンスを持っています。特に1つのアルゴリズムには、標準では残念ながら義務付けられていない特別な処理が必要です。

#include <vector>
#include <cassert>

int main()
{
    std::vector<bool> v(1);
    bool b = true;
    assert(v[0] == false);
    assert(b == true);
    std::swap(b, v[0]);
    assert(v[0] == true);
    assert(b == false);
}

これは、実装が非常に簡単に実行できます。swapとの任意の組み合わせで機能することを確認する必要がboolありvector<bool>::referenceます。しかし、libc ++以外の実装がこれを行うかどうかはわかりません。また、C++11では義務付けられていません。

ビットの配列は素晴らしいデータ構造です。ただし、残念ながら、C++標準では十分に指定されていません。libc ++は、これが非常に便利で高性能なデータ構造になり得ることを示すために、やや無法者になりました。将来のC++標準が、C++プログラマーの利益のためにこの方向に移行する可能性があることを期待しています。

于 2013-02-26T01:49:40.247 に答える
1

オフハンド私が最初に言うのは、*reference_typeがT*の左辺値であるという標準要件に公式に準拠していないため、実際には個々のSTL実装の詳細に依存するということです。したがって、潜在的な実装の問題に関して：

The main reason any piece of code would be explicitly dependent on the container's pointer being a real bool* is if the algo was using pointer arithmetic, in which case the size of the pointer type becomes relevant. Pointer arithmetic though would bypass the iterator interface and thus defeat the main purpose of the whole STL container-by-iterator design. std::vector<> itself is guaranteed to be contiguous in C++11, which allows optimized specializations of both STL algos and compiler for(:), both of which may use pointer arithmetic internally. If your type isn't derived from std::vector then that shouldn't be an issue; everything should just assume the iterator method instead.

でも！ STLコードは、ポインター演算の目的ではなく、他の目的でポインターを受け取る場合があります。この場合、問題はC++構文です。たとえば、あなた自身の質問を引用します：

代わりにT* x = &v[0]それを行うことができますauto x = &v[0]

STL内のテンプレート化されたコードも同じことを行う必要があります...そして、STL実装がを広く利用することは現時点ではまったくありそうにないようですauto。STLが巧妙なr値キャストのトリックを実行しようとして、参照型の不一致を予期していないために失敗する状況が他にもある可能性があります。

についてfor(auto b: v) { /* ... */ }：うまくいかない理由はわかりません。15分（またはそれ以下）で自分でロールできる同じバージョンよりもはるかに効率の悪いコードが生成されると思います。あなたが組み込み関数について言及しているので、私はそれを持ち出すだけですOPで、パフォーマンスに関する考慮事項を実装します。組み込み関数を使用しても、それを支援することはできません。ビットの配列を順番にトラバースするための単純なビット単位のシフトを何とか超えて、本質的にできることは何もありません。追加されるオーバーヘッドのほとんどは、コンパイラーがコードを生成してイテレーターポインターとマスク値を更新し、次の反復でマスク値を再ロードすることによるものです。あなたがやろうとしていることを魔法のように推測して、それをあなたのためのシーケンシャルシフト操作に変えることはできません。正直なところ、私の経験に基づいて非常に懐疑的ですが、ループの外側のレジスタにそれをキャッシュすることによって、少なくともポインタの更新と書き戻しの段階を最適化できる可能性があります。

比較のために、ビットを最初から最後まで通過する1つの方法を次に示します（ビットストリームの任意のポイントで開始できるバージョンでは、少し余分なセットアップロジックが必要になります）。

uint64_t* pBitSet   = &v[-1];   // gets incremented on first iteration through loop.
uint64_t  curBitSet =  v[0];

for (int i=0; i<v.length(); ++i)  {
    if ((i % 64) == 0) {
       curBitSet = *(++pBitSet);
    }
    int bit = curBitSet & 1;
    curBitSet >>= 1;

    // do stuff based on 'bit' here.
}
于 2012-12-31T22:03:07.397 に答える