26

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.

Improve this question

7 Answers 7

Reset to default
20

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

In the immortal words of Bob Dylan...the times they are a changing. So I just wanted to add that SortedSet<T> is now part of 4.0 framework. SortedSet is also implemented as a red-black tree.
@EBarr: You should post this as an answer, I nearly missed your comment! It's got to know that we now have a built-in option.
The opener wants to insert equivalent objects so SortedSet<T> cannot be an option.
14

Just to make EBarr's comment as answer, there is SortedSet<T> since .NET 4.0. Of course it is a set, which means you cannot have duplicates.

Improve this answer

2 Comments

Since he is not interested in answering, and it easy to miss comments, I made an effort..
I needed a sorted lookup on an INT primary key, and SortedSet<t> worked perfectly since the values are already guaranteed to be unique. +1
4

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.

Improve this answer

Comments

3

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.

Improve this answer

1 Comment

For Add() you may want to try a BinarySearch to find the correct position and then do an Insert(). You'll also want to override AddRange(), although for that one you may want to add everything to the end and do a single sort. Further, you'll want to override then disable Insert() and InsertRange() to prevent inadvertently "un-sort-ing" the collection.
1

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

Improve this answer

2 Comments

So which collection is the answer?
Consulting the documentation, the TreeBag<T>(SCG.IComparer<T> cmp) should fulfil ops requirements.
-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.

Improve this answer

3 Comments

That's closer, but again, requires unique keys. I may just have to add a counter to keep them unique.
Furthermore this is just an order respecting collection, not really an always-sorted collection which is what I think OP is after.
You could always make TKey the value, and TItem the counter if you're not using TItem as a lookup value.
-15

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

Improve this answer

2 Comments

...I'd give it a decent burial together with VB6
A List can do that as well and without the need of a form control(It has a Sort() method). Creating a form control to do a simple operation as a sort is not only an overkill but it is completely useless, as well. This answer totally ignores the OP's very detailed and clear question. If you have understood why this answer is not helping anyone that searches for a solution to the problem presented, you could delete it and recover your lost reputation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.