Hat C# .NET eine Datenstruktur, die die folgenden Eigenschaften erfüllt?

Question

Ich versuche, ein Problem zu lösen, und ich erkannte, dass die Komplexität meiner Lösung höher als erwartet war aufgrund der Tatsache, dass Insert für List<T> ist O (n) (Quelle: https://msdn.microsoft.com/en-us/library/sey5k5z4(v=vs.110).aspx).

Was ich will, ist eine Datenstruktur wie

• Sequential Behälter
• Hat binäre Suchverfahren, das funktioniert, wenn Elemente, um
• Besser als O (n) Insertion an einem Index sind
• O (1) Anzahl der Elemente in dem Behälter erhalten
• O (1) durch den Index lookup

Mit anderen Worten, ich möchte etwas wie List<T> außer schnelleres Einfügen.

Answer 1

Ist es möglich, dass Duplikate in der Liste angezeigt werden, oder können Sie garantieren, dass Sie den gleichen Wert nicht zweimal sehen? Müssen Sie den Index angeben, oder erwarten Sie, dass die Dinge basierend auf dem Wert des Elements sortiert werden?

Wenn Sie wissen, dass es keine Duplikate geben wird oder Sie den Wert nicht zweimal speichern möchten, wenn Dubletten vorhanden sind und Ihr Index vollständig darauf basiert, das Element basierend auf seinem Wert in die richtige Position zu bringen könnte den SortedSet<T> Typ betrachten.

Wenn möglicherweise Duplikate vorhanden sind, Sie den Wert jedoch manuell angeben möchten, können Sie unter SortedDictionary<TKey, TValue> nachsehen, wobei die Werte TKey Ihre ganzzahligen Indizes sind.

Wenn Sie keine dieser Bedingungen erfüllen können, müssen Sie Ihren eigenen Typ implementieren. Die gute Nachricht ist, dass Sie nicht bei Null anfangen müssen. Der Typ LinkedList<T> kann den größten Teil des Weges dorthin zurücklegen.

Answer 2

Es ist nicht genau eingebaut, aber Sie können es versuchen. Wintellect Power Collections hat BigList<T>, die den Job erledigen wird.

https://powercollections.codeplex.com/

Es hat schnellere Insertion an bestimmten Index im Vergleich zu List<T>. Ich kann Ihnen nicht genau sagen, wie es funktioniert, aber es behält einige Abweichungen bei den Elementen bei, so dass es im Hinblick auf das Gedächtnis eher epxensiv ist.

Sie können es auch als Nugget-Paket finden.

** EDIT: ** Es hat O (log n) indizierten Zugriff als @Ryan hat mich korrigiert.