C# has no SortedList?

Question

I'm trying to solve a problem in which it would be useful to have a data structure like

var list = new SortedList<int>(); 
list.Add(3); // list = { 3 } 
list.Add(1); // list = { 1, 3 }
list.Add(2); // list = { 1, 2, 3 }
int median = list[list.Length / 2];

i.e.

O(n) insertion
O(1) lookup by index

but I can't see that such a thing exists? I see that there's some confusing SortedList<T,U> and then an interface SortedList, but neither of those are what I'm looking for.

https://www.tutorialspoint.com/csharp/csharp_sortedlist.htm ? — Waffles, Jan 28 '17 at 06:54
See http://stackoverflow.com/questions/3663613/why-is-there-no-sortedlistt-in-net — Ian Mercer, Jan 28 '17 at 06:55
Possible duplicate of [Why is there no SortedList in .NET?](http://stackoverflow.com/questions/3663613/why-is-there-no-sortedlistt-in-net) — wake-0, Jan 28 '17 at 07:01
You could always try to [make one yourself](http://www.codedigest.com/Articles/CSHARP/9_Custom_Collection_in_C__-_Part_1.aspx). — Abion47, Jan 28 '17 at 07:21
The main problem with a pure SortedList is with mutable items. With the current SortedList you should use an immutable for the key values — Sir Rufo, Jan 28 '17 at 07:27

score 0 · Answer 1 · answered Jan 28 '17 at 16:15

The sorted list in the .NET framework is an associative list (that is it is for key/value pairs). You can use a regular List<T> if you use its binary search functionality, which works if you keep the list sorted at all times. You can encapsulate it in an extension method:

static class SortedListExtensions {
    public static void SortedAdd<T>(this List<T> list, T value) {
        int insertIndex = list.BinarySearch(value);
        if (value < 0) {
            value = ~value;
        }
        list.Insert(insertIndex, value);
    }

    //Added bonus: a faster Contains method
    public static bool SortedContains<T>(this List<T> list, T value) {
        return list.BinarySearch(value) >= 0;
    }
}


List<int> values = new List<int>();
values.SortedAdd(3);
values.SortedAdd(1);
values.SortedAdd(2);

C# has no SortedList?

1 Answers1