C#: Является ли SortedDictionary отсортированным, когда вы перечислите его?

Question

A 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