C# 中的通用有序字典

• 下载源代码 - 10.4 KB
• 从 GitHub 下载最新版本

引言

本文介绍了一个 OrderedDictionary<TKey,TValue> 类，你可以在你的项目中用到它，因为 Microsoft 的 OrderedDictionary 类没有泛型版本。 这不是对有序字典的封装，而是对其进行重写，以避免装箱和拆箱。

背景

标准的 IDictionary<TKey,TValue> 容器不能保证保留项目的顺序。 但是，有时你需要一个容器，允许你通过键或索引来访问。 这个类就是为此目的而设计的。

Using the Code

代码通过 partial 类分成几个部分，以便于阅读和导航。 以下是有序字典的核心，位于 OrderedDictionary.cs 中

/// <summary>
/// Represents a dictionary where the items are in an explicit and indexable order
/// </summary>
/// <typeparam name="TKey">The type of the keys in this dictionary</typeparam>
/// <typeparam name="TValue">The type of the values in this dictionary</typeparam>
public partial class OrderedDictionary<TKey,TValue>
{
    // we keep these synced
    List<KeyValuePair<TKey,TValue>> _innerList;
    Dictionary<TKey, TValue> _innerDictionary;
    IEqualityComparer<TKey> _comparer = null;
    /// <summary>
    /// Creates an ordered dictionary with the specified capacity and comparer
    /// </summary>
    /// <param name="capacity">The initial capacity</param>
    /// <param name="comparer">The comparer</param>
    public OrderedDictionary(int capacity,IEqualityComparer<TKey> comparer)
    {
        _innerDictionary = new Dictionary<TKey, TValue>(capacity, comparer);
        _innerList = new List<KeyValuePair<TKey,TValue>>(capacity);
        _comparer = comparer;
    }
    /// <summary>
    /// Creates an ordered dictionary with the specified items and the specified comparer
    /// </summary>
    /// <param name="collection">The collection or dictionary to copy from</param>
    /// <param name="comparer">The comparer to use</param>
    public OrderedDictionary(IEnumerable<KeyValuePair<TKey,TValue>> collection, 
                             IEqualityComparer<TKey> comparer)
    {
        _innerDictionary = new Dictionary<TKey, TValue>(comparer);
        _innerList = new List<KeyValuePair<TKey, TValue>>();
        _AddValues(collection);
        _comparer = comparer;
    }
    /// <summary>
    /// Creates an ordered dictionary with the specified capacity
    /// </summary>
    /// <param name="capacity">The initial capacity</param>
    public OrderedDictionary(int capacity)
    {
        _innerDictionary = new Dictionary<TKey, TValue>(capacity);
        _innerList = new List<KeyValuePair<TKey, TValue>>(capacity);
    }
    /// <summary>
    /// Creates an ordered dictionary filled with the specified collection or dictionary
    /// </summary>
    /// <param name="collection">The collection or dictionary to copy</param>
    public OrderedDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection)
    {
        _innerDictionary = new Dictionary<TKey, TValue>();
        _innerList = new List<KeyValuePair<TKey, TValue>>();
        _AddValues(collection);
    }
    /// <summary>
    /// Creates an ordered dictionary with the specified comparer
    /// </summary>
    /// <param name="comparer">The equality comparer to use for the keys</param>
    public OrderedDictionary(IEqualityComparer<TKey> comparer)
    {
        _innerDictionary = new Dictionary<TKey, TValue>(comparer);
        _innerList = new List<KeyValuePair<TKey, TValue>>();
        _comparer = comparer;
    }
    /// <summary>
    /// Creates a default instance of the ordered dictionary
    /// </summary>
    public OrderedDictionary()
    {
        _innerDictionary = new Dictionary<TKey, TValue>();
        _innerList = new List<KeyValuePair<TKey, TValue>>();
    }
    /// <summary>
    /// Gets the value at the specified index
    /// </summary>
    /// <param name="index">The index of the value to retrieve</param>
    /// <returns>The value of the item at the specified index</returns>
    public TValue GetAt(int index)
    {
        return _innerList[index].Value;
    }
    /// <summary>
    /// Sets the value at the specified index
    /// </summary>
    /// <param name="index">The index of the value to set</param>
    /// <param name="value">The new value to assign</param>
    public void SetAt(int index,TValue value)
    {
        var key = _innerList[index].Key;
        _innerList[index] = new KeyValuePair<TKey, TValue>(key, value);
        _innerDictionary[key] = value;
    }
    /// <summary>
    /// Inserts an item into the ordered dictionary at the specified position
    /// </summary>
    /// <param name="index">The index to insert the item before</param>
    /// <param name="key">The key of the new item</param>
    /// <param name="value">The value of the new item</param>
    public void Insert(int index, TKey key, TValue value)
        => (this as IList<KeyValuePair<TKey, TValue>>).Insert
           (index, new KeyValuePair<TKey, TValue>(key, value));
    
    void _AddValues(IEnumerable<KeyValuePair<TKey,TValue>> collection)
    {
        foreach (var kvp in collection)
        {
            _innerDictionary.Add(kvp.Key, kvp.Value);
            _innerList.Add(kvp);
        }
    }
}

如你所见，这个类实现了标准的 Dictionary<TKey,TValue> 构造函数。 使用它们的方式完全相同。 它还有一些额外的函数，例如 GetAt() 和 SetAt()。 这些函数以及其他函数允许你通过索引访问字典。 字典还实现了列表接口 - IList<KeyValuePair<TKey,TValue>>，允许你将整个容器视为键/值对的索引列表。 当然，它也实现了标准的字典接口。

所有查找都是哈希表查找或索引查找。 这意味着它们速度很快。 由于需要保持两个容器同步，因此添加、插入、设置和删除方法比标准的字典稍慢。

使用方法在演示程序中有所演示。 祝你使用愉快！

关注点

为了完成所有操作，我们需要每个 TKey 和 TValue 条目的两个副本 - 一个集合在列表中，另一个集合在字典中。 这是必需的。 没有其他方法可以在不镜像两个容器之间所有数据的情况下有效地提供所有操作。 权衡是牺牲更多的内存来换取更高的速度。

历史

• 2019 年 11 月 20 日 - 首次提交