Существует ли существующая реализация List
в Java, которая поддерживает порядок на основе Comparator
?
Что-то, что можно использовать следующим образом:
Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);
чтобы вставить someT
так, чтобы порядок в списке поддерживался в соответствии с cmp
(В предложении @andersoj я завершаю свой вопрос еще одним запросом)
Также я хочу, чтобы иметь возможность перемещать список в отсортированном порядке без удаления элементов, i.e:
T min = Const.SMALLEST_T;
for (T e: l) {
assertTrue(cmp.compare(min, e) >= 0);
min = e;
}
должен пройти.
Все предложения приветствуются (за исключением того, что мне нужно использовать Collections.sort
в неупорядоченном полном списке), хотя я бы предпочел что-то в java.*
или в конечном итоге org.apache.*
, так как в этот момент было бы сложно представить новые библиотеки.
Примечание: (UPDATE4) Я понял, что реализация такого списка будет иметь недостаточную производительность. Существуют два общих подхода:
- Использовать связанную структуру (вроде) B-дерево или подобное
- Использовать массив и вставку (с бинарным поиском)
Нет проблемы с ошибками кэша CPU Нет 2. имеет проблему с перемещением элементов в массиве.
UPDATE2:
TreeSet
не работает, потому что он использует предоставленный компаратор (MyComparator
) для проверки равенства и на его основе предполагает, что элементы равны и исключают их. Мне нужен этот компаратор только для упорядочения, а не для фильтрации "уникальности" (поскольку элементы по их естественному порядку не равны)
Update3:
PriorityQueue
не работает как List
(как мне нужно), потому что нет способа пройти его в том порядке, в котором он "отсортирован", чтобы получить элементы в отсортированном порядке, которые вы должны удалить из коллекции.
UPDATE:
Аналогичный вопрос:
Хороший Сортированный список для Java
Отсортированный список массивов в Java