Реализация списка, поддерживающая порядок
Есть ли существующийList
реализация в Java, которая поддерживает порядок на основе предоставленныхComparator
?
Что-то, что можно использовать следующим образом:
Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);
чтобыsomeT
вставляется так, что порядок в списке поддерживается в соответствии сcmp
(По предложению @andersoj я заканчиваю свой вопрос еще одним запросом)
Также я хочу иметь возможность просматривать список в отсортированном порядке, не удаляя элементы, т.е.
T min = Const.SMALLEST_T;
for (T e: l) {
assertTrue(cmp.compare(min, e) >= 0);
min = e;
}
должен пройти.
Все предложения приветствуются (кроме того, чтобы сказать мне, чтобы использоватьCollections.sort
в неупорядоченном полном списке), однако, я предпочел бы что-то вjava.*
или в конце концовorg.apache.*
поскольку было бы трудно представить новые библиотеки в данный момент.
Note: (UPDATE4) Я понял, что реализации такого рода списка будут иметь недостаточную производительность. Там два общих подхода:
Use Linked structure (sort of) B-tree or similar Use array and insertion (with binary search)№ 1. есть проблема с отсутствием кэша процессора № 2. есть проблемы со смещением элементов в массиве.
UPDATE2:
TreeSet
не работает, потому что использует предоставленный компаратор (MyComparator
) проверить на равенство и исходя из этого предполагает, что элементы равны и исключают их. Мне нужен этот компаратор только для заказа, а не «уникальности» фильтрация (поскольку элементы по своему естественному порядку не равны)
UPDATE3:
PriorityQueue
не работает какList
(как мне нужно), поскольку нет способа пройти его в том порядке, в котором он "отсортирован", чтобы получить элементы в отсортированном порядке, вы должны удалить их из коллекции.
ОБНОВИТЬ:
Подобный вопрос:
Хороший отсортированный список для Java
Список отсортированных массивов в Java