Quelle est la façon la 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.

Je fais maintenant:

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

Est-ce le moyen le plus efficace? Ou cela peut-il être fait simplement en copiant un morceau de mémoire? Merci!

Answer 1

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

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

Je vais garder l'ancien suggestion ici:

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

Il y a quelques raisons de le faire de la façon dont, bien qu'aucun d'entre eux assez forte:

• il n'y a pas de garantie sur ce que la taille du vecteur d'être réaffecté -- par exemple, si la somme de la taille est 1025, il peut être réaffecté à 2048 -- personne à charge sur la mise en œuvre. Il n'y a aucune garantie pour l' reserve , pour une mise en œuvre spécifique, il pourrait être vrai. Si la chasse pour un goulot d'étranglement, il pourrait être rasonable pour vérifier.
• réserve de nos intentions claires -- optimisation peut être plus efficace dans ce cas (les réserves de préparer le cache dans certains des top-notch de mise en œuvre).
• aussi, avec reserve nous avons un C++ Standard garantie qu'il n'y aura qu'un seul réaffectation, tout en insert pourrait être mis en œuvre de façon inefficace et faire plusieurs réaffectations (aussi quelque chose de tester avec une mise en oeuvre 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 le mentionne, à moins que les itérateurs ne soient des itérateurs d'entrée, le vecteur déterminera la taille requise et copiera les données ajoutées en une seule fois avec une complexité linéaire.

Answer 3

J'ai simplement fait une mesure rapide des performances 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 signalées ci-dessous.

Code de test:

 #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, x64, mode Release, / O2 / LTCG, la sortie est la suivante:

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

Answer 4

S'il vous arrive d'utiliser Boost vous pouvez télécharger la version de développement de la RangeEx de la bibliothèque de la poussée de la Voûte. Cette lib. a été acceptée dans l'Boost il y a un moment mais jusqu'à présent il n'a pas été intégré à la distribution principale. En lui, vous trouverez une nouvelle gamme basée sur un algorithme, 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 lisible.

Answer 5

Si vous avez un vecteur de pod-types et que vous avez vraiment besoin de performances, vous pouvez utiliser memcpy, qui devrait être plus rapide que vector <>. 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 l'utilise que si les performances sont vraiment, vraiment nécessaires, le code est sans danger pour les types de pod.