Wygląda na to, że nie ma ogólnej implementacji OrderedDictionary
(która znajduje się w System.Collections.Specialized
przestrzeni nazw) w .NET 3.5. Czy jest taki, którego mi brakuje?
Znalazłem implementacje zapewniające tę funkcjonalność, ale zastanawiałem się, czy / dlaczego nie ma standardowej implementacji od razu po wyjęciu z pudełka i czy ktoś wie, czy jest to coś w .NET 4.0?
OrderedDictionary<T>
: codeproject.com/Articles/18615/…Systems.Collections.Generic
. PoprośmyOrderedDictionary<TKey,TValue>
o .NET 5. Jak inni zauważyli, przypadek, w którym klucz jest int jest zdegenerowany i będzie wymagał szczególnej uwagi.Odpowiedzi:
Masz rację. W
OrderedDictionary
samym frameworku nie ma ogólnego odpowiednika .(O ile mi wiadomo, tak jest również w przypadku .NET 4).
Ale możesz na to głosować w witrynie UserVoice programu Visual Studio (04.10.2016)!
źródło
Wdrożenie generycznego
OrderedDictionary
nie jest strasznie trudne, ale jest niepotrzebnie czasochłonne i szczerze mówiąc, ta klasa jest ogromnym niedopatrzeniem ze strony Microsoftu. Jest na to wiele sposobów, ale zdecydowałem się użyć jakoKeyedCollection
pamięci wewnętrznej. Zdecydowałem się również zaimplementować różne metody sortowania,List<T>
ponieważ jest to zasadniczo hybryda IList i IDictionary. Umieściłem tutaj moją implementację dla potomności.Oto interfejs. Zauważ, że zawiera
System.Collections.Specialized.IOrderedDictionary
, która jest nieogólną wersją tego interfejsu dostarczoną przez firmę Microsoft.Oto implementacja wraz z klasami pomocniczymi:
Żadna implementacja nie byłaby kompletna bez kilku testów (ale tragicznie, SO nie pozwoli mi opublikować tak dużo kodu w jednym poście), więc będę musiał zostawić Ci napisanie testów. Ale zostawiłem kilka z nich, abyś mógł zorientować się, jak to działa:
-- AKTUALIZACJA --
Źródło dla tej i innych naprawdę przydatnych brakujących podstawowych bibliotek .NET tutaj: https://github.com/mattmc3/dotmore/blob/master/dotmore/Collections/Generic/OrderedDictionary.cs
źródło
TKey
takint
? Jakthis[]
będzie działać w takim przypadku?Dla rekordu istnieje ogólny KeyedCollection, który umożliwia indeksowanie obiektów za pomocą int i klucza. Klucz musi być osadzony w wartości.
źródło
Oto dziwne znalezisko: przestrzeń nazw System.Web.Util w pliku System.Web.Extensions.dll zawiera ogólny OrderedDictionary
Nie jestem pewien, dlaczego MS umieściło go tam zamiast pakietu System.Collections.Generic, ale zakładam, że możesz po prostu skopiować, wkleić kod i użyć go (jest wewnętrzny, więc nie można go używać bezpośrednio). Wygląda na to, że implementacja korzysta ze standardowego słownika i oddzielnych list kluczy / wartości. Całkiem proste ...
źródło
System.Runtime.Collections
zawiera również wewnętrzną,OrderedDictionary<TKey, TValue>
która po prostu otacza nieogólną wersjęSystem.Web.Util.OrderedDictionary<TKey, TValue>
jest wewnętrznie zaimplementowany wokół generycznegoDictionary
. Dziwne to nie realizuje,IList
aleICollection<KeyValuePair<TKey, TValue>>
List<KeyValuePair<TKey,TValue>>
będzie konkurencyjne ze względu na wzorzec dostępu do pamięci, dla większych rozmiarów po prostu użyj tej samej listy +Dictionary<TKey,int>
jako wyszukiwania. AFAIK nie ma takiej struktury danych, która radziłaby sobie lepiej pod względem szybkości / pamięci w BigO.System.Collections.Specialized.OrderedDictionary
nie jest typem ogólnym. Spójrz, bez nawiasów kątowych na stronie z dokumentem, z którą łączysz się: PWarto, oto jak to rozwiązałem:
Można go zainicjować w następujący sposób:
i dostępne w ten sposób:
źródło
Add
metod.pairList.Add(new KeyValuePair<K,V>())
(tj. Metoda naList
klasie). W takim przypadkuitsIndex
słownik nie jest aktualizowany, a lista i słownik nie są zsynchronizowane. Może ukryćList.Add
metodę, tworzącnew
PairList.Add(KeyValuePair<K,V>)
metodę, lub może użyć kompozycji zamiast dziedziczenia i po prostu ponownie zaimplementować wszystkieList
metody ... dużo więcej kodu ...if (itsindex.Contains(key)) return;
na początku,Add
aby zapobiec duplikatomGłównym problemem koncepcyjnym związanym z ogólną wersją programu
OrderedDictionary
jest to, że użytkownicyOrderedDictionary<TKey,TValue>
oczekiwaliby, że będą mogli indeksować go numerycznie przy użyciuint
lub wyszukując przy użyciu rozszerzeniaTKey
. Gdy jedynym typem klucza byłObject
, tak jak to było w przypadku nieogólnegoOrderedDictionary
, typ argumentu przekazywany do indeksatora byłby wystarczający do rozróżnienia, czy należy wykonać operację indeksowania. W obecnej sytuacji nie jest jednak jasne, jakOrderedDictionary<int, TValue>
powinien zachowywać się indeksator .Gdyby klasy takie jak
Drawing.Point
zalecały i stosowały się do reguły, zgodnie z którą struktury podlegające zmianom fragmentarycznym powinny uwidaczniać swoje zmienne elementy jako pola, a nie właściwości, i powstrzymywać się od używania metod ustawiających właściwości, które modyfikująthis
, wówczasOrderedDictionary<TKey,TValue>
mógłby efektywnie ujawnićByIndex
właściwość, któraIndexer
zwraca strukturę, która zawiera odniesienie do słownik i miał indeksowaną właściwość, której metody pobierające i ustawiające będą wywoływaćGetByIndex
iSetByIndex
na niej. Można by więc powiedzieć coś w rodzajuMyDict.ByIndex[5] += 3;
dodania 3 do szóstego elementu słownika.Niestety, aby kompilator zaakceptował coś takiego, należałoby sprawić, by
ByIndex
właściwość zwracała nową instancję klasy, a nie strukturę za każdym razem, gdy jest wywoływana, eliminując korzyści, które można by uzyskać unikając pudełkowania.W VB.NET można obejść ten problem, używając nazwanej, indeksowanej właściwości (więc
MyDict.ByIndex[int]
należałoby do niejMyDict
, a nie wymagałobyMyDict.ByIndex
bycia członkiem,MyDict
który zawiera indeksator), ale C # nie zezwala na takie rzeczy.Mimo wszystko warto było oferować
OrderedDictionary<TKey,TValue> where TKey:class
, ale głównym powodem wprowadzenia leków generycznych w pierwszej kolejności było umożliwienie ich używania z typami wartości.źródło
int
Słuszna uwaga, że klucze typu -ty stanowią wyzwanie, ale można by tego uniknąć, postępując zgodnie z przykładem pokrewnegoSortedList<TKey, TValue>
typu: obsługuj klucze tylko z[...]
i wymagają użycia w.Values[...]
celu uzyskania dostępu przez indeks. (SortedDictionary<TKey, TValue>
dla kontrastu, który nie jest zoptymalizowany pod kątem dostępu indeksowanego, wymaga użycia.ElementAt(...).Value
)Z wielu powodów odkryłem, że można sobie poradzić z plikiem
List<KeyValuePair<K, V>>
. (Dictionary
Oczywiście nie, jeśli potrzebujesz go rozszerzyć , a nie, jeśli potrzebujesz lepszego niż O (n) wyszukiwania klucza i wartości).źródło
Tuple<T1, T2>
jeśli nie mają relacji klucz-wartość.Jest
SortedDictionary<TKey, TValue>
. Chociaż semantycznie blisko, nie twierdzę, że to to samo, coOrderedDictionary
po prostu dlatego, że tak nie jest. Nawet z cech wydajności. Jednak bardzo interesująca i dość istotna różnica pomiędzyDictionary<TKey, TValue>
(iw tym zakresieOrderedDictionary
implementacjami podanymi w odpowiedziach) aSortedDictionary
polega na tym, że ta ostatnia używa pod spodem drzewa binarnego. Jest to krytyczne rozróżnienie, ponieważ czyni klasę odporną na ograniczenia pamięciowe stosowane do klasy ogólnej. Zobacz ten wątek na tematOutOfMemoryExceptions
zgłaszanych, gdy klasa ogólna jest używana do obsługi dużego zestawu par klucz-wartość.Jak obliczyć maksymalną wartość parametru pojemności przekazanego do konstruktora Dictionary, aby uniknąć wyjątku OutOfMemoryException?
źródło
SortedDictionary
w kolejności, w jakiej zostały dodane ? To właśnieOrderedDictionary
pozwala. Koncepcja inna niż posortowana . (Zrobiłem ten błąd w przeszłości, myślałem, dostarczając porównywarka do OrderedDictionary konstruktora pozwoliłoby sortowane, ale wszystko robi z porównywarka jest ustalenie klucza równości, np string-niewrażliwy comparer pozwala string-niewrażliwe wyszukiwanie kluczy.)Racja, to niefortunne pominięcie. Brakuje mi OrderedDict w Pythonie
Więc napisałem własną
OrderedDictionary<K,V>
klasę w C #. Jak to działa? Utrzymuje dwie kolekcje - nieuporządkowany słownik waniliowy i uporządkowaną listę kluczy. Dzięki temu rozwiązaniu standardowe operacje słownikowe zachowują szybką złożoność, a wyszukiwanie według indeksu jest również szybkie.https://gist.github.com/hickford/5137384
Oto interfejs
źródło
W następstwie komentarza @VB jest dostępna implementacja metody System.Runtime.Collections.OrderedDictionary <,> . Pierwotnie zamierzałem uzyskać do niego dostęp przez odbicie i udostępnić go przez fabrykę, ale plik dll, w którym się znajduje, nie wydaje się być w ogóle dostępny, więc po prostu pobrałem samo źródło.
Należy zwrócić uwagę na to, że indeksator tutaj nie zgłosi
KeyNotFoundException
. Absolutnie nienawidzę tej konwencji i to była pierwsza wolność, jaką przyjąłem w tej implementacji. Jeśli jest to dla Ciebie ważne, po prostu zamień wiersz nareturn default(TValue);
. Używa C # 6 ( zgodne z Visual Studio 2013 )Żądania pull / dyskusja akceptowane w GitHub
źródło
Dla tych, którzy szukają opcji pakietu „oficjalnego” w NuGet, implementacja generycznego OrderedDictionary została zaakceptowana w .NET CoreFX Lab. Jeśli wszystko pójdzie dobrze, typ zostanie ostatecznie zatwierdzony i zintegrowany z głównym repozytorium .NET CoreFX.
Istnieje możliwość, że ta implementacja zostanie odrzucona.
Do zatwierdzonej implementacji można się odwołać tutaj https://github.com/dotnet/corefxlab/blob/57be99a176421992e29009701a99a370983329a6/src/Microsoft.Experimental.Collections/Microsoft/Collections/Extensions/OrderedDictionary.cs
Pakiet NuGet, który definitywnie ma ten typ dostępny do użycia, można znaleźć tutaj https://www.nuget.org/packages/Microsoft.Experimental.Collections/1.0.6-e190117-3
Możesz też zainstalować pakiet w programie Visual Studio. Wyszukaj pakiet „Microsoft.Experimental.Collections” i upewnij się, że pole wyboru „Uwzględnij wersję wstępną” jest zaznaczone.
Zaktualizuje ten post, jeśli i kiedy typ zostanie oficjalnie udostępniony.
źródło
Zaimplementowałem rodzaj ogólny
OrderedDictionary<TKey, TValue>
, zawijającSortedList<TKey, TValue>
i dodając prywatny plikDictionary<TKey, int>
_order
. Następnie stworzyłem wewnętrzną implementacjęComparer<TKey>
, przekazując referencję do słownika _order. Następnie używam tej funkcji porównującej do wewnętrznej SortedList. Ta klasa zachowuje kolejność elementów przekazanych do konstruktora i kolejność dodawania.Ta implementacja ma prawie taką samą charakterystykę dużego O, jak
SortedList<TKey, TValue>
ponieważ dodawanie i usuwanie do _order jest O (1). Każdy element zajmie (zgodnie z książką „C # 4 w pigułce”, s. 292, tabela 7-1) dodatkową przestrzeń pamięci 22 (narzut) + 4 (w kolejności) + TKey size (przyjmijmy 8) = 34 Razem zSortedList<TKey, TValue>
narzutem 2 bajtów, całkowity narzut wynosi 36 bajtów, podczas gdy ta sama książka mówi, że nieogólneOrderedDictionary
ma narzut 59 bajtów.Jeśli przejdę
sorted=true
do konstruktora, to _order w ogóle nie jest używany,OrderedDictionary<TKey, TValue>
jest dokładnieSortedList<TKey, TValue>
z niewielkim narzutem na zawijanie, jeśli w ogóle ma sens.Mam zamiar przechowywać w formacie nie tak wiele dużych obiektów referencyjnych
OrderedDictionary<TKey, TValue>
, więc dla mnie to ok. 36 bajtów narzutu jest do przyjęcia.Główny kod znajduje się poniżej. Kompletny kod jest aktualizowany na tym GIST .
źródło
OrderedDictionary
wstawienia lub usunięcia: (1) Nigdy nie będzie żadnych usunięć; (2) nastąpi usunięcie, ale ważne jest, aby pozycje były wymienione w kolejności dodawania; nie ma potrzeby dostępu według indeksu; (3) numeryczny indeks pozycji powinien (lub przynajmniej może) pozostać stały, a nie więcej niż 2 miliardy pozycji zostanie dodanych w okresie istnienia kolekcji, więc jeśli pozycja # 7 zostanie usunięta, nigdy więcej nie będzie przedmiot nr 7; (4) indeks elementu powinien być jego rangą w odniesieniu do ocalałych.Dictionary
. Scenariusze # 2 i # 3 można by obsłużyć, utrzymując indeks każdego elementu, informujący o tym, kiedy został dodany i łącza do elementów dodanych przed lub po nim. Scenariusz # 4 jest jedynym, który wydaje się, że nie powinien być w stanie osiągnąć wydajności O (1) dla operacji w dowolnej kolejności. W zależności od wzorców użycia, # 4 może być pomocny przy użyciu różnych strategii leniwej aktualizacji (utrzymywanie liczników w drzewie i wprowadzanie zmian w węźle do unieważniania zamiast aktualizowania węzła i jego rodziców).