C# не имеет SortedList <T>?

Question

Я пытаюсь решить проблему, в которой было бы полезно иметь структуру данных, как

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]; 

т.е.

• О (п) вставки
• O (1) поиск по индекс

но я не вижу, что такое существует? Я вижу, что есть некоторые запутывающие SortedList<T,U>, а затем интерфейс SortedList, но ни один из них не является тем, что я ищу.

Answer 1

Сортированный список в .NET framework представляет собой ассоциативный список (то есть для пар ключ/значение). Вы можете использовать обычный List<T>, если вы используете его функцию бинарного поиска, которая работает, если вы всегда держите список отсортированным. Вы можете инкапсулировать в метод расширения:

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);