Vantaggi dell’utilizzo di riserva() in un vettore – C++

Qual è il vantaggio di riserva, che quando ha a che fare con i vettori. Quando dovrei farlo? Non riuscivo a trovare una chiara risposta su questo, ma suppongo che sia più veloce di quando si prenota in anticipo prima di utilizzarli.

Quello che dici la gente più intelligente di me?

  • Grazie a tutti per la risposta. Inoltre, l’utilizzo di riserva(20) significa che ci sono più di 20 elementi, o semplicemente che la memoria per 20 elementi, è stato allocato?
  • Solo la memoria è stata allocata. La memoria non inizializzata.
  • reserve() aggiunge capacità, ma non aggiungere elementi. Ciò che viene restituito da size() invariato (tuttavia, capacity() tornerà almeno 20 nel tuo esempio).

 

7 Replies
  1. 27

    È utile se si ha un’idea di come molti elementi del vettore conterrà – può aiutare il vettore di evitare ripetutamente l’allocazione di memoria (e di dover spostare i dati nella memoria).

    In generale, è probabilmente un potenziale di ottimizzazione che non c’è bisogno di preoccuparsi, ma non è nocivo o (nel peggiore dei casi si finisce per sprecare memoria se più di stima).

    Una zona dove può essere più di un’ottimizzazione è quando si desidera garantire che i iteratori non diventano nulli con l’aggiunta di nuovi elementi.

    Per esempio, un push_back() chiamata potrebbe invalidare esistenti iteratori per il vettore (se si verifica una ridistribuzione). Tuttavia, se hai riservato sufficienti elementi è possibile garantire che la riallocazione non si verificherà. Questa è una tecnica che non ha bisogno di essere utilizzato molto spesso, però.

    • …e facendo ripetute allocare/copiare/spostare le sequenze di quando lo spazio attualmente disponibile si esaurisce può portare alla frammentazione dell’heap.
    • “..garantire che i iteratori non diventano nulli con l’aggiunta di nuovi elementi.” questo è vero per il specifiche tipi di aggiunge (il push_back esempio è uno di questi tipo). Ma un insert() invalida tutti gli iteratori dal punto di inserimento, anche con un’ampia capacità disponibile (e, naturalmente, se la capacità richiede una ridimensionare tutto ciò che cade fuori tabella). La versione extreme è, naturalmente, un insert(v.begin(), ...) che invalida iteratori sempre. Per fortuna, ci sono meglio i contenitori di vettoriali per gestire che se è frequente operazione dal codice.
  2. 7

    Può essere … soprattutto se avete intenzione di essere l’aggiunta di un sacco di elementi vettoriali nel corso del tempo, e si vuole evitare automatico di espansione di memoria che il contenitore si fanno quando si esegue fuori di slot disponibili.

    Per esempio, back-inserimenti (cioè, std::vector::push_back) sono considerati un ammortized O(1) o a tempo costante processo, ma che è perché se un’inserzione sul retro di un vettore e il vettore di spazio, deve allocare memoria per un nuovo array di elementi, copiare i vecchi elementi in un array, e quindi è possibile copiare l’elemento che si sta cercando di inserire nel contenitore. Tale processo è O(N) o lineare tempo la complessità, e un grande vettore, potrebbe prendere un po ‘ di tempo. Utilizzando il reserve() metodo consente di pre-allocare memoria per il vettore se sai che sta per essere almeno di una certa dimensione, e di evitare di riallocazione di memoria ogni volta che lo spazio si esaurisce, soprattutto se avete intenzione di fare il back-inserimenti all’interno di alcune prestazioni critiche di codice in cui si desidera assicurarsi che il tempo per fare l’inserimento rimane un effettivo O(1) complessità del processo, e non corrispondere nascosto la riallocazione di memoria per l’array. Concesso, il costruttore di copia dovrebbe essere O(1) la complessità, nonché ottenere true O(1) complessità per l’intero back-processo di inserimento, ma riguardo ai algoritmo per l’inserimento nel vettore con il contenitore stesso, è possibile mantenere in una nota complessità che, se la memoria per le slot è già pre-assegnati.

  3. 3

    Se si conosce la dimensione finale del vettore riserviamo quindi vale la pena di usare.

    Altrimenti ogni volta che il vettore si esaurisce sala interna che si ri-dimensione del buffer. Questo di solito comporta un raddoppio (o 1,5 * dimensione attuale) la dimensione del buffer interno (può essere costoso se si fanno un sacco).

    Reale costoso bit è invocare il costruttore di copia su ogni elemento di copiare dal vecchio buffer per il nuovo buffer, seguita da chiamare il distruttore su ogni elemento nel vecchio buffer.

    Se il costruttore di copia è costoso, allora può essere un problema.

    • Se il costruttore di copia è costoso, utilizzando std::deque può essere un’opzione migliore. gotw.ca/gotw/054.htm
  4. 1

    Più veloce e fa risparmiare memoria

    Se si push_back un altro elemento, poi un vettore in genere allocare il doppio della memoria è attualmente in uso – dal allocare + copia è costoso

  5. 1

    Non conosci le persone più intelligenti di te, ma direi che si dovrebbe chiamare reserve in anticipo se avete intenzione di eseguire un sacco in operazioni di inserimento e sai già o è possibile stimare il numero totale di elementi, di almeno un ordine di grandezza. Si può risparmiare un sacco di riassegnazioni in ottime condizioni.

  6. 1

    Anche se la sua una vecchia questione, Qui è il mio attuazione per le differenze.

    #include <iostream>
    #include <chrono>
    #include <vector>
    
    using namespace std;
    
    int main(){
        vector<int> v1;
        chrono::steady_clock::time_point t1 = chrono::steady_clock::now();
        for(int i = 0; i < 1000000; ++i){
            v1.push_back(1);
        }
        chrono::steady_clock::time_point t2 = chrono::steady_clock::now();
        chrono::duration<double> time_first = chrono::duration_cast<chrono::duration<double>>(t2-t1);
        cout << "Time for 1000000 insertion without reserve: " << time_first.count() * 1000 << " miliseconds." << endl;
    
        vector<int> v2;
        v2.reserve(1000000);
        chrono::steady_clock::time_point t3 = chrono::steady_clock::now();
        for(int i = 0; i < 1000000; ++i){
            v2.push_back(1);
        }
        chrono::steady_clock::time_point t4 = chrono::steady_clock::now();
        chrono::duration<double> time_second = chrono::duration_cast<chrono::duration<double>>(t4-t3);
        cout << "Time for 1000000 insertion with reserve: " << time_second.count() * 1000 << " miliseconds." << endl;
        return 0;
    }

    Quando si compila e si esegue questo programma, uscite:

    Time for 1000000 insertion without reserve: 24.5573 miliseconds.
    
    Time for 1000000 insertion with reserve: 17.1771 miliseconds.

    Sembra essere qualche miglioramento con riserva, ma non troppo di miglioramento. Penso che sarà più miglioramento per oggetti complessi, non sono sicuro. Eventuali suggerimenti, modifiche e i commenti sono i benvenuti.

Lascia un commento