Я сбит с толку, что не могу найти быстрый ответ на это.По сути, я ищу структуру данных в Java, которая реализует интерфейс java.util.List, но хранит ее члены в отсортированном порядке.Я знаю, что вы можете использовать обычный ArrayList и использовать Collections.sort() для него, но у меня есть сценарий, в котором я иногда добавляю и часто получаю элементы из своего списка, и я не хочу сортировать его каждый раз, когда явосстановить участника в случае добавления нового.Может кто-нибудь указать мне на такую вещь, которая существует в JDK или даже сторонних библиотеках?
EDIT : структура данных должна будет сохранять дубликаты.
РЕЗЮМЕ ОТВЕТА : Я нашел все это очень интересным и многому научился.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 Guava Реализация набора, которая поддерживает дубликаты
- ca.odell.glazedlists.SortedList Этот класс содержит оговорку в своем javadoc:
Warning: This class breaks the contract required by List