将一个std :: vector追加到另一个std :: vector的最有效方法是什么？

设v1为目标vector，v2需要追加到它的后面。

我现在在做：

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

这是最有效的方法吗？ 或者可以通过复制一块内存来完成？ 谢谢！

Answer 1

经过很多争论（还有Matthieu M.和villintehaspam的合理评论），我会把我的build议改为

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

我会在这里保留以前的build议：

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

后一种做法有一些原因，尽pipe它们都不够强大：

• 无法保证向量被重新分配的大小 – 例如，如果总和大小为1025，则可能重新分配到2048 – 取决于实现。 reserve也没有这样的保证，但是对于具体的实施可能是真实的。 如果寻找一个瓶颈，那么检查这个可能是不合理的。
• 保留状态我们的意图明确 – 在这种情况下，优化可能会更有效率（保留可以准备在一些顶级实施高速caching）。
• 另外，我们reserve一个C ++标准，保证只有一次重新分配，而insert可能被低效地实现，并且执行一些重新分配（也可以用特定的实现来testing）。

Answer 2

使用专用的方法可能会更好，更简单： vector.insert

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

正如Michael所提到的，除非迭代器是input迭代器，否则向量将计算出所需的大小并一次性复制附加数据，具有线性复杂度。

Answer 3

我只是用下面的代码做了一个快速的性能测量

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

似乎是正确的select（如上所述）。 不过，您可以在下面find所报告的performance。

testing代码：

 #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，您可以从Boost Vault下载RangeEx库的开发版本。 这个lib。 前段时间被Boost接受，但到目前为止还没有与主要发行版本整合。 在这里你会发现一个新的基于范围的algorithm，它正是你想要的：

 boost::push_back(v1, v2); 

它在内部就像UncleBens给出的答案一样工作，但代码更简洁可读。

Answer 5

如果你有一个podtypes的向量，并且你确实需要这个性能的话，你可以使用memcpy，它应该比vector <> insert。（…）：

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

更新：虽然我只会使用这个，如果性能是真的， 真的需要，代码对于podtypes是安全的。