Czy posortowana kolejka istnieje w .NET?

Question

Potrzebuję dość wyspecjalizowanej kolekcji .NET i nie sądzę, że BCL może mi pomóc, ale pomyślałem, że wyrzucę ją tam, gdyby ktoś wiedział o czymś podobnym.

Zasadniczo moje wymagania są więc:

• mam listę par wartości, takich jak: (3, 10), (5, 10), (3, 7), (5, 5)
• Zamówienie jest ważne, tj. (3, 10)! = (10, 3)
• Duplikaty pojedynczych wartości są w porządku, ale zduplikowane pary należy upuścić (najlepiej po cichu).
• Kicker jest, potrzebuję tej listy posortowanej przez cały czas. Interesuje mnie tylko pierwsza wartość na liście, jaką definiuje algorytm sortowania w tym samym czasie.

Więc jakiś przykład kodu, co chcę być w stanie to zrobić (jak ja sobie wyobrazić, że to prawdopodobnie być realizowane, inne implementacje, które pasują powyższe są grzywny):

public class Pair 
{ 
    public Pair(int first, int second) 
    { First = first; Second = second; } 
    public int First { get; set; } 
    public int Second { get; set; } 
} 

SortedQueue<Pair> foo = new SortedQueue<Pair>((left, right) => { 
    return right.First - left.First; 
}); 

foo.Add(new Pair(10, 3)); 
foo.Add(new Pair(4, 6)); 
foo.Add(new Pair(6, 15)); 
foo.Add(new Pair(6, 13)); // This shouldn't cause a problem 

Pair current = foo.Shift(); // current = (4, 6) 

Answer 1

cytuję:

muszę to lista posortowana cały czas. Zawsze interesuje mnie tylko pierwsza wartość na liście zdefiniowana przez algorytm sortowania w dowolnym momencie.

To brzmi jak ty nie chcą posortowanej kolejki ale Priority Queue. Jeśli wydajność jest problemem, to PQ z pewnością będzie szybszy, O (log n) kontra O (n). Ale problem z duplikatem kropli wymagałby również zachowania równoległego HashSet <>.

Answer 2

Mają cię spojrzał na SortedDictionary lub SortedList?

Answer 3

SortedList byłby najlepszy, wszystko, co musisz zrobić, to zaimplementować funkcję IComparable w klasie Pair i automatycznie je uporządkować. Jeśli chodzi o usuwanie duplikatów, nie sądzę, że posortowana lista to obsługuje, ale można ją dziedziczyć i dodawać tę funkcję.

Answer 4

powinieneś najprawdopodobniej użyć klasy Lookup jako The Skeet wspomina w his answer. Następnie należy zbudować i dostęp do niego z czymś takim:

List<Lookup<int, int>> yourList = new List<Lookup<int, int>>(); 
yourList.Add(new Lookup(3,5)); 
//... 
var list = from item in yourList 
      orderby list.Key //or whatever sort criteria you want here 
      select item; 
//use list 

składnia może być trochę off w 1 lub 2 punktach, ale to powinno działać.

Answer 5

Nie ma nic wbudowanego w .NET w tym momencie, który spełnia wszystkie twoje wymagania. W .NET 4.0 istnieje klasa SortedSet. Zdaję sobie sprawę, że prawdopodobnie teraz ci nie pomaga.

SortedList jest blisko, jeśli zaimplementujesz funkcję IComparable. Po prostu użyjesz Pary jako klucza i wartości. Przechowywałbyś odwołanie do pary tylko dwa razy, więc nie jest to nadmierne obciążenie pamięci. Ale to nie zajmie duplikatów.

Istnieje wiele sposobów, aby napisać to samemu, ale nic w tym wbudowanego nie pasuje do tego, czego potrzebujesz. Istnieje kilka implementacji SortedSet Open Source (na przykład w Spring.Net). To może być teraz twój najlepszy zakład.

Answer 6

Zapoznaj się z C5 Generic Collections Library, który ma już taką samą implementację, o nazwie IntervalHeap lub Kolejka priorytetowa. Oto kilka dokumentów na ten temat z Książki C5: IPriorityQueue<T>