Existiert eine sortierte Warteschlange in .NET?

Question

Ich brauche eine ziemlich spezialisierte Sammlung von .NET, und ich denke nicht, dass die BCL mir helfen kann, aber ich dachte, ich würde es da rausschmeißen, wenn jemand etwas Ähnliches wüsste.

Grundsätzlich meine Anforderungen sind somit:

• Ich habe eine Liste von Paaren von Werten, wie zum Beispiel: (3, 10), (5, 10), (3, 7), (5, 5)
• Reihenfolge ist wichtig, dh. (3, 10)! = (10, 3)
• Duplikate einzelner Werte sind in Ordnung, doppelte Paare sollten jedoch gelöscht werden (vorzugsweise im Hintergrund).
• Der Kicker ist, ich brauche diese Liste die ganze Zeit sortiert. Ich bin immer nur an dem ersten Wert in der Liste interessiert, der durch den Sortieralgorithmus definiert wird.

So, einige Beispiel-Code, was ich will (wie ich es wahrscheinlich umgesetzt würde sich vorstellen, andere Implementierungen, die oben sind in Ordnung zu passen) zu tun in der Lage:

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

Ich zitiere:

Ich brauche diese Liste die ganze Zeit sortiert. Ich bin immer nur an der ersten Wert in der Liste interessiert, wie durch die Sortieralgorithmus zu jeder Zeit definiert.

Das klingt wie Sie nicht wollen eine Sorted Queue aber ein Priority Queue tun. Wenn Leistung ein Problem ist, wird ein PQ sicherlich schneller sein, O (log n) vs O (n). Aber das Drop-Duplikat-Problem würde erfordern, dass Sie ein paralleles HashSet <> auch beibehalten.

Answer 2

Sie haben schaute auf SortedDictionary oder SortedList?

Answer 3

SortedList wäre am besten, alles, was Sie tun müssen, ist dann IComparable in Ihrer Pair-Klasse zu implementieren, und es würde sie automatisch bestellen. Was das Entfernen von Duplikaten anbelangt, denke ich nicht, dass die sortierte Liste das handhabt, aber Sie könnten davon erben und diese Funktionalität hinzufügen.

Answer 4

sollten Sie höchstwahrscheinlich eine Lookup-Klasse verwenden, wie The Skeet in his answer erwähnt. Dann bauen Sie und greifen sie mit etwas wie folgt aus:

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 

Die Syntax ein wenig aus in 1 oder 2 Punkte sein können, aber es sollte funktionieren.

Answer 5

In .NET ist zu diesem Zeitpunkt nichts eingebaut, das alle Ihre Anforderungen erfüllt. In .NET 4.0 gibt es eine SortedSet-Klasse. Ich weiß, dass es dir jetzt wahrscheinlich nicht viel nützt.

SortedList kommt nahe, wenn Sie IComparable implementieren. Sie würden einfach das Paar als Schlüssel und Wert verwenden. Sie würden den Verweis auf Ihr Paar nur zweimal speichern, so dass kein großer Speicheraufwand entsteht. Aber das wird sich nicht um Duplikate kümmern.

Es gibt zahlreiche Möglichkeiten, um es selbst zu schreiben, aber nichts eingebaut, das vollständig entspricht, was Sie brauchen. Es gibt ein paar Open-Source-SortedSet-Implementierungen (zum Beispiel gibt es eine in Spring.Net). Das könnte jetzt deine beste Wette sein.

Answer 6

Überprüfen Sie die , die bereits eine Implementierung genau wie Sie, eine IntervalHeap oder Priority Queue genannt hat. Hier ist eine Dokumentation aus dem C5 Buch: IPriorityQueue<T>