Is there a non-unique-key sorted list generic collection in C#?

Question

I'm a bit surprised by System.Collections.Generic.SortedList, in that

1. It requires me to use <key, value> instead of <value>(comparer)
2. It only allows on entry per value

These seem quirky in the way I want to use it (although I'm sure they're just right for other situations). Is there another collection that doesn't have these two characteristics?

Answer 1

SortedList<,> is really a map sorted by key, not a list. Bad naming, maybe. But there are ways to emulate what you want, depending on your exact requirements. You could, for example, encapsulate a SortedList<T, int> and have add/remove something like:

// add
int count;
if(list.TryGetValue(value, out count)) list[value] = count+1;
else list[value] = 1;

Ultimately you could use a simple list (List<>) too - it depends what you are doing.

In part, I expect that data-binding etc makes it hard to implement a regular list that sorts immediately - you need to implement a lot of interfaces to get that working, as normally it expects the item you add to stay at the end.

Answer 2

I am not sure if this will meet your requirements. But you can sort a normal List. MSDN talks about it, but obviously this requires calling sort.

Answer 3

I've tried finding this same thing: basically a list that stays ordered as you add items to it. The closest I've found so far is a SortedSet from Goletas.Collections, which uses an AVL tree implementation:

http://www.goletas.com/solutions/collections/

But this class still requires that each element in the list be unique (hence "Set").

Perhaps this class could be modified to support non-unique items.

Answer 4

I know this is an old question, but I just came across this other question (C# Sortable collection which allows duplicate keys), which gives a solution: Use your own IComparer with a SortedSet! I.e.

/// <summary>
/// Comparer for comparing two keys, handling equality as being greater
/// Use this Comparer e.g. with SortedSets, SortedLists or SortedDictionaries, that don't allow duplicate keys
/// </summary>
/// <typeparam name="TKey"></typeparam>
public class DuplicateKeyComparer<TKey> : IComparer<TKey> where TKey : IComparable
{
    #region IComparer<TKey> Members

    public int Compare(TKey x, TKey y)
    {
        int result = x.CompareTo(y);

        return result == 0 ? 1 : result; // Handle equality as being greater
    }

    #endregion
}

Usage:

SortedSet<T> mySortedValues = new SortedSet<T>(new DuplicateKeyComparer<T>());

Edit: On second thoughts, this is probably a bad idea for anything other than SortedSet<T> as you probably wouldn't be able to lookup the different values associated with the duplicate keys using anything other than a foreach loop; and SortedSet<T> would be better represented by a SortedList<TKey,TValue> with the TKey being the interesting value and the TValue being a count (e.g. int) of the number of duplicates of that object.

Answer 5

If it is not performance-critical, you can use either

1) Linq OrderBy() or

2) List method Sort()

See this example

        var list = new List<int>();
        list.Add( 2);
        list.Add( 1);
        list.Add( 3);

        Console.WriteLine("Using Linq OrderBy");
        foreach (int i in list.OrderBy(i=>i))
            Console.WriteLine(i);

        Console.WriteLine("Using List.Sort()");
        list.Sort();
        foreach (int i in list)
            Console.WriteLine(i);