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

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

O (1) производительность для вставки/удаления в начале/конце
O (1) производительность для поиска по индексу
являются растущими коллекциями (не требуются фиксированные размеры)

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

Ответ 1

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

http://sourceforge.net/projects/pcj

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

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

EDIT: Если вы намерены использовать deque в многопоточном режиме, я бы пошел по пути "patch the JDK ArrayDeque". Эта реализация была тщательно протестирована и используется в новой инфраструктуре ForkJoin java.util.concurrent.

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

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