Domanda Qual è il modo più efficace per aggiungere uno std :: vector alla fine di un altro?


Sia v1 il vettore di destinazione, v2 deve essere aggiunto al retro di esso.

Ora sto facendo:

v1.reserve(v1.size() + v2.size()); 
copy(v2.begin(), v2.end(), back_inserter(v1));

È questo il modo più efficace? O può forse essere fatto semplicemente copiando un pezzo di memoria? Grazie!


44
2018-02-05 15:35


origine


risposte:


Dopo molte discussioni (e un commento ragionevole da Matthieu M. e villintehaspam), cambierò il mio suggerimento a

v1.insert( v1.end(), v2.begin(), v2.end() );

Terrò il precedente suggerimento qui:

v1.reserve( v1.size() + v2.size() ); 
v1.insert( v1.end(), v2.begin(), v2.end() );

Ci sono alcuni motivi per farlo in questo modo, anche se nessuno di loro è abbastanza forte:

  • non vi è alcuna garanzia su quale dimensione verrà riallocato il vettore - ad es. se la dimensione della somma è 1025, può essere riallocata a 2048, a seconda dell'implementazione. Non esiste una tale garanzia per reserve entrambi, ma per una specifica implementazione potrebbe essere vero. Se si cerca un collo di bottiglia, potrebbe essere possibile verificarlo.
  • riserva dichiara chiaramente le nostre intenzioni: l'ottimizzazione potrebbe essere più efficiente in questo caso (la riserva potrebbe preparare la cache in un'implementazione di prim'ordine).
  • inoltre, con reserve abbiamo una garanzia standard di C ++ che ci sarà solo una singola riallocazione, mentre insert potrebbe essere implementato in modo inefficiente e fare diverse riallocazioni (anche qualcosa da testare con una particolare implementazione).

56
2018-02-05 15:39



Probabilmente è meglio e più semplice usare un metodo dedicato: vector.insert

v1.insert(v1.end(), v2.begin(), v2.end());

Come menziona Michael, a meno che gli iteratori non siano degli iteratori di input, il vettore calcolerà la dimensione richiesta e copierà i dati aggiunti con una complessità lineare.


22
2018-02-05 15:40



Ho semplicemente fatto una misurazione rapida delle prestazioni con il seguente codice e

v1.insert( v1.end(), v2.begin(), v2.end() );

sembra essere la scelta giusta (come già detto sopra). Tuttavia, si trova la performance riportata di seguito.

Codice di prova:

#include <vector>
#include <string>

#include <boost/timer/timer.hpp>

//==============================================================================
// 
//==============================================================================

/// Returns a vector containing the sequence [ 0, ... , n-1 ].
inline std::vector<int> _range(const int n)
{
    std::vector<int> tmp(n);
    for(int i=0; i<n; i++)
        tmp[i] = i;
    return tmp;
}

void test_perf_vector_append()
{
    const vector<int> testdata1 = _range(100000000);
    const vector<int> testdata2 = _range(100000000);

    vector<int> testdata;

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  push_back()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;
        for(size_t i=0; i<testdata2.size(); i++)
        {
            testdata.push_back(testdata2[i]);
        }
    }

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  reserve() + push_back()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;
        testdata.reserve(testdata.size() + testdata2.size());
        for(size_t i=0; i<testdata2.size(); i++)
        {
            testdata.push_back(testdata2[i]);
        }
    }

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  insert()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;

        testdata.insert( testdata.end(), testdata2.begin(), testdata2.end() );
    }

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  reserve() + insert()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;

        testdata.reserve( testdata.size() + testdata.size() ); 
        testdata.insert( testdata.end(), testdata2.begin(), testdata2.end() );
    }

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  copy() + back_inserter()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;

        testdata.reserve(testdata.size() + testdata2.size()); 
        copy(testdata2.begin(), testdata2.end(), back_inserter(testdata));
    }

    printf("--------------------------------------------------------------\n");
    printf(" METHOD:  reserve() + copy() + back_inserter()\n");
    printf("--------------------------------------------------------------\n");
    testdata.clear();
    { vector<int>().swap(testdata); }
    testdata = testdata1;
    {
        boost::timer::auto_cpu_timer t;

        testdata.reserve(testdata.size() + testdata2.size()); 
        copy(testdata2.begin(), testdata2.end(), back_inserter(testdata));
    }

}

Con Visual Studio 2008 SP1, x64, Modalità di rilascio, / O2 / LTCG l'output è il seguente:

--------------------------------------------------------------
 METHOD:  push_back()
--------------------------------------------------------------
 0.933077s wall, 0.577204s user + 0.343202s system = 0.920406s CPU (98.6%)

--------------------------------------------------------------
 METHOD:  reserve() + push_back()
--------------------------------------------------------------
 0.612753s wall, 0.452403s user + 0.171601s system = 0.624004s CPU (101.8%)

--------------------------------------------------------------
 METHOD:  insert()
--------------------------------------------------------------
 0.424065s wall, 0.280802s user + 0.140401s system = 0.421203s CPU (99.3%)

--------------------------------------------------------------
 METHOD:  reserve() + insert()
--------------------------------------------------------------
 0.637081s wall, 0.421203s user + 0.218401s system = 0.639604s CPU (100.4%)

--------------------------------------------------------------
 METHOD:  copy() + back_inserter()
--------------------------------------------------------------
 0.743658s wall, 0.639604s user + 0.109201s system = 0.748805s CPU (100.7%)

--------------------------------------------------------------
 METHOD:  reserve() + copy() + back_inserter()
--------------------------------------------------------------
 0.748560s wall, 0.624004s user + 0.124801s system = 0.748805s CPU (100.0%)

17
2017-07-27 10:08



Se ti capita di utilizzare Boost, puoi scaricare la versione di sviluppo della libreria RangeEx dal Boost Vault. Questa lib. è stato accettato in Boost qualche tempo fa ma finora non è stato integrato con la distribuzione principale. In esso troverai un nuovo algoritmo basato sulla gamma che fa esattamente quello che vuoi:

boost::push_back(v1, v2);

Internamente funziona come la risposta data da UncleBens, ma il codice è più conciso e leggibile.


7
2018-02-05 16:50



Se hai un vettore di tipi di pod e hai davvero bisogno delle prestazioni, potresti usare memcpy, che dovrebbe essere più veloce del vettore <>. Insert (...):

v2.resize(v1.size() + v2.size());
memcpy((void*)&v1.front(), (void*)&v2[v1.size()], sizeof(v1.front())*v1.size());

Aggiornare: Anche se lo userei solo se la performance è davvero, veramente, necessario, il codice è sicuro per i tipi di cialde.


4
2018-02-05 15:44