连接两个std :: vector - 哪种方法更高效，以及如何/为什么？

考虑以下情形：连接两个std :: vector - 哪种方法更高效，以及如何/为什么？

std::vector<int> A; 
std::vector<int> B; 
std::vector<int> AB;

我想AB拥有的A内容，然后B以相同的顺序内容。

方法1：

AB.reserve(A.size() + B.size()); // preallocate memory 
AB.insert(AB.end(), A.begin(), A.end()); 
AB.insert(AB.end(), B.begin(), B.end());

方法2：

std::vector<int> AB (A.begin(), A.end()); // calling constructor 
AB.insert (AB.end(), B.begin(), B.end());

哪个的上述方法之一是更有效率？为什么？有没有更高效的不同方法？

来源

2014-10-09 CinCout

您是否尝试过测量它？ – 2014-10-09 09:22:17

这很大程度上取决于这两个向量的大小以及向量分配器算法的实现 – EdChum 2014-10-09 09:22:22

不确定您是否检查过，但请记住，性能是您一旦确定它是_problem的唯一问题。除非你的矢量是巨大的，或者它们中的项目构造/复制成本高昂，你不会注意到很大的区别。不要花大量的时间将0.2ms的操作减少到0.1ms，除非你需要每秒处理数千次:-) – paxdiablo 2014-10-09 09:25:21

我认为第一个会比第二个快，因为它只执行一次内存分配，第二个可能不得不重新分配至少一次。但my measurements似乎表明，对于尺寸小于约100,000，这是更快：

我猜这是因为，这不仅只执行一次分配和再分配没有，它甚至不需要检查它是否应该做任何重新分配。缺点是它可能必须初始化所有的内存，但我认为CPU是擅长的。

来源

2014-10-09 12:22:24

*缺点是它必须将所有内存清零* - 我看着生成的程序集，我无法解释这么大的差异，但是什么是显而易见的是优化器将内存清零。第一个和你的风格基本生成的代码是相同的，但代码的结构略有不同，它看起来像优化器更好地准备处理这最后一个选项... – 2014-10-10 22:42:03

@DavidRodríguez-dribeas有趣。这并不是我第一次感到惊讶，与“保留内存和插入”方法相比，“内存覆盖和覆盖”方法有多好。 E.g'std :: vector A（size）; for（size_t i = 0; i！= size; ++ i）A [i] = func（i）;'[出人意料地表现出色]（http://coliru.stacked-crooked.com/a/deef69909146f580）。也许你是对的，原因是优化器将内存清零。 – 2014-10-11 06:28:43

第一个可能更高效一点，因为您可以保证只执行一次内存分配。在第二种情况下，很可能（大多数实现方式）在向量构建期间将分配A.size()，然后insert将触发第二次分配，因为它需要增长B.size()个元素。

来源

2014-10-09 09:23:27

方法1执行否重新分配，而方法2可能重新分配多次，并且实际上很可能重新分配一次。所以方法1更好。

来源

2014-10-09 09:24:59

正在插入的迭代器范围使用RandomAccessIterators，因此插入的元素数量可以计算在O（1）中，因此在方法2中不能再重新分配一次。 – 2014-10-09 09:26:21

@JonathanWakely：实际上是保证，还是只是一个共同的实现？（我知道范围构造函数有一个实际的保证。） – 2014-10-09 09:28:25

@KerrekSB：即使标准不能保证它会被认为是一个bug，但它是其中的一个。 – 2014-10-09 09:30:22

连接两个std :: vector - 哪种方法更高效，以及如何/为什么？

回答

相关问题