Is there a sorted collection type in .NET?

Question

I'm looking for a container that keeps all its items in order. I looked at SortedList, but that requires a separate key, and does not allow duplicate keys. I could also just use an unsorted container and explicitly sort it after each insert.

Usage:

• Occasional insert
• Frequent traversal in order
• Ideally not working with keys separate from the actual object, using a compare function to sort.
• Stable sorting for equivalent objects is desired, but not required.
• Random access is not required.

I realize I can just build myself a balanced tree structure, I was just wondering if the framework already contains such a beast.

Answer 1

If the key is also an attribute of the object, you might try the System.Collections.ObjectModel.KeyedCollection<TKey, TItem>. It's an abstract class, but if your key is just a property of the item then it's real simple to derive from.

Answer 2

.Net has the SortedList class: MSDN - Sorted List

• Failing that you can just use the List class and the "Sort" method.

Answer 3

You might want to take a look at the Wintellect Power Collections. It is available on CodePlex and contains quite a few collections that are very helpful. The OrderedBag collection in the project is exactly what you are looking for. It essentially uses a red-black tree to provide a pretty efficient sort.

Answer 4

I would extend your own list class that, as you mentioned, simply sorts after every insert. Since your inserts are infrequent the performance hit would be minimal, and sorting a nearly sorted list is quick, in any case. Extend the Generic List and override the Add method to sort immediately. If performance becomes an issue you can insert in place to save some time. Furthermore you can queue up your inserts to do a single traversal insertion for all the values you want to insert.

Answer 5

Here's an old trick I used way back in VB6 to sort things alphabetically: Use a System.Windows.Forms ListBox object, and set its "Sorted" property to true. In C#, you can insert any object into the listbox, and it will sort the object alphabetically by its ToString() value:

for a class module:

---

using System.Windows.Forms;

    static void Main(string[] args)
    {
        ListBox sortedList = new ListBox();
        sortedList.Sorted = true;

        sortedList.Items.Add("foo");
        sortedList.Items.Add("bar");
        sortedList.Items.Add(true);
        sortedList.Items.Add(432); 

        foreach (object o in sortedList.Items)
        {
            Console.WriteLine(o);
        }

        Console.ReadKey();
    }

---

This will display:

432
bar
foo
True

Answer 6

As I mentioned earlier today here, the C5 Generic Collection Library has the proper container for you.

Answer 7

If you just want to stick with the standard collections then the Sort(IComparer<>) function of the List<> class is one that often gets ignored. All you need to do is create a suitable Comparer for your objects, for example:

public class PositionDateComparer : IComparer<VehiclePosition>
{
 public int Compare(VehiclePosition x, VehiclePosition y)
 {
  if (x.DateTime == DateTime.MinValue)
  {
   if (y.DateTime == DateTime.MinValue)
   {
    // If x is null and y is null, they're
    // equal. 
    return 0;
   }

   // If x is null and y is not null, y
   // is greater. 
   return -1;
  }

  // If x is not null...
  //
  if (y.DateTime == DateTime.MinValue)
  // ...and y is null, x is greater.
  {
   return 1;
  }

  // ...and y is not null, compare the dates
  //
  if (x.DateTime == y.DateTime)
  {
   // x and y are equal
   return 0;
  }

  if (x.DateTime > y.DateTime)
  {
   // x is greater
   return 1;
  }

  // y is greater
  return -1;
 }
}

Then just perform a vehiclePositionsList.Sort(new PositionDateComparer()) whenever you want to sort the list before accessing it. I realise that this might not be as simple as a container which automatically sorts every time you add a new object, but for many (like me!) this might be enough to do the job successfully without requiring any additional libraries.