13

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

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

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

4

4 に答える 4

11

Java のプリミティブ コレクションには、get(int idx) メソッドを持つ ArrayDeque があります。

http://sourceforge.net/projects/pcj

ただし、このプロジェクトの品質を保証することはできません。

別の方法は、JDK ArrayDeque ソースを取得し、get(int idx) メソッドを自分で追加することです。比較的簡単なはずです。

編集:非常にマルチスレッドな方法で両端キューを使用する場合は、「JDK の ArrayDeque にパッチを適用する」ルートに進みます。この実装は徹底的にテストされており、新しい java.util.concurrent ForkJoin フレームワークで使用されています。

于 2008-12-08T16:35:52.643 に答える
0

これは、Java で実装されたすぐに使用できる循環バッファー CircularArrayListです。ただし、作成後は成長できません。（免責事項：このリンクは私のウェブサイトを指しています）

Web に出回っているもう 1 つのオプションは、Java Specialists Newsletter からのものです。次の理由から、私はそれを使用したことはありません。

  1. 不完全です - (「この方法は読者への演習として残されています」)
  2. Java コレクションのフレームワークからの他のコレクションと一貫していたであろうジェネリック要素タイプをサポートしません。
  3. AbstractList の Javadoc で推奨されている拡張手順に従うのではなく、不必要に複雑であるため、バグが含まれている可能性があります。
于 2011-07-14T17:44:46.743 に答える
0

興味深い...私はJava Generics and Collectionsを読み終えたところで、 Java Specialists' Newsletterへのリンクを含む、この種のコレクションについての簡単な説明があり、必要なことを行う可能性のあるCircularArrayListが含まれています。

于 2008-12-22T21:06:51.340 に答える
0

私のデフォルトのアプローチは、基本的な実装として ArrayList を使用して、独自のクラスをハックすることです (たとえば、独自のクラスのインデックスを ArrayList インデックスにマップします)...しかし、特に失敗する可能性が高い場合は、車輪を再発明するのは嫌いです...

于 2008-12-08T17:11:00.997 に答える