C++ 将一个 std::vector 附加到另一个末尾的最有效方法是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2208293/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the most efficient way to append one std::vector to the end of another?
提问by Alex Jenter
Let v1 be the target vector, v2 needs to be appended to the back of it.
设 v1 为目标向量，v2 需要附加到它的后面。
I'm now doing:
我现在在做：
v1.reserve(v1.size() + v2.size());
copy(v2.begin(), v2.end(), back_inserter(v1));
Is this the most efficient way? Or can it maybe be done just via copying a chunk of memory? Thanks!
这是最有效的方法吗？或者它可以通过复制一块内存来完成吗？谢谢！
回答by Kornel Kisielewicz
After a lot of arguing (and a reasonable comment from Matthieu M. and villintehaspam), I'll change my suggestion to
经过多次争论（以及来自 Matthieu M. 和 villintehaspam 的合理评论），我将我的建议改为
v1.insert( v1.end(), v2.begin(), v2.end() );
I'll keep the former suggestion here:
我会在这里保留以前的建议：
v1.reserve( v1.size() + v2.size() );
v1.insert( v1.end(), v2.begin(), v2.end() );
There are some reasons to do it the latter way, although none of them enough strong:
有一些原因可以采用后一种方式，尽管它们都不够强大：
- there is no guarantee on to what size will the vector be reallocated -- e.g. if the sum size is 1025, it may get reallocated to 2048 -- dependant on implementation. There is no such guarantee for
reserveeither, but for a specific implementation it might be true. If hunting for a bottleneck it might be rasonable to check that. - reserve states our intentions clear -- optimization may be more efficient in this case (reserve could prepare the cache in some top-notch implementation).
- also, with
reservewe have a C++ Standard guarantee that there will be only a single reallocation, whileinsertmight be implemented inefficiently and do several reallocations (also something to test with a particular implementation).
- 无法保证重新分配向量的大小——例如，如果总和大小为 1025，它可能会重新分配到 2048——取决于实现。
reserve两者都没有这样的保证，但对于特定的实现，它可能是正确的。如果寻找瓶颈，检查它可能是合理的。 - Reserve 明确表达了我们的意图——在这种情况下优化可能更有效（reserve 可以在一些一流的实现中准备缓存）。
- 此外，
reserve我们有一个 C++ 标准保证只会有一次重新分配，而insert可能实现效率低下并进行多次重新分配（也需要使用特定实现进行测试）。
回答by UncleBens
Probably better and simpler to use a dedicated method: vector.insert
使用专用方法可能更好更简单：vector.insert
v1.insert(v1.end(), v2.begin(), v2.end());
As Michael mentions, unless the iterators are input iterators, the vector will figure out the required size and copy appended data at one go with linear complexity.
正如迈克尔提到的，除非迭代器是输入迭代器，否则向量将计算出所需的大小并以线性复杂度一次性复制附加数据。
回答by Stefan
I simply did a quick performance measurement with the following code and
我只是使用以下代码进行了快速性能测量
v1.insert( v1.end(), v2.begin(), v2.end() );
seems to be the right choice (as already stated above). Nevertheless, you find the reported performance below.
似乎是正确的选择（如上所述）。不过，您可以在下面找到报告的性能。
Test code:
测试代码：
#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));
}
}
With Visual Studio 2008 SP1, x64, Release mode, /O2 /LTCG the output is as follows:
使用 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%)
回答by Manuel
If you happen to use Boost you can download the development version of the RangeEx library from the Boost Vault. This lib. was accepted into Boost a while ago but so far it hasn't been integrated with the main distribution. In it you'll find a new range-based algorithm which does exactly what you want:
如果您碰巧使用 Boost，则可以从 Boost Vault下载 RangeEx 库的开发版本。这个库。不久前被 Boost 接受，但到目前为止它还没有与主要发行版集成。在其中你会发现一个新的基于范围的算法，它完全符合你的要求：
boost::push_back(v1, v2);
Internally it works like the answer given by UncleBens, but the code is more concise and readable.
在内部，它的工作原理类似于 UncleBens 给出的答案，但代码更简洁易读。
回答by Viktor Sehr
If you have a vector of pod-types, and you really need the performance, you could use memcpy, which ought to be faster than vector<>.insert(...):
如果你有一个 pod 类型的向量，并且你真的需要性能，你可以使用 memcpy，它应该比 vector<>.insert(...) 更快：
v2.resize(v1.size() + v2.size());
memcpy((void*)&v1.front(), (void*)&v2[v1.size()], sizeof(v1.front())*v1.size());
Update: Although I would only use this if performance is really, really, needed, the code issafe for pod types.
更新：虽然我只会在真的非常需要性能时使用它，但代码对于 pod 类型是安全的。
