Java-эквивалент std :: deque

Question

Я относительно новый Java-программист, пришедший из C ++ / STL, и ищу класс с такими характеристиками (которые, как я понимаю, есть в C ++ std :: deque):

1. O (1) производительность для вставки / удаления в начале / конце
2. O (1) производительность для поиска по индексу
3. являются растущими коллекциями (не нуждаются в границах фиксированного размера)

Есть ли Java-эквивалент этого? Я обнаружил класс Java 1.6 [ArrayDeque], который имеет характеристики вставки / удаления и возможности расширения, но, похоже, не имеет поиска по индексу, если вы не вызовете toArray (), который не будет O (1).

Answer 1

Примитивные коллекции для Java имеют ArrayDeque с методом get (int idx).

http://sourceforge.net/projects/pcj

Я не могу ручаться за качество этого проекта.

Альтернативой может быть получение источника JDK ArrayDeque и добавление метода get (int idx) самостоятельно. Должно быть относительно легко.

РЕДАКТИРОВАТЬ: Если вы намереваетесь использовать deque в многопоточной манере, я бы пошел "патч Jray ArrayDeque". Эта реализация была тщательно протестирована и используется в новой инфраструктуре java.util.concurrent ForkJoin.

Answer 2

Вот готовый к использованию кольцевой буфер, реализованный на Java, CircularArrayList . Это не растет после создания, хотя. ( Отказ от ответственности: эта ссылка указывает на мой собственный сайт )

Другой вариант, плавающий в Интернете, будет из рассылки Java Specialists Newsletter . Я никогда не использовал его по следующим причинам:

1. Это неполно - («Этот метод оставлен читателю в качестве упражнения»)
2. Он не поддерживает универсальный тип элемента, как это было бы совместимо с другими коллекциями из платформы Java Collection.
3. Это излишне сложно, и, следовательно, возможно, глючит, вместо того, чтобы следовать процедуре расширения, рекомендованной Javadoc от AbstractList.

Answer 3

Интересно ... Я только что закончил читать Дженерики и коллекции Java , и в нем кратко обсуждается этот вид коллекции, включая ссылку на Специалистов Java Информационный бюллетень , который включает в себя CircularArrayList, который может делать то, что мне нужно.

Answer 4

Моим подходом по умолчанию было бы объединить мой собственный класс с ArrayList в качестве базовой реализации (например, сопоставить индексы моего собственного класса с индексами ArrayList) ... но я ненавижу заново изобретать колесо, особенно когда есть хороший шанс испортить ...