SortedList

SortedList 表示键/值对的集合，这些键/值对基于关联的 System.Collections.Generic.IComparer<T> 实现按照键进行升序排序

public class SortedList<TKey, TValue> : IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IDictionary, ICollection, IEnumerable

其内部维护了两个动态数组keys[],values[]，每增加一个新的元素时，调用排序方法找到新增key的顺序位置，然后插入，如有重复key则抛出exception,其排序方法基于二分法排序：

public virtual void Add(object key, object value)
{
    if (key == null)
    {
        throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));
    }
    int index = Array.BinarySearch(this.keys, 0, this._size, key, this.comparer);
    if (index >= 0)
    {
        throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", new object[] { this.GetKey(index), key }));
    }
    this.Insert(~index, key, value);
}

Array.BinarySearch为二分查找法，源码实现如下，：

public static int BinarySearch(Array array, int index, int length, object value, IComparer comparer)
{
    int num2;
    if (array == null)
    {
        throw new ArgumentNullException("array");
    }
    int lowerBound = array.GetLowerBound(0);
    if ((index < lowerBound) || (length < 0))
    {
        throw new ArgumentOutOfRangeException((index < lowerBound) ? "index" : "length", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
    }
    if ((array.Length - (index - lowerBound)) < length)
    {
        throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
    }
    if (array.Rank != 1)
    {
        throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
    }
    if (comparer == null)
    {
        comparer = Comparer.Default;
    }
    if ((comparer == Comparer.Default) && TrySZBinarySearch(array, index, length, value, out num2))
    {
        return num2;
    }
    int low = index;
    int hi = (index + length) - 1;
    object[] objArray = array as object[];
    if (objArray == null)
    {
        while (low <= hi)
        {
            int num8;
            int median = GetMedian(low, hi);
            try
            {
                num8 = comparer.Compare(array.GetValue(median), value);
            }
            catch (Exception exception2)
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), exception2);
            }
            if (num8 == 0)
            {
                return median;
            }
            if (num8 < 0)
            {
                low = median + 1;
            }
            else
            {
                hi = median - 1;
            }
        }
    }
    else
    {
        while (low <= hi)
        {
            int num6;
            int num5 = GetMedian(low, hi);
            try
            {
                num6 = comparer.Compare(objArray[num5], value);
            }
            catch (Exception exception)
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), exception);
            }
            if (num6 == 0)
            {
                return num5;
            }
            if (num6 < 0)
            {
                low = num5 + 1;
            }
            else
            {
                hi = num5 - 1;
            }
        }
    }
    return ~low;
}