一个实现了合适比较器的 SortedList<> / SortedDictionary<> 是否能用来保证插入顺序？

Question

如果目标是创建一个通用的只读字典，保留插入顺序，是否可以可靠地使用带有试图通过执行类似以下操作来维护插入顺序的IComparer<>的 SortedList<,> 或 SortedDictionary<,>?

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，以防止元素按相反的插入顺序排序。

- J Smith

---

你到底想要实现什么目标？List<>和Queue<>都按照它们被添加的顺序列出项目。 - n8wrl

@n8wrl 目标是创建一个通用的只读字典。 - nawfal

Answer 1

比较器必须遵守法律

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

这是对称性质。你的示例代码没有遵守它。因此BCL集合根本不会给你任何保证。你已经违反了文档约定。

你不能这样做。

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

- usr

---

重要提示：正确的“规则”应该是 Compare(a,b) > 0 == Compare(b,a) < 0 && (Compare(a,b) == 0) == (Compare(b,a) == 0) && Compare(a,b) < 0 == Compare(b,a) > 0。在只有可能输出-1、0、1时，答案中所述的是简化形式。 - Scott Chamberlain

是的，我太懒了，不想打这个...谢谢！ - usr

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 类非常相似，但是它是通用的。还有其他通用实现可用。

- Tim S.

---

好主意，但我会做的唯一更改是只使用 OrderedDictionary 而不是 Dictionary<TKey,TValue> 和 List<TValue>，并且在调用任何从内部集合返回 object 的方法时只进行必要的转换。 - Scott Chamberlain

@ScottChamberlain 是的，那是另一个选项。但是，与直接使用泛型不同的是，这意味着装箱、拆箱和强制转换将在运行时发生。虽然这可能不是一个大问题，但这确实会有一些性能损失，特别是对于struct（例如int）。 - Tim S.

Answer 3

毫无疑问，你不应该做这么可怕的事情。出于各种完全合理的原因，你绝对不应该这样做，例如：

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

现在，要想确切地知道是否可以通过黑客攻击比较器来保留插入顺序的SortedList，只有一种方法：查看其实现。反编译字节码，并查看它能否工作。

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

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

对于红黑树，我不确定是否适用同样的技巧。我不记得这种类型的树在重新平衡时是否必须使用比较器。如果需要，你的比较器无法提供有意义的结果可能会导致运行时错误，或者最好情况下会失去复杂度保证。但也许实际上没问题。除了你仍然会得到最大量的重新平衡，我想。

- Eldritch Conundrum