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

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

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

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

java,collections,deque,

11

Ответов: 4


10 принят

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

http://sourceforge.net/projects/pcj

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

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

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


0

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


0

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


0

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

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

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