Fügen Sie zu sortedset und seiner Komplexität hinzu

Question

MSDN gibt die folgenden an SortEdSet (t) .Add -Methode :

Wenn die Anzahl geringer ist als die Kapazität des internen Arrays, ist diese Methode eine O (1) -Operation.

Könnte jemand bitte "wie so" erklären? Ich meine, wenn wir einen neuen Wert hinzufügen, müssen wir einen korrekten Ort finden, um einen Wert hinzuzufügen (damit er mit anderen Werten verglichen wird), und die interne Implementierung sieht wie ein "Rotschwarzbaum" mit O (log n) Insertionskomplexität aus.

Answer 1

Der Kommentar ist einfach falsch. Ja, es ist ein rotschwarzer Baum, O (log (n)) für Einsätze. Wenn Sie einen Look mit Reflektor haben, trägt die private addifnotpresent () -Methode eine while () -Schloop, um den Insertionspunkt unter Verwendung eines normalen rot-schwarzen Knoten-Traversals zu finden.

Dieser Doc -Fehler hat bereits wurde eingereicht von dir, weißt-wer.