10

SorteDictionaryは、MSDNに従ってキーでソートされています。これは、foreachで列挙するときに、確実にソートされることを意味しますか？それとも、SortedDictionaryが内部的にそのように機能して、さまざまなケースでパフォーマンスが向上することを意味するのでしょうか。

4

4 に答える 4

11

MSDNから：

辞書は、内部ツリーを使用してソートされた順序で維持されます。すべての新しい要素は正しい並べ替え位置に配置され、要素が削除されるたびに並べ替え順序が維持されるようにツリーが調整されます。列挙中、ソート順は維持されます。

于 2009-07-16T08:33:48.800 に答える
6

コレクションを列挙すると、キーで並べ替えられます（コレクションと言っても列挙しますValues）。内部的には、コレクションはバイナリ検索ツリーとして実装されます（ドキュメントによる）。値の挿入とルックアップはどちらもO（log n）です（つまり、かなり効率的です）。

于 2009-07-16T08:32:24.013 に答える
0

はい、それはまさにそれが意味することです。

編集：「foreachで列挙するときにソートされることを確認できるということですか？」という部分。

于 2009-07-16T08:29:43.083 に答える
0

でアイテムを列挙するSortedDictionaryと、アイテムはアイテムキーの並べ替え順序で返されます。また、のキーで列挙すると、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
于 2014-03-06T17:06:50.147 に答える