メモリ アクセスが予想よりもやや遅いのはなぜかと考えていたところ、Visual C++ の実装にはdeque実際に組み込みのインダイレクション層があり、メモリ ローカリティが破壊されていることがわかりました。
つまり、 の配列でT*はなく、 の配列を保持しているようですT。
この「機能」を持たない VC++ で使用できる別の実装はありますか、またはこの実装でそれを回避できる (可能性は低いと思いますが) 方法はありますか?
私は基本的vectorに、前面に O(1) プッシュ/ポップもある を探しています。
私はそれを自分で実装できると思いますが、allocators などを扱うのは面倒で、正しくするのに時間がかかるので、可能であれば以前に作成/テストされたものを使用したいと思います。
なんらかの理由で、少なくとも MSVC 2010 の時点では、std::deque実装は信じられないほど小さいブロック サイズ (最大 16 バイトまたは 1 つの要素が間違っていなければ 1 つです!) を使用しているようです。
私の経験では、これは非常に重大なパフォーマンスの問題を引き起こす可能性があります。基本的に、データ構造の各「ブロック」は単一の要素のみを格納することになり、あらゆる種類の追加のオーバーヘッド (時間とメモリ) につながるからです。
なぜこのようにされているのかわかりません。私が理解している限り、dequeこのような小さなブロックサイズで を設定することは、まさにそれが行われるべきではない方法です。
gcc stdlib実装を確認してください。メモリからは、はるかに大きなブロック サイズが使用されます。
編集:他の問題に対処するために:
std::deque 間接的な層を追加する必要があります。多くの場合、「ブロックされた」データ構造として実装されます。つまり、各ノード自体がデータ要素の配列である「ノード」の配列を格納します。リンクされたリストのようなものではありません - ノードの配列は、リストのように「トラバース」されることはなく、常に直接インデックスが付けられます (ブロックごとに 1 つの要素の場合でも)。
もちろん、先頭に余分なスペースを保持する独自のデータ構造をロールすることもできます。最悪の場合の動作はしないため、コンテナO(1) push/pop front/backの要件を満たしません。std::dequeでも、それさえ気にしなければ…
C++ 標準ではstd::deque、前面または背面へのプッシュで再割り当てを行うことは許可されていません。これらの操作は常に一定時間です。常に、償却されません。
C++ 標準には、そのようなコンテナーはありません。Boost には、私の知る限りではありません ( Boost.Containerライブラリにはあると思いますが、調べていません)。
あなたが不平を言う間接化は、参照/ポインターが/ /によって無効にされないという標準要件によって実際に義務付けられています(明らかに、削除された要素への参照/ポインターを除きます)。pushpop frontback
したがって、この要件は複雑さの要件とは何の関係もないことがわかります。
この間接化により、利用可能なスペースがない場合でも、高速化push front(ただし、O(サイズ) のまま)backが可能になります。