Каков наиболее эффективный способ добавить один std :: vector в конец другого?

Question

Пусть v1 будет целевым вектором, v2 необходимо добавить к его обратной стороне.

Я сейчас делаю:

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

Это самый эффективный способ? Или это может быть сделано только путем копирования части памяти? Спасибо!

Answer 1

После долгих споров (и разумного комментария от Матье М. и villintehaspam) я изменю свое предложение на

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

Я сохраню прежнее предложение здесь:

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

Есть несколько причин сделать это последним способом, хотя ни одна из них не достаточно сильна:

• нет гарантии того, на какой размер будет перераспределен вектор - например, если размер суммы равен 1025, он может быть перераспределен на 2048 - в зависимости от реализации. Для reserve такой гарантии также нет, но для конкретной реализации это может быть правдой. Если вы охотитесь за узким местом, возможно, стоит проверить это.
• Резерв заявляет, что наши намерения ясны - оптимизация может быть более эффективной в этом случае (резерв может подготовить кэш в некоторых первоклассных реализациях).
• также, с reserve у нас есть стандарт C ++ Standard, гарантирующий, что будет только одно перераспределение, в то время как insert может быть реализован неэффективно и делать несколько перераспределений (также что-то для тестирования с конкретной реализацией).

Answer 2

Вероятно, лучше и проще использовать выделенный метод: vector.insert

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

Как Майкл упоминает, если итераторы не являются входными итераторами, вектор будет вычислять необходимый размер и копировать добавленные данные за один раз с линейной сложностью.

Answer 3

Я просто сделал быстрое измерение производительности с помощью следующего кода и

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

представляется правильным выбором (как уже было сказано выше). Тем не менее, вы найдете отчет о производительности ниже.

Тестовый код:

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

}

В Visual Studio 2008 SP1, x64, режим выпуска, / O2 / LTCG вывод выглядит следующим образом:

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

Если вы используете Boost, вы можете загрузить версию для разработки библиотеки RangeEx из Boost Vault . Это библиотека был принят в Boost некоторое время назад, но до сих пор не интегрирован с основным дистрибутивом. В нем вы найдете новый алгоритм на основе диапазона, который делает именно то, что вы хотите:

boost::push_back(v1, v2);

Внутренне это работает как ответ, данный UncleBens, но код более краткий и читаемый.

Answer 5

Если у вас есть вектор типов pod, и вам действительно нужна производительность, вы можете использовать memcpy, который должен быть быстрее, чем vector <>. Insert (...):

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

Обновление: Хотя я бы использовал это, только если производительность действительно нужна, действительно , код является безопасным для типов стручков.