Quel est le moyen le plus efficace d'ajouter un std :: vector à la fin d'un autre?

Question

Soit v1 le vecteur cible, v2 doit être ajouté à l'arrière de celui-ci.

que je fais maintenant:

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

Est-ce la façon la plus efficace? Ou peut-on le faire simplement en copiant un morceau de mémoire? Merci!

Answer 1

Après beaucoup de disputes (et un commentaire raisonnable de Matthieu M. et villintehaspam), je vais changer ma suggestion

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

Je garderai l'ancienne suggestion:

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

il y a quelques raisons de le faire cette dernière façon, même si aucun d'entre eux assez forts:

• il n'y a aucune garantie sur à quelle taille le vecteur sera-t-il réaffecté - par ex. Si la taille de la somme est 1025, elle peut être réaffectée à 2048, en fonction de l'implémentation. Il n'y a pas de telle garantie pour reserve non plus, mais pour une implémentation spécifique, cela peut être vrai. Si vous cherchez un goulot d'étranglement, il peut être raisonnable de vérifier cela. Réserve nos intentions claires - l'optimisation peut être plus efficace dans ce cas (réserver pourrait préparer le cache dans une implémentation de premier ordre).
• également, avec reserve nous avons une garantie C++ Standard qu'il n'y aura qu'une seule réallocation, tandis que insert pourrait être implémentée de manière inefficace et faire plusieurs réallocations (aussi quelque chose à tester avec une implémentation particulière).

Answer 2

probablement mieux et plus simple d'utiliser une méthode dédiée: vector.insert

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

Comme Michael mentionne, à moins que les itérateurs sont itérateurs entrée, le vecteur figurerez la taille requise et copier des données jointes en une seule fois avec une complexité linéaire.

Answer 3

Si vous avez un vecteur de pod-types, et vous avez vraiment besoin de la performance, vous pouvez utiliser memcpy, qui devrait être plus rapide que vecteur <> .insert (...):

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

Mise à jour: Bien que je ne voudrais utiliser que si la performance est vraiment, vraiment, nécessaire, le code est sans danger pour les types de pod.

Answer 4

Si vous utilisez Boost, vous pouvez télécharger la version de développement de la bibliothèque RangeEx from the Boost Vault. Cette lib. a été accepté dans Boost il y a quelque temps mais jusqu'à présent, il n'a pas été intégré à la distribution principale. Dans ce document, vous trouverez un nouvel algorithme basé gamme qui fait exactement ce que vous voulez:

boost::push_back(v1, v2); 

En interne, il fonctionne comme la réponse donnée par Unclebens, mais le code est plus concis et facile à lire.

Answer 5

je tout simplement pas une mesure de performance rapide avec le code suivant et

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

semble être le bon choix (comme déjà indiqué ci-dessus). Néanmoins, vous trouverez les performances rapportées ci-dessous.

Code d'essai:

#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)); 
    } 

} 

Avec Visual Studio 2008 SP1, 64 bits, le mode de sortie,/O2/LTCG la sortie se présente comme suit:

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