問題タブ [deque]

2つの違いは何ですか？つまり、方法はすべて同じです。したがって、ユーザーにとっては、同じように機能します。

あれは正しいですか？？

今、ジョスティスのSTLの本を読んでいます。

私の知る限り、c++ vector は再割り当て可能な c-array です。それで、 push_back() の後にすべてのイテレータと参照が無効になる理由を理解しています。

しかし、私の質問は std::deque に関するものです。私が知っているように、それは大きなブロックの配列です（c配列のc配列）。したがって、push_front() は最初に要素を挿入し、スペースがない場合、deque は新しいブロックを割り当て、割り当てられたブロックの最後に要素を配置します。

真ん中の insert() の後、すべての参照とイテレータが無効になり、その理由がわかりました - すべての要素が移動されます。しかし、「... push_back() および push_front() の後、すべての参照は有効なままですが、イテレータはそうではありません」というフレーズを本当に誤解しています (同じフレーズは @ standard:23.2.2.3 で見つかります)。

どういう意味ですか？！参照が有効な場合、deque はその要素を再割り当て (== 移動) できませんでした。では、なぜ反復子が無効になるのでしょうか? 非移動要素の挿入後にそれらを使用できないのはなぜですか? それとも、begin() または end() とオーバーフローに対するイテレータの等価性について確信が持てないということですか?

また、ererase() の後、すべてのイテレータと参照が有効なままであることにも言及したいと思います (消去されたものを除く:-))。

PS: 「標準」形式で回答しないでください: 「標準でそう言っているので使用できません」。なぜ、何が起こるのかを理解したい。

HerbSutter の記事Gotw 54を参照して、彼は次のように説明しています。

1. ベクターまたは両端キューを「縮小して合わせる」正しい方法と

2. ベクターまたは両端キューを完全にクリアする正しい方法

container.resize() 上記のタスクにandを使用できますcontainer.clear()か、それとも何か不足していますか?

これは、SMPシステムの割り込みハンドラーで実行する必要があるため、ロックフリーである必要があります。鍵が取れません。

いくつかの値を保持する連続した配列があります。この配列の一部のエントリは「フリー」であり、占有されていません。これらのエントリのリストを作成して、すばやく割り当てることができるようにします。ただし、任意のエントリを割り当てる必要がある場合があります。

したがって、次のことが適切な方法であることがわかります。連続する配列は、値だけでなく、左右のポインターも保持するため、両端キューが作成されます。有効な左/右ポインタを持つのは空き値のみです。dequeへの単なるインデックスアクセスであるため、任意のノードにすばやくアクセスできます。

さて、その核心に：比較的効率的で、任意のノードの削除をサポートできる優れたロックフリーの両端キューアルゴリズムはありますか？

私には次のシナリオがあります：整数のペア（本質的にはタスクの説明）でコンテナーを埋めることになっている単一のスレッドがあり、これから要素を取得する必要がある多数のワーカースレッド（8〜16）がありますコンテナといくつかの作業を実行します。

この問題は、キューをブロックすることで簡単に解決できると思いました。たとえば、アイテムの削除、スレッドはキューへのアクセスを同期し、利用可能なデータがない場合はスリープします。

私は（おそらく間違って）このようなものがSTLまたはブーストに存在するはずだと思いましたが、何も見つかりませんでした。

私は実際にそれを自分で実装する必要がありますか？そのような一般的なシナリオのようです...

Java にはDequeというクラスがあり、これに似たものを .NET (C#) で見つけたいと思います。

これが必要な理由は、コレクションの最後の項目を覗いてから、コレクションの最初の項目をデキューする必要があるためです。

ありがとう、AJラビンディラン。

私は何を間違っていますか？

http://www.cppreference.com/wiki/stl/deque/insertを参照として使用して、特定の場所で両端キューに値を挿入していました。

たとえば、deque A が次の場合:

d を指すイテレータを使用すると、次のことができます。

iter はまだ d を指しています。ただし、 iter が g を指す場合、最後の要素:

しかし iter は f を指すようになりました!!

私の現在の回避策は次のとおりです。

私はこれをもう一度テストしたことはありません。バグを追跡するのに非常に多くの時間を費やして、すべての場所のstlでinsert()の一貫性のない動作を発見するのは面倒でした。

最後に、他の場所と比較して、insert() の動作が異なるのはなぜですか? それとも私が何か間違ったことをしたのですか？

オーディオデータをキューに入れるために使用している std::deque のラッパーがあります (問題がある場合は、libavcodec を介してブロックに入っています)。

これは、16 ビット データのバッファを取り、それを両端キューに追加する関数です。

ロック/ロック解除の定義:

私の問題は、 data_buffer_.insert ステートメントがコードに含まれている場合、この関数が含まれているスレッドが一度実行されてからロックアップすることです。コードを削除すると、機能します。挿入を src データの手動反復に置き換えて、要素ごとに push_back() を呼び出してみましたが、これもスレッドがロックされます。

これは両端キューにデータを追加する有効な方法ですか? テスト プログラムで試してみたところ、問題なく動作しているように見えました。これにより、スレッドが停止するのはなぜですか?

更新された情報: ロック/ロック解除が失敗した場合のエラー メッセージを追加し、どちらも問題なく成功しました。それらがペアで実行されていることを確認するためにそれらをインストルメント化しました。deque::insert 呼び出しで問題が発生している必要があります。それを削除すると、再び動き出すことができます。

更新: 問題が見つかりました。コードをリファクタリングし、定数を逃したため、デキューが常に満杯としてチェックされ、ループ =( が発生しました。

私はPythonのcollection.dequeで遊んでいて、次のベンチマークを作成しました。

これにより、さまざまなサイズのリスト/両端キューからpop（0）/ popleft（）が実行されます。結果は次のとおりです。

私の質問は、小さな両端キューとリスト（〜1000要素）のパフォーマンスがほぼ同じなのはなぜですか？