C++, il modo più veloce per cancellare o cancellare un vettore

Question

Ho un codice in cui di solito riempio un vettore con da 0 a 5000 elementi. So che la massima non supera mai i 5000. Invece di inizializzazione vettore più volte, vorrei fare solo una volta

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

Tuttavia, per riempire di nuovo il vettore, devo cancellare il vettore prima senza alterarne la portata. Quindi di solito chiamo myvector.clear();

Questa è un'operazione O (n). C'è qualcosa di semplice che posso fare per aumentare le prestazioni di questo o è il migliore che otterrà?

Answer 1

Se la propria struct ha un distruttore non banale, è necessario chiamare tutti gli elementi del vettore indipendentemente da come viene svuotato. Se la tua struct ha solo un distruttore banale, il compilatore o l'implementazione della libreria standard può ottimizzare il processo di distruzione e darti un'operazione O (1).

Answer 2

Qualsiasi cosa tu faccia per rimuovere gli elementi esistenti dal vettore deve (potenzialmente) richiamare il distruttore di ogni oggetto che viene distrutto. Pertanto, dal punto di vista del contenitore, il meglio che si possa sperare è la complessità lineare.

Questo lascia solo la domanda su che tipo di elementi memorizzi nel vettore. Se si memorizza qualcosa come int che il compilatore può sapere prima del tempo non ha alcun distruttore da invocare, è probabile che la rimozione finisca con una complessità costante.

Dubito, tuttavia, che la modifica della sintassi (ad es. clear() vs. resize() vs. erase(begin(), end())) comporterà alcuna differenza significativa. La sintassi non modifica il fatto che (in assenza di threading) l'invocazione di N destructors è un'operazione O (N).

Answer 3

Il costo di clear() dipende in gran parte da cosa sono gli oggetti memorizzati e, in particolare, se hanno un distruttore banale. Se il tipo non ha un distruttore banale, la chiamata deve distruggere tutti gli oggetti memorizzati ed è in realtà un'operazione O (n), ma non si può fare nulla di meglio.

Ora, se gli elementi memorizzati hanno distruttori banali, l'implementazione può ottimizzare il costo e clear() diventa un'operazione O (1) economica (basta reimpostare la dimensione - puntatore end).

Ricordare che per comprendere la complessità asintotica è necessario sapere di cosa parla. Nel caso di clear() rappresenta il numero di distruttori chiamati, ma se il costo (nascosto) è 0, allora l'operazione è un no-op.