C#：枚举 SortedDictionary 时它是否已排序？

Question

SorteDictionary 是根据 MSDN 对键进行排序的。 这是否意味着当您在 foreach 中枚举它时可以确定它会被排序？ 或者这只是意味着 SortedDictionary 在内部以这种方式工作以便在各种情况下具有更好的性能？

Answer 1

来自 MSDN：

字典维护在
使用内部树排序。
每个新元素都位于
正确的排序位置，树是
调整以保持排序顺序
每当一个元素被删除时。 尽管
枚举，排序顺序为
维护。

Answer 2

当您枚举集合时，它会按键排序（即使您枚举 Values 集合）。 在内部，该集合被实现为二叉搜索树（根据文档）。 值的插入和查找都是 O(log n)（意味着它们非常高效）。

Answer 3

如果您枚举 SortedDictionary 中的项目，这些项目将按项目键的排序顺序返回。 如果您通过 SortedDictionary 中的键进行枚举，键也将按排序顺序返回。 也许有些令人惊讶的是，如果您通过其值枚举 SortedDictionary，则这些值会按键的排序顺序返回，而不是您可能会看到的值的排序顺序预计。

演示：

请注意，在此演示中，添加到 SortedDictionary 的项目未按排序顺序添加。

另外，如果您打算按字典的值枚举字典，并且可能存在重复值，请考虑使用反向查找功能返回一个 IEnumerable。 （当然，对于大型字典，通过值查找键可能会导致性能不佳。）

using System;
using System.Collections.Generic;
using System.Linq;

class SortedDictionaryEnumerationDemo
{
    static void Main()
    {
        var dict = new SortedDictionary<int, string>();
        dict.Add(4, "Four");
        dict.Add(5, "Five");
        dict.Add(1, "One");
        dict.Add(3, "Three");
        dict.Add(2, "Two");

        Console.WriteLine("== Enumerating Items ==");
        foreach (var item in dict)
        {
            Console.WriteLine("{0} => {1}", item.Key, item.Value);
        }

        Console.WriteLine("\n== Enumerating Keys ==");
        foreach (int key in dict.Keys)
        {
            Console.WriteLine("{0} => {1}", key, dict[key]);
        }

        Console.WriteLine("\n== Enumerating Values ==");
        foreach (string value in dict.Values)
        {
            Console.WriteLine("{0} => {1}", value, GetKeyFromValue(dict, value));
        }
    }

    static int GetKeyFromValue(SortedDictionary<int, string> dict, string value)
    {
        // Use LINQ to do a reverse dictionary lookup.
        try
        {
            return
                (from item in dict
                 where item.Value.Equals(value)
                 select item.Key).First();
        }
        catch (InvalidOperationException e)
        {
            return -1;
        }
    }
}

预期输出：

== Enumerating Items ==
1 => One
2 => Two
3 => Three
4 => Four
5 => Five

== Enumerating Keys ==
1 => One
2 => Two
3 => Three
4 => Four
5 => Five

== Enumerating Values ==
One => 1
Two => 2
Three => 3
Four => 4
Five => 5

Answer 4

是的，这正是它的意思。

编辑：“这是否意味着当您在 foreach 中枚举它时可以确定它会被排序？”的部分