java - Java 等价于 std::deque

Question

我是来自 C++/STL 的相对较新的 Java 程序员，我正在寻找具有这些特征的类（据我了解，C++ std::deque 具有）：

1. O(1) 在开头/结尾插入/删除的性能
2. 按索引查找的 O(1) 性能
3. 是可增长的集合（不需要固定大小的界限）

有与此等效的Java吗？我发现 Java 1.6 [ArrayDeque] 类具有插入/删除和可增长的特性，但似乎没有按索引查找，除非您调用不会为 O(1) 的 toArray()。

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 索引）......但我讨厌重新发明轮子，尤其是当很有可能搞砸时......

Answer 3

有趣...我刚读完Java 泛型和集合，它简要讨论了这种集合，包括指向Java 专家时事通讯的链接，其中包括一个 CircularArrayList，它可能满足我的需要。

Answer 4

这是一个用Java 实现的即用型循环缓冲区 CircularArrayList。但是，它在创建后不可增长。（免责声明：此链接指向我自己的网站）

网上流传的另一种选择是来自 Java 专家时事通讯的选择。我从来没有用过那个，原因如下：

1. 它不完整 - （“此方法留给读者作为练习”）
2. 它不支持与 Java 集合框架中的其他集合一致的通用元素类型。
3. 它不必要地复杂，因此可能有错误，而不是遵循 AbstractList 的 Javadoc 推荐的扩展过程。