C++ schnellste Möglichkeit, einen Vektor zu löschen oder zu löschen

Question

Ich habe einen Code, wo ich routinemäßig einen Vektor mit zwischen 0 und 5000 Elementen fülle. Ich weiß, dass das Maximum überschreitet nie 5000. Stattdessen Vektor mehrere Male von der Initialisierung, ich möchte nur einmal

vector<struct> myvector; 
myvector.reserve(5000); 

jedoch tun, um den Vektor wieder zu füllen, habe ich zuerst den Vektor löschen, ohne seine Fähigkeit zu verändern. Normalerweise rufe ich myvector.clear() auf;

Dies ist eine O (n) -Operation. Gibt es etwas Einfaches, das ich tun kann, um die Leistung zu erhöhen, oder ist es das Beste, was es bekommen wird?

Answer 1

Wenn Ihre Struktur einen nicht-trivialen Destruktor hat, dann muss dieser für alle Elemente des Vektors aufgerufen werden, unabhängig davon, wie er geleert wird. Wenn Ihre Struktur nur einen trivialen Destruktor hat, kann der Compiler oder die Implementierung der Standardbibliothek den Zerstörungsprozess optimieren und Ihnen eine O (1) -Operation geben.

Answer 2

Alles, was Sie tun, um die vorhandenen Elemente aus dem Vektor zu entfernen, muss (möglicherweise) den Destruktor jedes zu zerstörenden Elements aufrufen. Aus Sicht des Containers ist daher die lineare Komplexität das Beste, worauf Sie hoffen können.

Das lässt nur die Frage, welche Art von Elementen Sie in dem Vektor speichern. Wenn Sie etwas wie int speichern, von dem der Compiler im Voraus wissen kann/wird, dass es keinen Destruktor zum Aufrufen gibt, sind die Chancen zumindest ziemlich gut, dass die Entfernung mit konstanter Komplexität endet.

Ich bezweifle jedoch, dass die Änderung der Syntax (z. B. clear() vs. resize() vs. erase(begin(), end())) keinen signifikanten Unterschied machen wird. Die Syntax ändert diese Tatsache nicht, die (in Abwesenheit von Threading) N-Destruktoren aufrufen ist eine O (N) -Operation.

Answer 3

Die Kosten von clear() hängen hauptsächlich davon ab, was die gespeicherten Objekte sind und insbesondere, ob sie einen trivialen Destruktor haben. Wenn der Typ keinen trivialen Destruktor hat, dann muss der Aufruf alle gespeicherten Objekte zerstören und es ist tatsächlich eine Operation O (n), aber Sie können wirklich nichts Besseres tun.

Nun, wenn die gespeicherten Elemente triviale Destruktoren haben, dann kann die Implementierung die Kosten weg optimieren und clear() wird eine billige O (1) Operation (nur die Größe zurücksetzen - end Zeiger).

Denken Sie daran, dass Sie, um asymptotische Komplexität zu verstehen, wissen müssen, worüber es spricht. Im Fall von clear() stellt es die Anzahl der Destruktoren genannt, aber wenn die Kosten (versteckt) 0 ist, dann ist die Operation ein No-Op.