C#: un SortedDictionary è ordinato quando si enumera su di esso?

Question

Un SorteDictionary è secondo MSDN ordinato sulla chiave. Ciò significa che puoi essere sicuro che sarà ordinato quando lo enumererai in un foreach? O significa solo che SortedDictionary funziona internamente per avere prestazioni migliori in vari casi?

Answer 1

Quando si enumera la raccolta, viene ordinata per chiavi (anche se si enumera la raccolta Values). Internamente la collezione è implementata come un albero di ricerca binario (secondo la documentazione). Sia l'inserimento che la ricerca dei valori sono O (log n) (il che significa che sono piuttosto efficienti).

Answer 2

Sì, questo è esattamente ciò che significa.

Modifica: la parte che dice "Significa che si può essere sicuri che sarà ordinato quando lo si annota in un foreach?"

Answer 3

From MSDN:

Il dizionario è mantenuto in un ordine ordinato usando un albero interno. Ogni nuovo elemento viene posizionato nella posizione di ordinamento corretta e l'albero è corretto per mantenere l'ordinamento ogni volta che viene rimosso un elemento. Mentre Enumerazione , l'ordinamento è gestito.

Answer 4

Se si elencano gli articoli in un SortedDictionary, gli articoli verranno restituiti nell'ordine di ordinamento delle chiavi degli articoli. E se si annoverano con le chiavi in ​​SortedDictionary, le chiavi verranno restituite anche nell'ordine ordinato. E forse un po 'sorprendentemente, se si elencano i valori SortedDictionary, i valori vengono restituiti nell'ordine di ordinamento delle chiavi, non l'ordinamento dei valori come ci si potrebbe aspettare.

Dimostrazione:

Si noti che in questa demo gli elementi aggiunti alla SortedDictionary sono non aggiunto in modo ordinato.

Inoltre, se si prevede di enumerare il dizionario in base ai relativi valori e vi è la possibilità di valori duplicati, considerare la funzione di ricerca inversa return an IEnumerable<T>. (Naturalmente, per i grandi dizionari, alzando una chiave dal suo valore può causare una riduzione delle prestazioni.)

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; 
     } 
    } 
} 

Expected uscita:

== 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