Эквивалент std :: deque в Java
Я относительно новый программист на Java, пришедший из C++ / STL, и ищу класс с этими характеристиками (которые, как я понимаю, имеет C++ std :: deque):
- O (1) производительность для вставки / удаления в начале / конце
- O (1) производительность поиска по индексу
- являются растущими коллекциями (не нуждаются в фиксированных границах размера)
Есть ли этому эквиваленту в Java? Я нашел класс Java 1.6 [ArrayDeque], который имеет характеристики вставки / удаления и увеличения, но, похоже, не имеет поиска по индексу, если вы не вызываете toArray (), который не был бы O (1).
Ответы 4
В примитивных коллекциях для Java есть ArrayDeque с методом get (int idx).
http://sourceforge.net/projects/pcj
Однако я не могу поручиться за качество этого проекта.
Альтернативой может быть получение источника JDK ArrayDeque и самостоятельное добавление метода get (int idx). Должно быть относительно легко.
Обновлено: Если вы намереваетесь использовать двухстороннюю очередь в многопоточном режиме, я бы пошел по маршруту «патч JDK ArrayDeque». Эта реализация была тщательно протестирована и используется в новом фреймворке java.util.concurrent ForkJoin.
PCJ работает только с примитивными типами, что весьма ограничивает его полезность.
Интересно ... Материал GNU меня пугает (хотя в лицензии на указанный вами код ArrayDeque указано Creative Commons ... странно), потому что я работаю в коммерческой среде и не могу использовать какой-либо код GPL.
Вы можете использовать бэкпорт JSR166 по адресу: backport-jsr166.sourceforge.net Он выпущен в общественное достояние; нет проблем с лицензированием.
Мой подход по умолчанию заключался бы в том, чтобы собрать мой собственный класс с ArrayList в качестве базовой реализации (например, сопоставить индексы моего собственного класса с индексами ArrayList) ... но я ненавижу изобретать колесо, особенно когда есть хороший шанс облажаться ...
Я удалил свой пост о HashMap, но я думаю, что это было бы улучшением по сравнению с ArrayList для произвольных вставок.
Интересно ... Я как раз заканчивал чтение Обобщения и коллекции Java, и в нем есть краткое обсуждение такого рода коллекции, включая ссылку на Информационный бюллетень специалистов по Java, который включает CircularArrayList, который может делать то, что мне нужно.
Вот готовый к использованию кольцевой буфер, реализованный на Java, CircularArrayList. Однако после создания его нельзя выращивать. (Отказ от ответственности: эта ссылка указывает на мой собственный веб-сайт)
Другой вариант, распространенный в сети, - это один из бюллетеня Java Specialists Newsletter. Я никогда не использовал его по следующим причинам:
- Он неполный - («Этот метод оставлен читателю в качестве упражнения»)
- Он не поддерживает универсальный тип элемента, как это было бы согласовано с другими коллекциями из Java Collection Framework.
- Это излишне сложно и, следовательно, возможно, содержит ошибки, вместо того, чтобы следовать процедуре расширения, рекомендованной Javadoc от AbstractList.
Исходный код для пути к классам GNU ArrayDeque находится здесь: fuseyism.com/classpath/doc/java/util/ArrayDeque-source.html. Должно быть достаточно легко добавить get (i) или даже заставить его реализовать List <E>