C＃：SortedDictionaryは列挙したときソートされますか？

Question

SorteDictionaryはMSDNに準拠しており、キーに基づいてソートされています。それは、あなたがforeachでそれを列挙するときにソートされることを確実にすることができるということですか？または、SortedDictionaryがさまざまなケースでパフォーマンスを向上させるために内部的に動作することを意味しますか？

Answer 1

コレクションを列挙すると、コレクションによって列挙されます（たとえ列挙したとしてもValuesコレクション）。内部的には、コレクションはバイナリ検索ツリーとして実装されています（ドキュメントに従って）。挿入と参照の両方ともO（log n）（かなり効率的です）です。

Answer 2

はい、まさにその意味です。

編集：「foreachで列挙したときにソートされることを確実に確認できますか？

Answer 3

From MSDN：

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

Answer 4

SortedDictionaryの項目を列挙すると、項目は項目キーの並べ替え順に返されます。 SortedDictionaryのキーで列挙すると、キーもソート順に返されます。おそらく驚くべきことに、SortedDictionaryをその値で列挙すると、キーのソート順に値が返されます。ではなく、の値のソート順が予想されます。

デモンストレーション：アイテムがSortedDictionaryに追加このデモでソートされた順序で追加さないあること

注意。

また、その値で辞書を列挙し、の重複する可能性がある場合は、逆引き参照機能return an 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