¿Cuál es la forma más eficiente de agregar un std :: vector al final de otro?

Question

Deje que v1 sea el vector de destino, v2 debe agregarse a la parte posterior.

que estoy haciendo ahora:

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

¿Es esta la manera más eficiente? ¿O puede hacerse simplemente copiando un pedazo de memoria? Gracias!

Answer 1

Después de un montón de discutir (y un comentario razonable a partir de Matthieu M. y villintehaspam), voy a cambiar mi sugerencia de

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

Voy a mantener la antigua sugerencia aquí:

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

hay algunas razones para hacerlo esta última manera, aunque ninguno de ellos lo suficientemente fuerte:

• no hay ninguna garantía de a qué tamaño se reasignará el vector, p. si el tamaño de la suma es 1025, puede reasignarse a 2048, dependiendo de la implementación. Tampoco existe dicha garantía para reserve, pero para una implementación específica podría ser cierto. Si busca un cuello de botella, podría ser razonable comprobarlo.
• reserva declara nuestras intenciones claras - la optimización puede ser más eficiente en este caso (reserve podría preparar el caché en alguna implementación de primera categoría).
• también, con reserve tenemos una norma C++ estándar que garantiza que habrá una sola reasignación, mientras que insert podría implementarse de manera ineficiente y realizar varias reasignaciones (también algo para probar con una implementación particular).

Answer 2

Probablemente mejor y más fácil de usar un método específico: vector.insert

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

Como se menciona Michael, a menos que los iteradores son iteradores de entrada, el vector se darán cuenta de las dimensiones requeridas y copiar datos adjuntos en una sola vez con complejidad lineal.

Answer 3

Si usted tiene un vector de vaina-tipos, y que realmente necesita el rendimiento, se puede utilizar establecimiento de memoria, que debe ser más rápido que el vector <> .Insert (...):

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

Actualización: Aunque solo utilizaría esto si el rendimiento es realmente, realmente, necesario, el código es seguro para los tipos de pod.

Answer 4

Si utiliza Boost, puede descargar la versión de desarrollo de la biblioteca RangeEx from the Boost Vault. Esta lib. fue aceptado en Boost hace un tiempo, pero hasta ahora no se ha integrado con la distribución principal. En él se puede encontrar un nuevo algoritmo basado en la gama que hace exactamente lo que quiere:

boost::push_back(v1, v2); 

Internamente funciona como la respuesta dada por UncleBens, pero el código es más concisa y fácil de leer.

Answer 5

simplemente hice una rápida medición de los resultados con el siguiente código y

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

parece ser la elección correcta (como ya se ha indicado anteriormente). Sin embargo, a continuación encontrará el rendimiento informado.

código

prueba:

#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, modo de lanzamiento,/O2/LTCG la salida es la siguiente:

-------------------------------------------------------------- 
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%)