Kolejność elementów w słowniku

107

Moje pytanie dotyczy wyliczenia elementów Słownika

// Dictionary definition
private Dictionary<string, string> _Dictionary = new Dictionary<string, string>();

// add values using add

_Dictionary.Add("orange", "1");
_Dictionary.Add("apple", "4");
_Dictionary.Add("cucumber", "6");

// add values using []

_Dictionary["banana"] = 7;
_Dictionary["pineapple"] = 7;

// Now lets see how elements are returned by IEnumerator
foreach (KeyValuePair<string, string> kvp in _Dictionary)
{
  Trace.Write(String.Format("{0}={1}", kvp.Key, kvp.Value));
}

W jakiej kolejności zostaną wyliczone elementy? Czy mogę wymusić alfabetyczny porządek?

Kapitan Komiks
źródło

Odpowiedzi:

125

Kolejność elementów w słowniku jest niedeterministyczna. Pojęcie porządku po prostu nie jest zdefiniowane dla tabel skrótów. Nie polegaj więc na wyliczaniu w tej samej kolejności, w jakiej elementy zostały dodane do słownika. To nie jest gwarantowane.

Cytat z dokumentu :

Na potrzeby wyliczenia każdy element w słowniku jest traktowany jako KeyValuePair<TKey, TValue>struktura reprezentująca wartość i jej klucz. Kolejność, w jakiej zwracane są produkty, jest nieokreślona.

Darin Dimitrov
źródło
1
Ale jest OrderedDictionary .
Peter Mortensen
28

Jeśli chcesz uporządkować elementy, użyj OrderedDictionary . Zwykły hastable / słownik jest uporządkowany tylko w pewnym sensie układu pamięci.

Mitch Wheat
źródło
10
OrderedDictionary jest w większości przypadków błędny. Nie jest uporządkowany według klucza lub wartości, ale według wewnętrznego indeksu. SortedDictionary jest tym, który jest uporządkowany w sposób, w jaki użytkownik może manipulować (klucz domyślny)
Offler
3
Pytanie dotyczy kolejności alfabetycznej (zakładając, że pytający mówi o kluczu). Uporządkowany słownik, jeśli dobrze zrozumiem dokumentację, wypluje elementy w kolejności ich wstawiania, tj. Nie alfabetycznie, ale z wykorzystaniem wewnętrznego indeksu. SortedDictionary jest prawdopodobnie najlepiej dopasowany do pytania użytkownika.
Mattpm
28

Zawsze możesz SortedDictionarydo tego użyć . Zauważ, że słownik jest domyślnie uporządkowany według klucza, chyba że określono element porównujący.

Jestem sceptyczny co OrderedDictionarydo tego, czego chcesz, ponieważ dokumentacja mówi, że:

Elementy OrderedDictionary nie są sortowane według klucza, w przeciwieństwie do elementów klasy SortedDictionary.

Adriano Carneiro
źródło
Należy zauważyć, że SortedDictionary<K,V>jest zaimplementowane jako drzewo wyszukiwania binarnego, co daje jego operacjom różną złożoność czasową i przestrzenną w porównaniu z bazującym na tablicy haszy Dictionary<K,V>. Jeśli użytkownicy potrzebują struktury O(1)wstawiającej / usuwającej hashy, a także chcą iterować po elementach w kolejności kluczy, powinni dict.Keys.OrderBy( k => k ).Select( k => dict[k] )zamiast tego (kosztem O(n)miejsca i O( n log n )czasu) dla OrderBy()(który będzie musiał buforować całą kolekcję kluczy na liście wewnętrznej ).
Dai
12

Elementy zostaną zwrócone w kolejności, w jakiej znajdują się fizycznie w słowniku, która zależy od kodu skrótu i ​​kolejności dodawania elementów. Tak więc kolejność będzie wydawać się losowa, a gdy implementacje się zmieniają, nigdy nie powinieneś polegać na tym, że kolejność pozostanie taka sama.

Możesz zamówić pozycje wyliczając je:

foreach (KeyValuePair<string, string> kvp in _Dictionary.OrderBy(k => k.Value)) {
  ...
}

We frameworku 2.0 musiałbyś najpierw umieścić elementy na liście, aby je posortować:

List<KeyValuePair<string, string>> items = new List<KeyValuePair<string, string>>(_Dictionary);
items.Sort(delegate(KeyValuePair<string, string> x, KeyValuePair<string, string> y) { return x.Value.CompareTo(y.Value); });
foreach (KeyValuePair<string,string> kvp in items) {
  ...
}
Guffa
źródło
11

Dla OrderedDictionary:

 var _OrderedDictionary = new System.Collections.Specialized.OrderedDictionary();

_OrderedDictionary.Add("testKey1", "testValue1");
_OrderedDictionary.Add("testKey2", "testValue2");
_OrderedDictionary.Add("testKey3", "testValue3");

var k = _OrderedDictionary.Keys.GetEnumerator();
var v = _OrderedDictionary.Values.GetEnumerator();

while (k.MoveNext() && v.MoveNext()) {
    var key = k.Current; var value = v.Current;
}

Elementy są zwracane w kolejności ich dodania.

Siedziba
źródło
5

Tablice asocjacyjne (czyli tablice skrótów) są nieuporządkowane, co oznacza, że ​​elementy można uporządkować w dowolny możliwy sposób.

JEDNAK możesz pobrać klucze tablic (tylko klucze), uporządkować je alfabetycznie (za pomocą funkcji sortowania), a następnie nad tym pracować.

Nie mogę dać Ci próbki C #, ponieważ nie znam języka, ale to powinno wystarczyć, abyś mógł kontynuować.

Tim Čas
źródło