Ich habe gelesen, dass die Komplexität des Hinzufügens von Elementen zum Ende eines std::vector amortisiert ist und das Einfügen von Elementen am oberen und unteren Rand von std::deque konstant ist. Beide Container haben einen wahlfreien Zugriffs-Iterator, der auf Elemente zugreift bei jedem Index ist konstant. Bitte lassen Sie mich wissen, wenn einer dieser Fakten falsch ist. Meine Frage ist, ob der Zugriff auf ein Element in std::vector oder std::deque konstant ist, warum ist dann die zeitliche Komplexität der Entfernung eines Elements durch Löschen von O (n). Eine der Antworten hier gibt hier an, dass Elemente entfernt werden via löschen ist O (n). Ich weiß, dass Löschen die Elemente zwischen den Start-Iteratoren und der Endung entfernt, so bedeutet die Antwort im Wesentlichen, dass seine O(n) abhängig von der Anzahl der Elemente zwischen den beiden Iteratoren und das Entfernen eines einzelnen Elements aus einem Vektor / Deque in einem Index wird Null sein?
Die Dinge sind ein bisschen anders für std::vector und std::deque , ebenso wie sie für C ++ 98 und C ++ 11 anders sind.
Die Komplexität von std::vector::erase() ist sowohl linear zur Länge des gelöschten Bereichs als auch zur Anzahl der Elemente zwischen dem Ende des Bereichs und dem Ende des Containers (das Löschen eines Elements vom Ende dauert also konstant).
C ++ 2003 [lib.vector.modifiers] liest:
...
Komplexität: Der Destruktor von
Theißt die Anzahl der Male, die der Anzahl der gelöschten Elemente entspricht. aber der Zuweisungsoperator vonTheißt die Anzahl der Male, die der Anzahl der Elemente im Vektor nach den gelöschten Elementen entspricht.
C ++ 14 Entwurf N4140 [vector.modifiers] lautet:
Komplexität: Der Destruktor von
Theißt die Anzahl der Male, die der Anzahl der Elemente entspricht gelöscht, aber der Zuweisungsoperator move vonTwird die Anzahl der Male genannt, die der Anzahl von entspricht Elemente im Vektor nach den gelöschten Elementen.
Sie sehen also, dass die C ++ 11/14-Implementierung im Allgemeinen effizienter ist, da sie die Zuweisungszuweisung anstelle der Kopierzuweisung durchführt, aber die Komplexität bleibt gleich.
Die Komplexität von std::deque::erase() ist sowohl linear zur Länge des gelöschten Bereichs als auch zum Minimum zweier Zahlen: Anzahl der verbleibenden Elemente vor Beginn des Bereichs und Anzahl der verbleibenden Elemente nach dem Ende des Bereichs. Das Löschen eines Elements entweder vom Anfang oder vom Ende dauert konstant.
C ++ 2003 [lib.deque.modifiers] :
Komplexität: Die Anzahl der Aufrufe an den Destruktor ist gleich der Anzahl der gelöschten Elemente, aber der Anzahl der Aufrufe an den Zuweisungsoperator ist maximal gleich dem Minimum der Anzahl der Elemente vor den gelöschten Elementen und der Anzahl der Elemente nach den gelöschten Elementen.
C ++ 14 Entwurf N4140 [deque.modifiers]/5 :
Komplexität: Die Anzahl der Aufrufe an den Destruktor ist identisch mit der Anzahl der gelöschten Elemente, aber die Anzahl der Aufrufe an den Zuweisungsoperator ist nicht mehr als der Wert kleiner der Anzahl der Elemente vor den gelöschten Elementen und der Anzahl der Elemente nach den gelöschten Elementen.
Also, es ist das gleiche in C ++ 98 und C ++ 11/14, außer dass C ++ 11 zwischen der Zuweisung von Zuweisungen und der Zuweisung von Kopien wählen kann (hier sehe ich einige Unstimmigkeiten im Standard, weil die Formulierung nicht Die Erwähnung der Bewegungszuweisung wie für std::vector - könnte ein Grund für eine andere Frage sein.)
Beachten Sie auch die "höchstens" und "nicht mehr" in den Formulierungen. Dies ermöglicht es, dass Implementierungen effizienter als linear sind, obwohl sie in der Praxis linear sind ( DEMO ).
>Das Löschen eines Elements in einem Vektor ist O (n), da Sie nach dem Entfernen des Elements immer noch alle nachfolgenden Elemente verschieben müssen, um die entstandene Lücke zu füllen. Wenn ein Vektor n Elemente hat, müssen Sie im schlimmsten Fall n-1 Elemente verschieben, daher ist die Komplexität O (n).
Das Entfernen von Elementen ist in der Tat O(n) , nicht wegen dem, was Sie tun müssen, um das zu entfernende Element zu finden, sondern wegen dem, was Sie für alle nach tun müssen. Diese Elemente müssen nach unten geschoben werden, um den leeren Steckplatz zu füllen.
Im Durchschnitt wird beim Löschen also ein Element etwa auf halbem Weg durch den Vektor verwendet, sodass Sie etwa die Hälfte der Elemente verschieben müssen. Daher O(n) . Im besten Fall löscht man das letzte Element - kein Gleiten notwendig. Im schlimmsten Fall löscht man das erste Element - muss dann jedes andere Element verschieben.