Does a sorted queue exist in .NET?

Question

I have a need for a fairly specialised collection .NET, and I don't think that the BCL can help me, but I thought I'd throw it out there for if anyone knew of something similar.

Basically, my requirements are thus:

• I have a list of pairs of values, such as: (3, 10), (5, 10), (3, 7), (5, 5)
• Order is important, ie. (3, 10) != (10, 3)
• Duplicates of individual values are fine, but duplicate pairs should be dropped (preferably silently).
• The kicker is, I need this list sorted all the time. I'm only ever interested in the first value in the list as defined by the sort algorithm at any one time.

So, some example code of what I want to be able to do (as I envision it would probably be implemented, other implementations that fit the above are fine to):

public class Pair
{
    public Paid(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

Have you looked at SortedDictionary or SortedList?

Answer 2

SortedList would be best, all you have to do then is implement IComparable in your Pair class, and it would auto-order them. As for removing duplicates, I dont think Sorted list handles that, but you could inherit from it, and add this functionality.

Answer 3

you should most likely use a Lookup class as The Skeet mentions in his answer. Then you build and access it with something like this:

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

The syntax may be a little off in 1 or 2 spots but it ought to work.

Answer 4

I quote:

I need this list sorted all the time. I'm only ever interested in the first value in the list as defined by the sort algorithm at any one time.

This sounds like you do not want a Sorted Queue but a Priority Queue. If performance is an issue then a PQ will certainly be faster, O(log n) vs O(n). But the drop-duplicates issue would require you to keep a parallel HashSet<> as well.

Answer 5

There is nothing built into .NET at this time that meets all of your requirements. In .NET 4.0 there is a SortedSet class. I realize that it probably does not do you much good now.

SortedList comes close if you implement IComparable. You would just use the Pair as the key and the value. You would only be storing the reference to your Pair twice so it isn't a huge memory overhead. But this will not take care of duplicates.

There are numerous ways to write it yourself, but nothing built in that fully matches what you need. There are a few open source SortedSet implementations (there is one in Spring.Net for example). That might be your best bet right now.

Answer 6

Check out the C5 Generic Collections Library which already has an implementation just like you're looking for, called an IntervalHeap or Priority Queue. Here's some documentation on it from the C5 Book: IPriorityQueue<T>