您现在的位置：程式碼之家 >> 編程語言 > >> .NET 網頁程式設計 >> C# >> 關於C#

構建可反轉排序的泛型字典 (3/9)：元素添加、二分查找插入與自動擴容機制

編輯：關於C#

核心數據結構

兩個平行陣列：`TKey[] _keys`、`TValue[] _values`
元素始終按鍵**有序排列**（降序預設）
`int _size` 記錄當前元素數量（區別於陣列長度 `Capacity`）

自動擴容策略

初始容量 0
首次添加 → 容量 4
後續滿容時 → 容量翻倍（2×）
擴容本質：分配新陣列 → `Array.Copy` 舊數據 → 替換引用（舊陣列變垃圾）

完整實現代碼


public class ReversibleSortedList
{
    #region 欄位
    private TKey[] _keys = Array.Empty();
    private TValue[] _values = Array.Empty();
    private SortDirectionComparer _comparer;
    private int _size;
    private int _version;
    #endregion

    #region 構造函數
    public ReversibleSortedList()
    {
        _comparer = new SortDirectionComparer(); // 預設降序
    }
    #endregion

    #region 屬性
    public int Count => _size;
    public int Capacity => _keys.Length;
    #endregion

    #region 核心公有方法
    public void Add(TKey key, TValue value)
    {
        if (key == null) throw new ArgumentNullException(nameof(key));

        // 二分查找插入位置
        int index = Array.BinarySearch(_keys, 0, _size, key, _comparer);
        if (index >= 0) throw new ArgumentException("鍵已存在");

        // ~index 為補碼，轉為正數插入位置
        Insert(~index, key, value);
    }
    #endregion

    #region 私有輔助方法
    private void Insert(int index, TKey key, TValue value)
    {
        // 確保容量
        if (_size == _keys.Length) EnsureCapacity(_size + 1);

        // 移動元素騰出空位
        if (index < _size)
        {
            Array.Copy(_keys, index, _keys, index + 1, _size - index);
            Array.Copy(_values, index, _values, index + 1, _size - index);
        }

        _keys[index] = key;
        _values[index] = value;
        _size++; _version++;
    }

    private void EnsureCapacity(int min)
    {
        int newCap = _keys.Length == 0 ? 4 : _keys.Length * 2;
        if (newCap < min) newCap = min;
        InternalSetCapacity(newCap);
    }

    private void InternalSetCapacity(int capacity)
    {
        if (capacity < _size) throw new ArgumentOutOfRangeException(nameof(capacity));
        if (capacity != _keys.Length)
        {
            var newKeys = new TKey[capacity];
            var newValues = new TValue[capacity];
            if (_size > 0)
            {
                Array.Copy(_keys, 0, newKeys, 0, _size);
                Array.Copy(_values, 0, newValues, 0, _size);
            }
            _keys = newKeys;
            _values = newValues;
        }
    }
    #endregion

    #region 比較器：支援升/降序切換
    public class SortDirectionComparer : IComparer
    {
        private ListSortDirection _dir = ListSortDirection.Descending;
        public ListSortDirection SortDirection { get => _dir; set => _dir = value; }

        public int Compare(T x, T y)
        {
            int result = Comparer.Default.Compare(x, y);
            return _dir == ListSortDirection.Descending ? -result : result;
        }
    }
    #endregion

    #region 測試用 Print 方法
    public void Print()
    {
        for (int i = 0; i < _size; i++)
            Console.WriteLine($"Key: {_keys[i]}, Value: {_values[i]}");
    }
    #endregion
}

測試驗證


static void Main()
{
    var rs = new ReversibleSortedList();
    rs.Add(3, "a"); rs.Add(1, "b"); rs.Add(2, "c"); rs.Add(6, "d");
    rs.Print(); Console.WriteLine($"Cap={rs.Capacity}, Count={rs.Count}");
    // 輸出: 6d, 3a, 2c, 1b (降序) | Cap=4, Count=4

    rs.Add(5, "e"); rs.Add(4, "f");
    rs.Print(); Console.WriteLine($"Cap={rs.Capacity}, Count={rs.Count}");
    // 輸出: 6d, 5e, 4f, 3a, 2c, 1b | Cap=8, Count=6

    rs.Add(8, "g"); rs.Add(7, "h"); rs.Add(9, "i");
    rs.Print(); Console.WriteLine($"Cap={rs.Capacity}, Count={rs.Count}");
    // 輸出: 9i, 8g, 7h, 6d, 5e, 4f, 3a, 2c, 1b | Cap=16, Count=9
}