C #: Is SortedDictionary sorted when you list it?

Question

A SorteDictionary corresponds to an MSDN sorted by key. Does this mean that you can be sure that it will be sorted when you list it in foreach? Or does it just mean that SortedDictionary works this way internally to have better performance on various occasions?

Answer 1

When you list a collection, it is sorted by key (even if you list the Values command). Internally, the collection is implemented as a binary search tree (according to the documentation). Inserting and searching for values ​​is O (log n) (which means they are quite efficient).

Answer 2

From MSDN :

The dictionary is maintained in a sorted order using the internal tree. Each new item is positioned at the correct sorting position, and the tree is adjusted to maintain the sort order whenever the item is deleted. While enumeration, sort order is supported.

Answer 3

Yes, that’s exactly what it means.

Edit: the part that says: “Does this mean that you can be sure that it will be sorted when you list it in foreach?”

Answer 4

If you list items in a SortedDictionary , the items will be returned in the sort order of the item keys. And if you list the keys in a SortedDictionary , the keys will also be returned in sorted order. And, perhaps somewhat surprisingly, if you list the SortedDictionary values ​​by its values, the values ​​will be returned in the sort order of the keys, rather than the sort order of the values ​​as you might expect.

Demonstration:

Note that in this demo, items added to SortedDictionary are not added in sorted order.

In addition, if you plan to list a dictionary by its values ​​and there is the possibility of duplicating the values , consider having a reverse search function to return IEnumerable <T> . (Of course, for large dictionaries, searching for a key by its value can lead to poor performance.)

 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 Result:

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