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

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

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

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


java collections deque
person Jason S    schedule 08.12.2008    source источник

Ответы (4)


arrow_upward
10
arrow_downward

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

http://sourceforge.net/projects/pcj

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

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

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

person bajafresh4life    schedule 08.12.2008
comment
Исходный код GNU classpath ArrayDeque находится здесь: fuseyism.com/classpath/doc/ java/util/ArrayDeque-source.html. Должно быть достаточно легко добавить get(i) или даже реализовать List‹E› - person Todd Gamblin; 08.12.2008
comment
PCJ работает только с примитивными типами, что ограничивает его полезность. - person Michael Myers; 08.12.2008
comment
Интересно... Материалы GNU пугают меня (хотя лицензия для кода ArrayDeque, которую вы перечисляете, показывает Creative Commons... странно), потому что я работаю в коммерческой среде и не могу использовать какой-либо код GPL. - person Jason S; 08.12.2008
comment
Вы можете использовать бэкпорт JSR166 по адресу: backport-jsr166.sourceforge.net Он выпущен в общественное достояние. ; никаких проблем с лицензией. - person bajafresh4life; 08.12.2008

arrow_upward
0
arrow_downward

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

person Jason S    schedule 08.12.2008
comment
Я удалил свой пост о HashMap, но я думаю, что это было бы улучшением по сравнению с ArrayList для произвольных вставок. - person Daddy Warbox; 08.12.2008

arrow_upward
0
arrow_downward

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

person Jason S    schedule 22.12.2008

arrow_upward
0
arrow_downward

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

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

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