Java等價於std :: deque

Question

我是一個來自C++/STL的相對較新的Java程序員，並且正在尋找一個具有這些特性的類（C++ std :: deque，據我瞭解）：

1. O（1），用於在開始/結束的插入/取出性能
2. O（1）通過指數爲查找性能
3. 是可增長的集合（不需要固定大小邊界）

是否有與此相當的Java？我發現Java 1.6 [ArrayDeque]類具有插入/刪除和可擴展特性，但似乎沒有按索引查找，除非調用toArray（），而不是O（1）。

Answer 1

Java的原始集合具有帶get（int idx）方法的ArrayDeque。

http://sourceforge.net/projects/pcj

我不能保證這個項目的質量雖然。

另一種方法是獲取JDK ArrayDeque源代碼並自己添加get（int idx）方法。應該比較容易。

編輯：如果您打算以高度多線程的方式使用雙端隊列，我會去「修補JDK的ArrayDeque」路線。此實現已經過徹底測試，並在新的java.util.concurrent ForkJoin框架中使用。

Answer 2

我的默認方法是將我自己的類破解在一起，並將ArrayList作爲底層實現（例如，將我自己的類的索引映射到ArrayList索引）......但是我討厭重新發明輪子，尤其是當存在很大的可能性時up ...

Answer 3

有趣...我剛讀完Java Generics and Collections，它對這種集合有一個簡短的討論，包括一個鏈接到Java Specialists' Newsletter，其中包括一個CircularArrayList，可以做我所需要的。

Answer 4

這是一個隨時可用的circular buffer implemented in Java, CircularArrayList。儘管如此，它在創作之後仍然不可增長。 （免責聲明：該鏈接指向我自己的網站）

其他選項漂浮在網絡上將是one from the Java Specialists Newsletter。我從來沒有使用過的那一個，有以下原因：

1. 它是不完整的 - （「此方法作爲練習留給讀者」）
2. 它不支持泛型元素類型將是一致來自Java Collection框架的其他集合。
3. 這是不必要的複雜，因此可能是越野車，而不是按照AbstractList的Javadoc推薦的擴展程序。