Collection that maintains sort order C#

Question

I have a class Foo which contains a list of objects: List<Bar>. Each Bar has a property which they can be ordered on (of type TimeSpan, representing a duration), and Bar is an immutable object - that is, the duration does not change over the running of the algorithm. At the moment, for each Foo I also maintain the Bar that would be first in the list if it were to be ordered (i.e. the Bar of shortest duration). Something like this:

public class Foo
{
    public List<Bar> AllBars { get; set; }

    public Bar FirstBar { get; set; }

    public Foo (Bar bar)
    {
        FirstBar = bar;

        AllBars = new List<Bar>() { bar };
    }

    public AddBar(Bar bar)
    {
        if(bar.Duration < FirstBar.Duration)
        {
            FirstBar = bar;
        }

        AllBars.Add(bar);
    }
}

This class Foo is used in an algorithm where processing performance (speed) is critical. Memory is important but not as much as speed. There is a list of n Foos, each of which has up to m Bars. This class has served me well up until this point. I now wish to offer the user several choices, meaning I will need to provide random access to the first few Bars in the list.

I would thus like to store my Bars in order so that I can access them by index in order. In my Bar class I implemented IComparable to allow Bars to be compared on duration but I am stuck at choosing an appropriate data type. I looked at System.Collections.SortedList but (unless I am wrong) this appears to reference elements by key as it implements IDictionary. What collection could I use that would maintain my objects such that they stay sorted, and such that they are traversable in order of index?

Answer 1

(promoted from a comment, as requested by the asker)

If you can live with having "values" that mean nothing, just use a SortedList<Bar, object> where you do not use the value part.

Add with yourSortedList.Add(yourBar, null) in O(n) time (the list will have to move "up" all entries after the point where you insert). Retrieve the ith entry in O(1) time with yourSortedList.Keys[i].

See the SortedList<,>.Keys property documentation for some "proof" that the above description is correct. Note that a SortedList<,> actually consists of a "list" (i.e. an array of length Capacity, subject to substitution by a larger array when necessary). This is different from SortedDictionary<,> which I believe is a binary search tree.

Note however: You will not be able to have duplicates in your SortedList<,>, so two members in the list are not allowed to CompareTo each other with return value zero.