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

Question

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

Answer 1

来自 MSDN：

字典使用内部树按排序顺序维护。每个新元素都定位在正确的排序位置，并且每当删除一个元素时，都会调整树以保持排序顺序。枚举时，排序顺序保持不变。

Answer 2

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

Answer 3

是的，这正是它的意思。

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

Answer 4

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

示范：

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

此外，如果您计划按其值枚举您的字典并且存在重复值的可能性，请考虑让您的反向查找函数返回一个 IEnumerable<T>。（当然，对于大型字典，按值查找键可能会导致性能不佳。）

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