连接两个std::vector -- 哪种方法更有效率，如何实现/为什么？

Question

请考虑以下情景：

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

我将会翻译以下内容，涉及IT技术。请注意，我会尽力使文本更通俗易懂，但不会添加解释或删除HTML标签。以下是需要翻译的内容：

我希望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() );

以上方法中哪一个更有效？为什么？ 是否有其他更有效的方法？

- CinCout

---

你有尝试过测量它吗？ - Chris Drew

这很大程度上取决于两个向量的大小和向量分配器算法的实现。 - EdChum

不确定您是否已经检查过，但请记住，性能是仅当您确定它是一个“问题”时才应关注的事情。除非您的向量非常大，或其中的项目构造/复制成本很高，否则您不会注意到太大的差异。不要花费大量时间将一个0.2毫秒的操作减少到0.1毫秒，除非您需要每秒执行数千次 :-) - paxdiablo

如果性能不是问题的话，我建议你选择那个更容易阅读的。在长时间之后回到代码时，代码的可读性非常重要。 - rozina

Answer 1

第一种方法可能更有效，因为您可以保证只执行一次内存分配。在第二种方法中，很有可能（大多数实现都会这样做）在向量构造期间进行A.size()的分配，然后insert将触发第二次分配，因为它需要按B.size()的元素进行扩展。

- David Rodríguez - dribeas

Answer 2

方法一不会发生任何重新分配，而方法二可能会重新分配多次，并且在实践中很可能重新分配一次。因此，方法一更好。

- Kerrek SB

---

被插入的迭代器范围使用RandomAccessIterators，因此可以在O(1)时间内计算插入的元素数量，因此在第二种方法中没有重新分配内存的借口。 - Jonathan Wakely

@JonathanWakely：这是否是实际保证，还是仅为常见实现？（我知道range构造函数有一个实际保证。） - Kerrek SB

@KerrekSB：即使标准没有保证，这也是被认为是一个 bug 的事情之一。 - David Rodríguez - dribeas

不能保证，但这就是为什么我说“没有借口”而不是“如果重新分配则是一个错误” :-) 如果你的供应商的实现在插入RandomAccessIterators时没有计算元素数量，那么你一定要投诉。除了InputIterators之外，接受迭代器范围的vector构造函数必须计算元素数量，但是insert范围却不需要。 - Jonathan Wakely

@JonathanWakely：我经常向我的供应商抱怨 :-) - Kerrek SB

Answer 3

我认为第一个比第二个更快，因为它只执行一次内存分配，而第二个可能至少需要重新分配一次。但是我的测量结果表明，在大小小于约100,000时，这甚至更快速：

std::vector<int> AB(A.size() + B.size());
std::copy(A.begin(), A.end(), AB.begin());
std::copy(B.begin(), B.end(), AB.begin() + B.size());

我猜测这是因为，它不仅执行一次分配和无任何重新分配，甚至不需要检查是否应该进行任何重新分配。缺点是它可能需要初始时清零所有内存，但我认为CPU在这方面做得很好。

- Chris Drew

---

缺点是它必须将所有内存清零。我查看了生成的汇编代码，无法解释如此巨大的差异，但显而易见的是，优化器删除了内存清零操作。第一个和你的版本的基本生成代码相同，但代码结构略有不同，看起来优化器更适合处理最后一种选项... - David Rodríguez - dribeas

@DavidRodríguez-dribeas 很有趣。这已经不是我第一次惊讶于“清零内存并覆盖”方法与“保留内存并插入”方法的比较了。例如，std::vector<int> A(size); for(size_t i=0;i!=size;++i) A[i]=func(i); 表现出意外的良好性能。也许你是对的，优化器会删除内存清零的操作。 - Chris Drew