問題タブ [deque]

私は C++/STL 出身の比較的新しい Java プログラマーであり、これらの特性を持つクラスを探しています (私が理解しているように、C++ std::deque が持っている):

1. 先頭/末尾の挿入/削除の O(1) パフォーマンス
2. インデックスによるルックアップの O(1) パフォーマンス
3. 成長可能なコレクションです（固定サイズの境界は必要ありません）

これに相当するJavaはありますか？挿入/削除と成長可能な特性を持つJava 1.6 [ArrayDeque]クラスを見つけましたが、O(1)ではないtoArray()を呼び出さない限り、インデックスによるルックアップはないようです。

アクセスの複雑さ、サイズ変更時の再割り当てなどに関しては、STL ベクトルに似たものが必要です。任意のインデックス範囲をサポートする必要があります。 10. push_front を効率的にできるようにしたい。また、双方向のサイズ変更が必要です...

私は自分でこのようなものを書くことができることを知っていますが、これをサポートするすでに書かれたライブラリがあれば教えてください.

複数のスレッドが物を入れることができ、複数のスレッドが読み取ることができるキューが必要です。

Python には少なくとも 2 つのキュー クラスと がQueue.Queueありcollections.deque、前者は後者を内部的に使用しているようです。どちらもドキュメントでスレッドセーフであると主張しています。

ただし、キューのドキュメントにも次のように記載されています。

collections.deque は、ロックを必要としない高速のアトミックな append() および popleft() 操作を備えた無制限キューの代替実装です。

私はよく理解していないと思います:これは、dequeが完全にスレッドセーフではないことを意味しますか?

もしそうなら、私は 2 つのクラスの違いを完全には理解していないかもしれません。Queue がブロッキング機能を追加していることがわかります。一方、インオペレーターのサポートなど、いくつかの deque 機能が失われます。

内部dequeオブジェクトに直接アクセスすることは、

x in Queue().deque

スレッドセーフ？

また、deque が既にスレッドセーフであるのに、なぜ Queue はその操作にミューテックスを使用するのですか?

タイトルが尋ねるように。

両端キューについての私の理解は、それが「ブロック」を割り当てたということでした。より多くのスペースを割り当てるとイテレータが無効になる方法がわかりません。どちらかといえば、両端キューのイテレータはベクトルよりも多くの保証を持っていると思うでしょう。

deque でのイテレータの無効化に関して、私は少し混乱しています。（この質問の文脈で）

以下は抜粋です -- The C++ Standard Library: A Tutorial and Reference, by Nicolai M. Josuttis

先頭または末尾以外の要素を挿入または削除する と、deque の要素を参照するすべてのポインター、参照、および反復子が無効になります。

以下は、 SGIサイトからの抜粋です。

deque の反復子無効化のセマンティクスは次のとおりです。Insert (push_frontおよびを含むpush_back) は、deque を参照するすべての反復子を無効にします。両端キューの途中で消去すると、両端キューを参照するすべての反復子が無効になります。pop_front両端キュー (およびを含む) の先頭または末尾での消去は、消去され pop_backた要素を指している場合にのみ反復子を無効にします。

IMHO、deque は、最初のブロックが一方向に成長し、最後のブロックが反対方向に成長するブロックのコレクションです。

push_back, push_frontdeque イテレータに影響を与えるべきではありません (私は Josuttis に同意します)。

正しい説明は何ですか？これについて標準は何と言っていますか？

私はJavaソリューションを探していますが、一般的な答えもOKです。

Vector / ArrayListは、追加と取得の場合はO（1）ですが、追加の場合はO（n）です。

LinkedList（Javaでは二重リンクリストとして実装）は、追加と追加の場合はO（1）ですが、取得の場合はO（n）です。

Deque（ArrayDeque）は、上記のすべてに対してO（1）ですが、任意のインデックスの要素を取得することはできません。

私の考えでは、上記の要件を満たすデータ構造には、2つの拡張可能なリスト（1つは追加用、もう1つは追加用）があり、取得時に要素を取得する場所を決定するためのオフセットも格納されます。

std::dequeかなりの数のオブジェクトを格納するためにを使用しています。これらのオブジェクトの束を削除すると、std :: vectorと同様に、メモリ使用量が減少しないように見えます。

それを減らす方法はありますか？ベクトルでは、「スワップトリック」を使用する必要があることを知っています。これは、ここでも機能すると思いますが、コンテナに残っているすべての要素をコピーする必要があるため、これは避けたいと思います（したがって、すべてのオブジェクトを2回保存するのに十分なメモリ）。私はdequeの実装に精通していませんが、多くのコピーがなくてもそのようなことを実現できる可能性があることを理解しています（ベクトルでは明らかにそうではありません）。

違いがあれば、VC ++（Dinkumware）STLを使用しています。

に非常に短いコードdequeを書かなければなりませんが、メソッドのコードを書く方法がわかりません。もし誰かがメソッドの1つを手伝ってくれるなら(例えば、オブジェクトを追加するメソッド) deque の from に)、それで始められます。残りのメソッドを管理できると確信していますが、現時点ではかなり困惑しています。

（モジュールからの）キューがあり、そのキューへのQueueインデックス付きアクセスを取得したいと思います。（つまり、キューからアイテム番号4を削除せずに、キュー内のアイテム番号4を要求できるようになります。）

キューが内部でdequeを使用し、dequeがインデックス付きアクセスを持っていることを確認しました。問題は、（1）キューを台無しにすることなく、（2）スレッドセーフを壊すことなく、どのように両端キューを使用できるかということです。

タイトルが示すように、std :: listをスタックとして使用し、リストのすべての要素を反復処理するプログラムで問題が発生しました。リストが非常に大きくなったとき、プログラムはあまりにも長くかかっていました。

誰かがこれについて良い説明がありますか？スタック/キャッシュの動作ですか？

（リストをstd::vectorとstd::deque（ちなみに驚くべきデータ構造）に変更することで問題を解決し、すべてが突然非常に速くなりました）

編集：私はばかではなく、リストの真ん中にある要素にアクセスしません。私がリストで行った唯一のことは、最後/最初の要素を削除/追加し、リストのすべての要素を反復処理することでした。そして、私は常にイテレータを使用してリストを反復処理しました。