是否可以使用具有正确实现的比较器的 SortedList<>/SortedDictionary<>来保证广告顺序？

Question

如果目标是创建一个保留插入顺序的通用只读字典，则可以SortedList<，>或SortedDictionary<，>可与IComparer一起实际使用<>试图通过做类似于以下的事情来维持插入顺序？

class OrderedComparer<T> : IComparer<M>
{
    public int Compare(M x, M y)
    {
        return x.Equals(y) ? 0 : -1;//or 1
    }
}
SortedList<M> orderedList = new SortedList<M>(new OrderedComparer<T>());

（有趣的是，在SortedDictionary的情况下，上面的方法需要返回0或1，以防止元素按相反的插入顺序排序）。

Answer 1

比较器必须遵守定律

Compare(a, b) == -Compare(b, a) //assuming only possible values are -1, 0, 1

这就是对称性。您的示例代码不遵守它。因此BCL集合根本不能为您提供任何保证。你违反了书面合同。

你不能这样做。

相反，您可以向M添加一个新字段，将插入顺序存储为int。然后可以在比较器中使用该字段。

Answer 2

Compare实现没有遵循它应该遵循的对称规则。这不是正确的做法。

对于按插入顺序排序的列表，只需使用List<T>作为实现即可。另一方面，对于Dictionary<,>，"返回项的顺序是未定义的。"您可以制作自己的IDictionary<,>实现，将这两个类一起使用来完成您想要做的事情。

public class MyInsertionOrderDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    private List<TKey> keysList;
    private Dictionary<TKey, TValue> dict;
    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        foreach (TKey key in keysList)
        {
            TValue value = dict[key];
            yield return new KeyValuePair<TKey, TValue>(key, value);
        }
    }
    // TODO implement interface
    // when adding:
    // keysList.Add(key);
    // dict.Add(key, value);
    // when removing:
    // keysList.Remove(key);
    // dict.Remove(key);
    // you could also implement an indexer property like
    public KeyValuePair<TKey, TValue> this[int index] { get { ... } }
}

这个类在外部与OrderedDictionary类非常相似，但是是泛型的。还有其他通用实现。

Answer 3

毫无疑问，您是否应该做这样可怕的事情。你绝对不应该，因为各种非常好的理由，比如：

• 不要将已排序的容器用于未排序的数据
• 这不是使用比较器的方式
• 避免依赖于您不拥有的库的实现细节

现在，要真正知道是否可以通过破解比较器来保留SortedList中的插入顺序，只有一种方法：查看实现。分解字节码，看看它是否能工作。

事实证明，SortedList使用二进制搜索，而SortedDictionary使用红黑树。

欺骗二进制搜索很容易。比较器仅用于比较新项目（如果未删除任何内容）。总是返回1或-1，我总是忘记是哪一个，而你有一个未排序的列表。

对于红黑树，我不确定同样的技巧是否有效。我不记得这种树在重新平衡自己时是否必须使用比较器。如果是这样，比较器无法提供有意义的结果将导致运行时错误，或者充其量是失去复杂性保证。但也许这真的很好。我认为，除了你仍然会得到最大程度的再平衡。