Список отсортированных массивов в Java
Я сбит с толку, что не могу найти быстрый ответ на это. По сути, я ищу структуру данных в Java, которая реализуетjava.util.List
интерфейс, но который хранит своих членов в отсортированном порядке. Я знаю, что вы можете использовать нормальныйArrayList
и использоватьCollections.sort()
на нем, но у меня есть сценарий, в котором я время от времени добавляю и часто извлекаю участников из своего списка, и я не хочу сортировать его каждый раз, когда извлекаю участника в случае добавления нового. Кто-нибудь может указать мне на такую вещь, которая существует в JDK или даже сторонних библиотеках?
РЕДАКТИРОВАТЬ: Структура данных должна сохранить дубликаты.
РЕЗЮМЕ ОТВЕТАЯ нашел все это очень интересным и многому научился. Aioobe, в частности, заслуживает упоминания за его настойчивость в попытке выполнить мои требования выше (в основном, отсортированная реализация java.util.List, которая поддерживает дубликаты). Я принял его ответ как наиболее точный из того, что я просил, и больше всего думал о последствиях того, что я искал, даже если то, что я спрашивал, было не совсем тем, что мне нужно.
Проблема с тем, что я просил, заключается в самом интерфейсе List и концепции необязательных методов в интерфейсе. Процитирую Javadoc:
Пользователь этого интерфейса имеет точный контроль над тем, где в списке каждый элемент вставлен.
Вставка в отсортированный список не имеет точного контроля над точкой вставки. Затем вы должны подумать, как вы будете обрабатывать некоторые методы. приниматьadd
например:
public boolean add (Object o)
Appends the specified element to the end of this list (optional operation).
Теперь вы оказались в неудобной ситуации: 1) разорвать контракт и внедрить отсортированную версию add 2)add
добавить элемент в конец списка, нарушая ваш отсортированный порядок 3) Выходadd
(как его необязательно), бросаяUnsupportedOperationException
и реализации другого метода, который добавляет элементы в отсортированном порядке.
Вариант 3, вероятно, самый лучший, но я нахожу нежелательным иметь метод add, который вы не можете использовать, и другой метод sortedAdd, которого нет в интерфейсе.
Другие связанные решения (без определенного порядка):
java.util.PriorityQueue что, вероятно, ближе всего к тому, что мне нужно, чем то, что я просил. В моем случае очередь - не самое точное определение коллекции объектов, но функционально она делает все, что мне нужно.net.sourceforge.nite.util.SortedList, Однако эта реализация нарушает контракт интерфейса List, осуществляя сортировку вadd(Object obj)
метод и причудливо не имеет никакого эффекта для методаadd(int index, Object obj)
, Общее согласие предполагаетthrow new UnsupportedOperationException()
может быть лучшим выбором в этом сценарии.TreeMultiSet гуавы Реализация набора, которая поддерживает дубликатыca.odell.glazedlists.SortedList Этот класс поставляется с оговоркой в его Javadoc:Warning: This class breaks the contract required by List