C++ najszybszy sposób wyczyszczenia lub usunięcia wektora

Question

Mam kod, w którym rutynowo wypełniam wektor od 0 do 5000 elementów. Wiem, że nigdy nie przekracza maksymalnej 5000. Zamiast inicjowania wektor wiele razy, chciałbym to zrobić tylko raz

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

Jednak, aby ponownie napełnić wektor, muszę najpierw wyczyścić wektor bez zmiany jego pojemności. Zwykle nazywam się myvector.clear();

To jest operacja O (n). Czy jest coś prostego, co mogę zrobić, aby zwiększyć wydajność tego produktu lub czy jest on najlepszy z możliwych?

Answer 1

Jeśli twój struct ma nietrywialny destruktor, to musi on zostać wywołany dla wszystkich elementów wektora, bez względu na sposób jego opróżnienia. Jeśli twoja struktura ma tylko trywialny destruktor, kompilator lub standardowa implementacja biblioteki może zoptymalizować proces destrukcji i dać operację O (1).

Answer 2

Wszystko, co robisz, aby usunąć istniejące elementy z wektora, musi (potencjalnie) wywołać destruktor każdego zniszczonego elementu. Dlatego z punktu widzenia kontenera najlepsze, na co możesz liczyć, to złożoność liniowa.

Pozostaje tylko pytanie, jakie elementy przechowujesz w wektorze. Jeśli przechowujesz coś takiego jak int, które kompilator może/będzie wiedzieć z wyprzedzeniem, nie ma destruktora do wywołania, szanse są co najmniej całkiem dobre, że usunięcie zakończy się ciągłą złożonością.

Wątpię jednak, aby zmiana składni (np. clear() vs. resize() vs. erase(begin(), end())) spowoduje jakąkolwiek istotną różnicę. Składnia nie zmienia tego faktu, że (w przypadku braku wątkowania) wywołanie N destruktorów jest operacją O (N).

Answer 3

Koszt clear() zależy w dużej mierze od tego, jakie przechowywane są obiekty, aw szczególności od tego, czy mają one trywialny destruktor. Jeśli typ nie ma trywialnego destruktora, to wywołanie musi zniszczyć wszystkie przechowywane obiekty i jest to faktycznie operacja O (n), ale tak naprawdę nie można zrobić nic lepszego.

Teraz, jeśli przechowywane elementy mają trywialne destruktory, wówczas implementacja może zoptymalizować koszt, a clear() staje się tanią operacją O (1) (wystarczy zresetować rozmiar - wskaźnik end).

Pamiętaj, że aby zrozumieć asymptotyczną złożoność, musisz wiedzieć, o czym mówi. W przypadku clear() reprezentuje liczbę wywoływanych destruktorów, ale jeśli koszt (ukryty) wynosi 0, operacja to operacja "no-op".