C#: Là một SortedDictionary được sắp xếp khi bạn liệt kê nó?

Question

A SorteDictionary theo MSDN được sắp xếp trên khóa. Điều đó có nghĩa là bạn có thể chắc chắn rằng nó sẽ được sắp xếp khi bạn liệt kê nó trong một foreach? Hay nó chỉ có nghĩa là SortedDictionary hoạt động theo cách nội bộ để có hiệu suất tốt hơn trong các trường hợp khác nhau?

Answer 1

Khi bạn liệt kê bộ sưu tập nó được sắp xếp theo phím (ngay cả khi bạn liệt kê nói bộ sưu tập Values). Nội bộ bộ sưu tập được thực hiện như một cây tìm kiếm nhị phân (theo tài liệu). Cả việc chèn và tra cứu các giá trị là O (log n) (nghĩa là chúng khá hiệu quả).

Answer 2

Vâng, đó là chính xác những gì nó có nghĩa.

Edit: phần mà nói "Điều đó có nghĩa rằng bạn có thể chắc chắn rằng nó sẽ được sắp xếp khi bạn liệt kê nó trong một foreach?"

Answer 3

From MSDN:

Từ điển được duy trì theo một thứ tự sắp xếp sử dụng một cây nội. Mỗi phần tử mới sẽ được đặt tại các vị trí loại chính xác, và cây là điều chỉnh để duy trì thứ tự sắp xếp bất cứ khi nào một yếu tố được lấy ra. Trong khi liệt kê, thứ tự sắp xếp là duy trì.

Answer 4

Nếu bạn liệt kê các mục trong một SortedDictionary, các mục sẽ được trả lại theo thứ tự sắp xếp của các khóa mục. Và nếu bạn liệt kê các phím trong số SortedDictionary, các phím cũng sẽ được trả lại theo thứ tự được sắp xếp. Và có lẽ hơi ngạc nhiên, nếu bạn liệt kê các SortedDictionary bởi giá trị của nó, các giá trị được trả về trong thứ tự sắp xếp của các phím, không thứ tự sắp xếp của các giá trị như bạn mong đợi.

diễn:

Lưu ý rằng trong bản demo này các hạng mục bổ sung vào SortedDictionary là không thêm vào trong thứ tự sắp xếp.

Ngoài ra, nếu bạn dự định liệt kê từ điển của mình theo giá trị của nó và có khả năng giá trị trùng lặp, hãy xem xét có chức năng tra cứu ngược lại return an IEnumerable<T>. (Tất nhiên, đối với các từ điển lớn, nhìn lên một chìa khóa bởi giá trị của nó có thể dẫn đến hiệu suất kém.)

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

Dự kiến ​​Output:

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