C #: É um SortedDictionary classificado quando você enumerar sobre isso?

Question

A SorteDictionary está de acordo com MSDN classificadas na chave. Isso significa que você pode ter certeza que ele vai ser resolvido quando você enumerar-lo em um foreach? Ou será que ele apenas significa que o SortedDictionary funciona dessa forma internamente para ter melhor desempenho em vários casos?

Answer 1

Quando você enumerar a coleção é classificado por chaves (mesmo se você enumerar dizer a coleção Values). Internamente, a coleção é implementada como uma árvore de busca binária (de acordo com a documentação). Ambos inserção e pesquisa de valores são O (N log N) (o que significa que são muito eficiente).

Answer 2

De MSDN :

O dicionário é mantida em um ordem de classificação usando uma árvore interna. Cada novo elemento é posicionado no posição espécie correta, ea árvore é ajustada para manter a ordem de classificação sempre que um elemento é removido. Enquanto enumerando, a ordem de classificação é mantida.

Answer 3

Sim, isso é exatamente o que significa.

Edit: a parte que diz "? Isso significa que você pode ter certeza que ele vai ser resolvido quando você enumerar-lo em um foreach"

Answer 4

Se você enumerar os itens em um SortedDictionary, os itens serão devolvidos na ordem de classificação das chaves item. E se você enumerar pelas chaves na SortedDictionary, as teclas também serão retornados em ordem classificada. E talvez um pouco surpreendentemente, se você enumerar a SortedDictionary por seus valores, os valores são retornados na ordem de classificação das chaves, não a ordem de classificação dos valores como você poderia esperar.

Demonstração:

Note-se que nesta demonstração os itens adicionados ao SortedDictionary são não adicionado na ordem de classificação.

Além disso, se você pretende enumerar seu dicionário por seus valores e há uma possibilidade de valores duplicados , considere ter sua função de pesquisa inversa retornar um IEnumerable . (Claro que, para grandes dicionários, olhando para cima uma chave pelo seu valor pode resultar em mau desempenho.)

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

saída esperada:

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