Java相当于std :: deque

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

1. O（1）在开始/结束时插入/移除的性能
2. O（1）按索引查找的性能
3. 是可成长的集合（不需要固定大小的边界）

是否有Java等同于此？ 我找到了Java 1.6 [ArrayDeque]类，它具有插入/删除和可增长的特性，但似乎没有按索引查找，除非你调用toArray（），它不是O（1）。

Answer 1

Java的Primitive Collections有一个带有get（int idx）方法的ArrayDeque。

http://sourceforge.net/projects/pcj

我不能保证这个项目的质量。

另一种方法是获取JDK ArrayDeque源并自己添加get（int idx）方法。 应该比较容易。

编辑：如果你打算以高度multithreading的方式使用deque，我会去“修补JDK的ArrayDeque”路线。 此实现已经过彻底测试，并在新的java.util.concurrent ForkJoin框架中使用。

Answer 2

我的默认方法是将我自己的类混合在一起，将ArrayList作为底层实现（例如将我自己的类索引映射到ArrayList索引）……但我讨厌重新发明轮子，特别是当有很好的机会搞砸时……

Answer 3

有趣……我刚刚阅读了Java Generics and Collections ，它对这种集合进行了简短的讨论，包括Java专家通讯的链接，其中包括一个可能做我需要的CircularArrayList。

Answer 4

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

围绕网络的另一个选择是Java专家通讯中的选项 。 我从未使用过那个，原因如下：

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