In .NET 3.5 scheint es keine generische Implementierung von OrderedDictionary
(im System.Collections.Specialized
Namespace) zu geben. Gibt es eine, die ich vermisse?
Ich habe Implementierungen gefunden, um die Funktionalität bereitzustellen, habe mich aber gefragt, ob / warum es keine sofort einsatzbereite generische Implementierung gibt und ob jemand weiß, ob es sich um etwas in .NET 4.0 handelt.
OrderedDictionary<T>
: codeproject.com/Articles/18615/…Systems.Collections.Generic
. Fordern wirOrderedDictionary<TKey,TValue>
.NET 5 an. Wie andere bereits betont haben, ist der Fall, dass der Schlüssel ein Int ist, entartet und erfordert besondere Sorgfalt.Antworten:
Du hast recht. Es gibt kein generisches Äquivalent
OrderedDictionary
im Framework selbst.(Soweit mir bekannt ist, gilt dies auch für .NET 4.)
Sie können jedoch bei UserVoice von Visual Studio (04.10.2016) dafür stimmen!
quelle
Die Implementierung eines Generikums
OrderedDictionary
ist nicht besonders schwierig, aber unnötig zeitaufwändig, und ehrlich gesagt ist diese Klasse ein großes Versehen von Microsoft. Es gibt mehrere Möglichkeiten, dies zu implementieren, aber ich habe mich für die Verwendung einesKeyedCollection
für meinen internen Speicher entschieden. Ich habe mich auch dafür entschieden, verschiedene Methoden zum Sortieren zu implementieren,List<T>
da dies im Wesentlichen eine hybride IList und ein IDictionary ist. Ich habe meine Implementierung hier für die Nachwelt aufgenommen.Hier ist die Schnittstelle. Beachten Sie
System.Collections.Specialized.IOrderedDictionary
, dass dies die nicht generische Version dieser Schnittstelle ist, die von Microsoft bereitgestellt wurde.Hier ist die Implementierung zusammen mit Hilfsklassen:
Und keine Implementierung wäre ohne ein paar Tests vollständig (aber tragischerweise lässt mich SO nicht so viel Code in einem Beitrag veröffentlichen), also muss ich Sie verlassen, um Ihre Tests zu schreiben. Aber ich habe ein paar davon gelassen, damit Sie eine Vorstellung davon bekommen, wie es funktioniert:
- UPDATE -
Quelle für diese und andere wirklich nützliche fehlende .NET-Kernbibliotheken hier: https://github.com/mattmc3/dotmore/blob/master/dotmore/Collections/Generic/OrderedDictionary.cs
quelle
TKey
istint
? Wiethis[]
wird in einem solchen Fall funktionieren?Für den Datensatz gibt es eine generische KeyedCollection , mit der Objekte durch ein int und einen Schlüssel indiziert werden können. Der Schlüssel muss in den Wert eingebettet sein.
quelle
Hier ist ein bizarrer Fund: Der System.Web.Util-Namespace in System.Web.Extensions.dll enthält ein generisches OrderedDictionary
Ich bin mir nicht sicher, warum MS es dort anstelle des System.Collections.Generic-Pakets abgelegt hat, aber ich gehe davon aus, dass Sie den Code einfach kopieren, einfügen und verwenden können (er ist intern, kann ihn also nicht direkt verwenden). Die Implementierung verwendet anscheinend ein Standardwörterbuch und separate Schlüssel- / Wertelisten. Ziemlich einfach...
quelle
System.Runtime.Collections
enthält auch eine interne,OrderedDictionary<TKey, TValue>
die nur die nicht generische VersionSystem.Web.Util.OrderedDictionary<TKey, TValue>
wird intern um generisch implementiertDictionary
. Merkwürdig ist es nicht umzusetzen ,IList
sondernICollection<KeyValuePair<TKey, TValue>>
List<KeyValuePair<TKey,TValue>>
aufgrund des Speicherzugriffsmusters wettbewerbsfähig. Bei größeren Größen verwenden Sie einfach dieselbe Liste +Dictionary<TKey,int>
als Suche. AFAIK Es gibt keine solche Datenstruktur, die in BigO hinsichtlich Geschwindigkeit / Speicher besser abschneidet.System.Collections.Specialized.OrderedDictionary
ist kein generischer Typ. Schauen Sie ma, keine spitzen Klammern auf der von Ihnen verlinktenFür das, was es wert ist, habe ich es folgendermaßen gelöst:
Es kann folgendermaßen initialisiert werden:
und wie folgt zugegriffen:
quelle
Add
Methoden sind.pairList.Add(new KeyValuePair<K,V>())
(dh der Methode für dieList
Klasse). In diesem Fall wird dasitsIndex
Wörterbuch nicht aktualisiert, und jetzt sind die Liste und das Wörterbuch nicht mehr synchron. Könnte dieList.Add
Methode durch Erstellen einernew
PairList.Add(KeyValuePair<K,V>)
Methode ausblenden oder könnte Komposition anstelle von Vererbung verwenden und einfach alleList
Methoden erneut implementieren ... viel mehr Code ...if (itsindex.Contains(key)) return;
am AnfangAdd
, um Duplikate zu verhindernEin großes konzeptionelles Problem bei einer generischen Version von
OrderedDictionary
ist, dass Benutzer von aOrderedDictionary<TKey,TValue>
erwarten, dass sie es entweder numerisch mit aint
oder durch Nachschlagen mit a indizieren könnenTKey
. Wenn der einzige Schlüsseltyp warObject
, wie dies bei nicht generischen Schlüsseln der Fall warOrderedDictionary
, würde der an den Indexer übergebene Argumenttyp ausreichen, um zu unterscheiden, ob welche Art von Indexierungsoperation ausgeführt werden soll. Es ist jedoch unklar, wie sich der Indexer einesOrderedDictionary<int, TValue>
verhalten soll.Wenn wie Klassen
Drawing.Point
empfohlen hatte , und folgte eine Regel , dass stückweise-veränderbare Strukturen ihre veränderbare Elemente wie Felder aussetzen sollte , anstatt Eigenschaften und verzichten auf Eigenschaft Setter , die ändernthis
, dann einOrderedDictionary<TKey,TValue>
könnte effizient eine aussetzenByIndex
Eigenschaft , die ein zurückIndexer
Struktur , die eine Referenz gehalten das Wörterbuch und hatte eine indizierte Eigenschaft, deren Getter und SetterGetByIndex
undSetByIndex
auf sie aufrufen würden . Man könnte also so etwas wieMyDict.ByIndex[5] += 3;
3 zum sechsten Element des Wörterbuchs hinzufügen.Damit der Compiler so etwas akzeptieren kann, muss die
ByIndex
Eigenschaft leider jedes Mal, wenn sie aufgerufen wird, eine neue Klasseninstanz anstelle einer Struktur zurückgeben, wodurch die Vorteile beseitigt werden, die sich aus der Vermeidung des Boxens ergeben.In VB.NET könnte man dieses Problem umgehen, indem man eine benannte indizierte Eigenschaft verwendet (
MyDict.ByIndex[int]
wäre also ein Mitglied vonMyDict
, anstattMyDict.ByIndex
ein Mitglied zu sein,MyDict
das einen Indexer enthält), aber C # erlaubt solche Dinge nicht.Es mag sich immer noch gelohnt haben, ein Produkt anzubieten
OrderedDictionary<TKey,TValue> where TKey:class
, aber der Hauptgrund für die Bereitstellung von Generika bestand darin, ihre Verwendung mit Werttypen zuzulassen.quelle
int
Schlüssel vomSortedList<TKey, TValue>
Typ "Typ" eine Herausforderung darstellen. Sie können jedoch vermieden werden, indem Sie dem Beispiel des zugehörigen Typs folgen : Schlüssel nur mit[...]
unterstützen und.Values[...]
für den Zugriff per Index verwenden. (ImSortedDictionary<TKey, TValue>
Gegensatz dazu erfordert die Verwendung, die nicht für den indizierten Zugriff optimiert ist, die Verwendung von.ElementAt(...).Value
)Für viele Zwecke habe ich festgestellt, dass man mit einem auskommen kann
List<KeyValuePair<K, V>>
. (Natürlich nicht, wenn Sie es benötigen, um es zu erweiternDictionary
, und nicht, wenn Sie eine bessere Suche nach O (n) -Schlüsselwerten benötigen.)quelle
Tuple<T1, T2>
wenn sie keine Schlüssel-Wert-Beziehung haben.Es gibt
SortedDictionary<TKey, TValue>
. Obwohl semantisch nahe, behaupte ich nicht, dass es dasselbe ist wieOrderedDictionary
einfach, weil sie es nicht sind. Auch von Leistungsmerkmalen. Der sehr interessante und sehr wichtige Unterschied zwischenDictionary<TKey, TValue>
(und insoweitOrderedDictionary
und den in den Antworten angegebenen Implementierungen)SortedDictionary
besteht jedoch darin, dass letzterer einen darunter liegenden Binärbaum verwendet. Dies ist eine kritische Unterscheidung, da die Klasse dadurch immun gegen Speicherbeschränkungen ist, die auf generische Klassen angewendet werden. In diesem Thread wird beschrieben, wieOutOfMemoryExceptions
ausgelöst wird, wenn eine generische Klasse für die Verarbeitung einer großen Anzahl von Schlüssel-Wert-Paaren verwendet wird.Wie kann der maximale Wert für den Kapazitätsparameter ermittelt werden, der an den Dictionary-Konstruktor übergeben wird, um OutOfMemoryException zu vermeiden?
quelle
SortedDictionary
in der Reihenfolge abzurufen, in der sie hinzugefügt wurden ? DasOrderedDictionary
erlaubt es. Anderes Konzept als sortiert . (Ich habe diesen Fehler in der Vergangenheit gemacht, ich dachte einen Comparer OrderedDictionary Konstruktor liefern würde es sortiert, aber alle mit dem Comparer tut , ist Gleichheit der Schlüssel zu bestimmen, zB String unempfindlichen Vergleich ermöglicht String unempfindlichen Schlüsselsuche.)Richtig, es ist eine unglückliche Unterlassung. Ich vermisse Pythons OrderedDict
Also habe ich meine eigene
OrderedDictionary<K,V>
Klasse in C # geschrieben. Wie funktioniert es? Es werden zwei Sammlungen verwaltet - ein ungeordnetes Vanille-Wörterbuch und eine geordnete Liste von Schlüsseln. Mit dieser Lösung behalten die Standardwörterbuchoperationen ihre schnelle Komplexität bei, und das Nachschlagen nach Index ist ebenfalls schnell.https://gist.github.com/hickford/5137384
Hier ist die Schnittstelle
quelle
Im Anschluss an den Kommentar von @VB finden Sie hier eine barrierefreie Implementierung des System.Runtime.Collections.OrderedDictionary <,> . Ich wollte ursprünglich durch Reflektion darauf zugreifen und es über eine Factory bereitstellen, aber die DLL, in der sich diese befindet, scheint überhaupt nicht sehr zugänglich zu sein, also habe ich einfach die Quelle selbst gezogen.
Eine Sache zu beachten ist, dass der Indexer hier nicht wirft
KeyNotFoundException
. Ich hasse diese Konvention absolut und das war die Freiheit, die ich mir bei dieser Implementierung genommen habe. Wenn Ihnen das wichtig ist, ersetzen Sie einfach die Leitung fürreturn default(TValue);
. Verwendet C # 6 ( kompatibel mit Visual Studio 2013 )Pull-Anfragen / Diskussion auf GitHub akzeptiert
quelle
Für diejenigen, die nach einer "offiziellen" Paketoption in NuGet suchen, wurde eine Implementierung eines generischen OrderedDictionary in .NET CoreFX Lab akzeptiert. Wenn alles gut geht, wird der Typ schließlich genehmigt und in das Haupt-Repo von .NET CoreFX integriert.
Es besteht die Möglichkeit, dass diese Implementierung abgelehnt wird.
Auf die festgeschriebene Implementierung kann hier verwiesen werden: https://github.com/dotnet/corefxlab/blob/57be99a176421992e29009701a99a370983329a6/src/Microsoft.Experimental.Collections/Microsoft/Collections/Extensions/OrderedDictionary
Das NuGet-Paket, für das dieser Typ definitiv verfügbar ist, finden Sie hier https://www.nuget.org/packages/Microsoft.Experimental.Collections/1.0.6-e190117-3
Oder Sie können das Paket in Visual Studio installieren. Suchen Sie nach dem Paket "Microsoft.Experimental.Collections" und stellen Sie sicher, dass das Kontrollkästchen "Prerelease einschließen" aktiviert ist.
Aktualisiert diesen Beitrag, wenn der Typ offiziell verfügbar gemacht wird.
quelle
Ich habe ein Generikum implementiert,
OrderedDictionary<TKey, TValue>
indem ich es umwickeltSortedList<TKey, TValue>
und ein privates hinzugefügt habeDictionary<TKey, int>
_order
. Dann habe ich eine interne Implementierung von erstelltComparer<TKey>
und einen Verweis auf das _order-Wörterbuch übergeben. Dann benutze ich diesen Komparator für die interne SortedList. Diese Klasse behält die Reihenfolge der an den Konstruktor übergebenen Elemente und die Reihenfolge der Ergänzungen bei.Diese Implementierung hat fast die gleichen großen O-Eigenschaften wie das
SortedList<TKey, TValue>
Hinzufügen und Entfernen von _order zu O (1). Jedes Element benötigt (gemäß dem Buch 'C # 4 in a Nutshell', S. 292, Tabelle 7-1) zusätzlichen Speicherplatz von 22 (Overhead) + 4 (int order) + TKey size (nehmen wir 8 an) = 34 Zusammen mitSortedList<TKey, TValue>
dem Overhead von zwei Bytes beträgt der Gesamt-Overhead 36 Bytes, während das gleiche Buch besagt, dass nicht generischeOrderedDictionary
einen Overhead von 59 Bytes haben.Wenn ich an
sorted=true
den Konstruktor übergebe, wird _order überhaupt nicht verwendet, dasOrderedDictionary<TKey, TValue>
ist genauSortedList<TKey, TValue>
mit geringem Aufwand für das Umbrechen, wenn überhaupt sinnvoll.Ich werde nicht so viele große Referenzobjekte in der aufbewahren
OrderedDictionary<TKey, TValue>
. 36 Bytes Overhead sind tolerierbar.Der Hauptcode ist unten. Der vollständige aktualisierte Code befindet sich in diesem Kern .
quelle
OrderedDictionary
Einfügungen oder Löschungen sehen kann: (1) Es wird niemals Löschungen geben; (2) es wird Löschungen geben, aber wichtig ist, dass die Elemente in der hinzugefügten Reihenfolge aufgelistet werden; Der Zugriff per Index ist nicht erforderlich. (3) Der numerische Index eines Artikels sollte (oder kann zumindest konstant bleiben), und während der Lebensdauer der Sammlung werden nicht mehr als 2 Milliarden Artikel hinzugefügt. Wenn also Artikel 7 entfernt wird, wird es nie wieder einen geben Artikel # 7; (4) Der Index eines Gegenstands sollte sein Rang in Bezug auf Überlebende sein.Dictionary
. Die Szenarien Nr. 2 und Nr. 3 können behandelt werden, indem jedes Element einen Index verwaltet, der angibt, wann es hinzugefügt wurde, und Links zu Elementen enthält, die davor oder danach hinzugefügt wurden. Szenario 4 ist das einzige, das anscheinend nicht in der Lage sein sollte, eine O (1) -Leistung für Operationen in beliebiger Reihenfolge zu erzielen. Abhängig von den Verwendungsmustern kann # 4 durch die Verwendung verschiedener verzögerter Aktualisierungsstrategien unterstützt werden (Anzahl in einem Baum beibehalten und Änderungen an einem Knoten ungültig machen, anstatt den Knoten und seine Eltern zu aktualisieren).