c# - 维护按值排序的键值对列表的最简单方法是什么？

Question

每个键在列表中都是唯一的。当一个新的键值对到达时，该对按值的升序插入到列表中（如果键已经存在，则更新值）。

请避免为每次插入对列表进行排序。

Answer 1

您不会获得具有这种行为的内置组件，它太不标准了。我会研究为什么以及何时需要这些竞争行为。实际上，您正在查看备用键。除了写一些 for 的链表之外，在我的脑海中，我会查看 SortedList 的按值部分，以及字典的键。例如

CustomerID 和 SortKey 的 Dictionary 以及 SortKey 和 value 的 SortedList。

如果可以的话，我会尽量避免它，因为维护两者的成本比在需要时简单地按所需顺序返回值列表的成本更高。

Answer 2

我会建议 SortedDictionary 或 SortedList

根据 MSDN：

SortedList 使用的内存比 SortedDictionary 少。

SortedDictionary 对未排序的数据具有更快的插入和删除操作：O(log n) 相对于 SortedList 的 O(n)。

更新：评论后

您将不得不自己订购价值，例如使用字典

    var dictionary = new Dictionary<int, string>{ {1, "Z"}, {2, "A"}};
    IOrderedEnumerable<KeyValuePair<int, string>> orderedEnumerable = dictionary.OrderBy(d => d.Value);

Answer 3

如果可以接受对每个枚举的项目进行排序，则可以使用Dictionary<TKey, TValue>并在枚举时按值对键值对进行排序：

var dict = new Dictionary<MyKey, MyValue>();

// insertion (updates value when key already exists)
dict[key] = value;

// enumeration (ordered by value)
foreach (var keyValuePair in dict.OrderBy(kvp => kvp.Value))
{
    ...
}

Answer 4

我会写一个像下面这样的临时类（未完全测试）：

public class DictionarySortedByValue<TKey, TValue> : IDictionary<TKey, TValue>
{
    class ValueWrapper : IComparable, IComparable<ValueWrapper>
    {
        public TKey Key { get; private set; }
        public TValue Value { get; private set; }

        public ValueWrapper(TKey k, TValue v)
        {
            this.Key = k;
            this.Value = v;
        }
        public int CompareTo(object obj)
        {
            if (!(obj is ValueWrapper))
                throw new ArgumentException("obj is not a ValueWrapper type object");
            return this.CompareTo(obj as ValueWrapper);
        }
        public int CompareTo(ValueWrapper other)
        {
            int c = Comparer<TValue>.Default.Compare(this.Value, other.Value);
            if (c == 0)
                c = Comparer<TKey>.Default.Compare(this.Key, other.Key);
            return c;
        }
    }

    private SortedSet<ValueWrapper> orderedElements;
    private SortedDictionary<TKey, TValue> innerDict;

    public DictionarySortedByValue()
    {
        this.orderedElements = new SortedSet<ValueWrapper>();
        this.innerDict = new SortedDictionary<TKey, TValue>();
    }

    public void Add(TKey key, TValue value)
    {
        var wrap = new ValueWrapper(key, value);
        this.innerDict.Add(key, value);
        this.orderedElements.Add(wrap);
    }

    public bool ContainsKey(TKey key)
    {
        return this.innerDict.ContainsKey(key);
    }

    public ICollection<TKey> Keys
    {
        get { return this.innerDict.Keys; }
    }

    public bool Remove(TKey key)
    {
        TValue val;
        if (this.TryGetValue(key, out val))
        {
            var wrap = new ValueWrapper(key, val);
            this.orderedElements.Remove(wrap);
            this.innerDict.Remove(key);
            return true;
        }
        return false;
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        return this.innerDict.TryGetValue(key, out value);
    }

    public ICollection<TValue> Values
    {
        get { return this.innerDict.Values; }
    }

    public TValue this[TKey key]
    {
        get
        {
            return this.innerDict[key];
        }
        set
        {
            bool removed = this.Remove(key);
            this.Add(key, value);
        }
    }

    public void Add(KeyValuePair<TKey, TValue> item)
    {
        this.Add(item.Key, item.Value);
    }

    public void Clear()
    {
        this.innerDict.Clear();
        this.orderedElements.Clear();
    }

    public bool Contains(KeyValuePair<TKey, TValue> item)
    {
        var wrap = new ValueWrapper(item.Key,item.Value);
        return this.orderedElements.Contains(wrap);
    }

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
    {
        this.innerDict.CopyTo(array, arrayIndex);
    }

    public int Count
    {
        get { return this.innerDict.Count; }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }

    public bool Remove(KeyValuePair<TKey, TValue> item)
    {
        if (this.Contains(item))
            return this.Remove(item.Key);
        return false;
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        foreach (var el in this.orderedElements)
            yield return new KeyValuePair<TKey, TValue>(el.Key, el.Value);
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }
}

备注：

• 它还要求该TKey类型实现 IComparable。
• 发布的代码仅使用 TKey 和 TValue 的默认比较器，但您可以通过另一个构造函数传递自定义比较器。