C#: Wird ein SortedDictionary beim Aufzählen sortiert?

Question

Ein SorteDictionary wird nach MSDN nach dem Schlüssel sortiert. Bedeutet das, dass Sie sicher sein können, dass es sortiert wird, wenn Sie es in einer foreach aufzählen? Oder bedeutet es nur, dass das SortedDictionary intern so funktioniert, dass es in verschiedenen Fällen bessere Leistung bringt?

Answer 1

Wenn Sie die Auflistung auflisten, wird sie nach Schlüsseln sortiert (selbst wenn Sie die Values Auflistung aufzählen). Intern wird die Sammlung als binärer Suchbaum implementiert (gemäß der Dokumentation). Sowohl das Einfügen als auch das Nachschlagen von Werten ist O (log n) (was bedeutet, dass sie ziemlich effizient sind).

Answer 2

Ja, genau das ist es.

Edit: der Teil, der sagt "Bedeutet das, dass Sie sicher sein können, dass es sortiert wird, wenn Sie es in einer foreach aufzählen?"

Answer 3

From MSDN:

Das Wörterbuch in einem sortierte gehalten, um einen internen Baum verwendet wird. Jedes neue Element wird an der korrekten Sortierposition positioniert, und der Baum wird angepasst, um die Sortierreihenfolge beizubehalten, wenn ein Element entfernt wird. Während aufgelistet wird, wird die Sortierreihenfolge beibehalten.

Answer 4

Wenn Sie die Elemente in einem SortedDictionary auflisten, werden die Elemente in der Sortierreihenfolge der Elementschlüssel zurückgegeben. Und wenn Sie mit den Schlüsseln im SortedDictionary aufzählen, werden die Schlüssel auch in sortierter Reihenfolge zurückgegeben. Und vielleicht etwas überraschend, wenn Sie die SortedDictionary durch seine Werte auflisten, werden die Werte in der Sortierreihenfolge der Schlüssel, nicht die Sortierreihenfolge der Werte zurückgegeben, wie Sie erwarten können.

Demonstration:

Beachten Sie, dass die Elemente in dieser Demo zum SortedDictionary hinzugefügt sind nicht in sortierter Reihenfolge hinzugefügt.

Auch, wenn Sie durch ihre Werte Ihr Wörterbuch aufzuzählen planen und es gibt eine Möglichkeit, doppelte Werte, betrachten Sie Ihre Reverse-Lookup-Funktion return an IEnumerable<T> mit. (Natürlich für große Wörterbücher, sucht einen Schlüssel durch seinen Wert kann bis zu einer schlechten Leistung zur Folge hat.)

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

Ausgang Erwartet:

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