2010-02-05 2 views
42

Soit v1 le vecteur cible, v2 doit être ajouté à l'arrière de celui-ci.Quel est le moyen le plus efficace d'ajouter un std :: vector à la fin d'un autre?

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!

+0

double possible http://stackoverflow.com/questions/201718/how-to-concat-two-stl-vectors – Serge

+0

Les réponses sont correctes pour cette question, mais pas pour cette question (!) – MSalters

Répondre

55

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).
+6

La réserve est très probablement inutile, puisque cela sera probablement fait automatiquement par la fonction d'insertion. – villintehaspam

+0

Il n'y a aucune garantie que la réserve allouera exactement la quantité de stockage demandée. La seule garantie est que capacity() sera> = à ce que vous demandez. – villintehaspam

+8

@villintehaspam - theres aussi ** non ** garantie dans la norme que l'insertion ne fera pas plusieurs réaffectations au lieu d'un. Il y a ** une garantie sur réserve cependant: 'Il est garanti qu'aucune réallocation ne se produit lors des insertions qui se produisent après un appel à reserve() jusqu'au moment où une insertion rendrait la taille du vecteur supérieure à la taille spécifié dans le dernier appel à la réserve(). 'Par conséquent, la réserve est plus sûre. –

21

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.

+5

Tant que les itérateurs sont avancés, accès bidirectionnel, ou aléatoire, la taille finale du vecteur sera déterminée à l'avance et réservée. Il n'est donc pas nécessaire d'effectuer une réserve() avant. Si les itérateurs sont des itérateurs d'entrée, cela ne peut pas être fait, et le vecteur devra peut-être être réalloué plusieurs fois en fonction du nombre d'éléments qui seront ajoutés. –

+0

@ Michael, voir ma réponse pour le motif de la réserve. –

+2

@Kornel Kisielewicz: C'est incorrect, la réserve peut également allouer plus de mémoire que nécessaire. – villintehaspam

4

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.

+0

Bien que je ne suis pas sûr à 100% parce que redimensionner fait beaucoup d'appels contructor unnessesary. –

+0

@dirkgently: c'est pourquoi j'ai utilisé le redimensionnement et non la réservation. –

+0

Oui, c'est très rapide, mais il utilise des détails d'implémentation. – Notinlist

7

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.

15

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

Merveilleuse réponse! –