ReversibleSortedList<TKey, TValue> 核心原始碼解析：公有方法完整實現

前言

ReversibleSortedList<TKey, TValue> 是一個支援動態反轉排序方向的泛型排序字典實作。本文呈現其完整公有方法原始碼，涵蓋新增、移除、查詢、排序、列舉等核心功能，展示如何基於陣列實現高效的有序鍵值對集合。

核心欄位與輔助結構

類別內部維護兩個平行陣列：

• keys：TKey[]，依排序順序儲存鍵
• values：TValue[]，對應儲存值
• _size：目前元素數量
• _sortDirectionComparer：SortDirectionComparer<TKey>，封裝升序/降序邏輯
• version：修改版本號，供列舉器檢測集合變更

關鍵方法實現詳解

Add(TKey, TValue) - 二分搜尋定位插入點

public void Add(TKey key, TValue value)
{
    if (key.Equals(null)) throw new ArgumentNullException("key");
    int index = Array.BinarySearch(keys, 0, _size, key, _sortDirectionComparer);
    if (index >= 0) throw new ArgumentException("Attempting to add duplicate");
    Insert(~index, key, value); // ~index 為補數，取得插入位置
}

利用 Array.BinarySearch 回傳負數的補數特性，O(log n) 定位插入位置，再由 Insert 位移陣列元素。

Insert(int index, TKey, TValue) - 陣列位移與擴容

若容量不足自動擴容（雙倍策略），再以 Array.Copy 將 index 之後元素向後移動一格，寫入新鍵值，更新 _size 與 version。

RemoveAt(int index) - 陣列前移與清理

邊界檢查後，將 index 之後元素向前移動一格，最後位置設為 default(T) 釋放參考，避免記憶體洩漏。

IndexOfKey / ContainsKey - 二分搜尋 O(log n)

直接呼叫 Array.BinarySearch，負數表示不存在。

IndexOfValue / ContainsValue - 線性掃描 O(n)

值未排序，只能 Array.IndexOf 逐一比對。

Sort() - 就地反轉陣列

public void Sort()
{
    if (_currentSortDirection != _sortDirectionComparer.SortDirection)
    {
        Array.Reverse(keys, 0, _size);
        Array.Reverse(values, 0, _size);
        _currentSortDirection = _sortDirectionComparer.SortDirection;
    }
}

若排序方向改變，直接 Array.Reverse 兩平行陣列，O(n) 完成重排，避免完整重排序的 O(n log n) 成本。

TrimExcess() - 釋放多餘容量

當使用率低於 90% 時，將 Capacity 設為 _size，觸發陣列重新配置縮減記憶體佔用。

TryGetValue - 結合二分搜尋與輸出參數

先 IndexOfKey，找到則輸出值並回傳 true，否則輸出 default(TValue) 回傳 false。

GetEnumerator - 結構體列舉器模式

回傳內部 struct Enumerator<K, V>，實作 IEnumerator<KeyValuePair<TKey, TValue>>，避免列舉時配置物件，提升熱路徑效能。

介面實現完整性

類別完整實作：

• IDictionary<TKey, TValue>
• ICollection<KeyValuePair<TKey, TValue>>
• IEnumerable<KeyValuePair<TKey, TValue>>
• 非泛型 IDictionary、ICollection、IEnumerable

並標記 [Serializable]、[ComVisible(false)]、[DebuggerDisplay] 屬性，符合框架級元件標準。

總結

ReversibleSortedList 展示了如何以雙平行陣列 + 自訂比較器構建高效能有序字典。其核心亮點在於：

1. 二分搜尋保證鍵操作 O(log n)
2. 就地反轉實現 O(n) 動態排序切換
3. 結構體列舉器消除列舉配置
4. 完整介面實現確保生態相容性

原始碼規範、註解完整，堪稱商業級集合實作的教科書範例。