Implementacja listy, która utrzymuje porządek
Czy istniejeList
implementacja w Javie, która utrzymuje porządek oparty na dostarczonymComparator
?
Coś, co można wykorzystać w następujący sposób:
Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);
po to abysomeT
zostaje wstawiony tak, że kolejność na liście jest utrzymywana zgodnie zcmp
(W sugestii @andersoj kończę pytanie z jeszcze jedną prośbą)
Chcę także móc przeglądać listę w posortowanej kolejności bez usuwania elementów, tj .:
T min = Const.SMALLEST_T;
for (T e: l) {
assertTrue(cmp.compare(min, e) >= 0);
min = e;
}
powinien przejść.
Wszystkie sugestie są mile widziane (z wyjątkiem powiedzenia mi, żebym używałCollections.sort
na nieuporządkowanej pełnej liście), jednak wolałbym coś w tymjava.*
lub w końcuorg.apache.*
ponieważ trudno obecnie wprowadzić nowe biblioteki.
Uwaga: (UPDATE4) Zdałem sobie sprawę, że implementacje tego rodzaju listy będą miały niewystarczającą wydajność. Istnieją dwa ogólne podejścia:
Użyj połączonej struktury (rodzaju) drzewa B lub podobnegoUżyj tablicy i wstawienia (przy wyszukiwaniu binarnym)Nie 1. ma problem z pominięciem pamięci podręcznej procesora Nie 2. ma problem z przesuwaniem elementów w tablicy.
UPDATE2: TreeSet
nie działa, ponieważ używa dostarczonego komparatora (MyComparator
) sprawdzanie równości i na tej podstawie zakłada, że elementy są równe i wykluczają je. Potrzebuję tego komparatora tylko do porządkowania, a nie filtrowania „unikalności” (ponieważ elementy według ich naturalnego uporządkowania nie są równe)
AKTUALIZACJA3: PriorityQueue
nie działa jakList
(jak potrzebuję), ponieważ nie ma sposobu, aby przemieścić go w kolejności, w jakiej jest „posortowany”, aby uzyskać elementy w posortowanej kolejności, należy je usunąć z kolekcji.
AKTUALIZACJA:
Podobne pytanie:
Dobra sortowana lista dla Javy
Posortowana lista tablic w Javie