ソートされたキューは.NETに存在しますか？

Question

私はかなり専門的なコレクション.NETの必要性があります.BCLが私を助けてくれるとは思いませんが、誰かが似たようなことを知っていれば、私はそれをそこに投げ捨てると思いました。

基本的に、私の要件は、このようにしている：

• Iは、以下のような値のペアのリストを有する：（3,10）、（5,10）、（3,7）、（5、 5）
• 注文は重要です。 （3,10）！=（10,3）
• 個々の値は重複していますが、重複するペアは削除してください（できればサイレント）。
• キッカーは、私はこのリストが常にソートされている必要があります。私はいつでも並べ替えアルゴリズムによって定義されたリストの最初の値だけに興味があります。だから、

、私が行うことができるようにしたいもののいくつかのサンプルコード（私はそれはおそらく実施される構想として、上記に合わせて他の実装がに問題あり）：

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

私は引用：

私はこのリストはすべての時間をソートする必要があります。 私はいつも ソートアルゴリズムによって定義されたリストの最初の 値に興味があります。あなたがないがソートキューしかしPriority Queueたいですかのように

は、これが聞こえます。パフォーマンスが問題であれば、PQは確かに高速ですが、O（log n）対O（n）です。しかし、ドロップ重複の問題では、パラレルHashSet <>を保持する必要があります。

Answer 2

はあなたを持っていますSortedDictionaryまたはSortedListを見ましたか？

Answer 3

ソートされたリストは、あなたのPairクラスにIComparableを実装するだけで済むので、自動的に並べ替える必要があります。重複を取り除くために、私はソートされたリストがそれを処理するとは思わないが、あなたはそれを継承し、この機能を追加することができる。

Answer 4

SkeetがLookupクラスを使用する可能性が最も高いのはhis answerです。そして、あなたが構築し、このようなもので、それをアクセス：

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 

構文は、1つのまたは2のスポットに少しずれることがありますが、それは動作するはず。

Answer 5

現時点では、.NETには何も組み込まれておらず、すべての要件を満たしています。 .NET 4.0にはSortedSetクラスがあります。私はおそらく今あなたのことをよくしていないことを理解しています。

IComparableを実装するとSortedListが近づきます。キーと値としてペアを使用するだけです。 Pairへの参照を2回だけ格納するので、メモリのオーバーヘッドが大きくなりません。しかし、これは重複を考慮しません。

自分で書く方法はたくさんありますが、必要なものと完全に一致するものは何もありません。いくつかのオープンソースSortedSet実装があります（たとえば、Spring.Netには1つあります）。それは今、あなたの最善の策かもしれません。

Answer 6

IntervalHeapまたは優先度キューと呼ばれる、あなたが探しているのと同じように実装されているC5 Generic Collections Libraryを確認してください。ここにC5ブックからのいくつかの文書があります：IPriorityQueue<T>