8

考虑以下两种将元素附加到向量中的方法

std::vector<int> vi1(10,42), vi2;

vi2.insert(vi2.end(),vi1.begin(),vi1.end());
<OR>
std::copy(vi1.begin(),vi1.end(),std::back_inserter(vi2));

std::copy版本看起来更干净，我不必输入vi2两次。但是由于它是一个通用算法，而 insert 是一个成员函数，它可以比它insert执行得更好std::copy还是做同样的事情？

我可以对自己进行基准测试，但我必须对每种模板类型的每个向量都进行基准测试。有人已经做过了吗？

4

4 回答 4

9

有一些细微的差别。在第一种情况 ( std::vector<>::insert) 中，您为容器提供了一个范围，因此它可以计算距离并执行单个分配器以增长到最终所需的大小。在第二种情况下std::copy（

请注意，即使需要多次重新分配，插入的摊销成本仍必须保持不变，因此这并不意味着渐近成本变化，但可能很重要。另请注意，该库的一个特别智能的实现具有通过专门std::copy处理反向插入迭代器的行为来使第二个版本高效的所有必需信息（尽管我没有检查任何实现是否确实这样做）。

于 2013-01-17T15:23:48.307 回答
1

vector::insert在大多数情况下，在 C++ 标准库的大多数主流实现上可能会表现得更好。原因是vector对象对当前分配的内存缓冲区具有内部知识，并且可以预先分配足够的内存来执行整个插入，因为可以使用随机访问迭代器预先计算元素的数量。但是，std::copywithstd::back_inserter会一直调用vector::push_back，这可能会触发多次分配。

std::vector::insert例如，在 libstdc++ 中的 GNU 实现，如果迭代器类别是RandomAccessIterator. 使用输入迭代器，vector::insert可能等价于std::copy，因为您无法提前确定元素的数量。

于 2013-01-17T15:22:38.070 回答
1

您会认为这vector::insert可能能够优化一次插入多个项目的情况，但它比看起来更难。例如，如果迭代器是输出迭代器怎么办 - 无法提前知道您将执行多少次插入。insertjust的代码很可能push_back与back_inserter.

于 2013-01-17T15:24:26.430 回答
0

它不等同于std::copy。它相当于push_back（在某种意义上）。

是的，std::back_inserter做同样的事情，std::copy如果你使用它也可以插入前面std:front_inserter（尽管你不能使用它std::vector）。如果您改用它，它也可以在指定的迭代器处插入std::inserter。所以你看，std::copy根据你作为第三个参数传递的内容来做事。

现在回到问题的本质。我认为您应该使用insert，因为它可以更好地执行，因为它可能会发现要插入的元素数量，因此它可能会一次分配那么多内存（如果需要）。在您的情况下，它可能会表现得更好，因为v1这std::vector意味着在 O(1) 时间内很容易计算元素的数量。

于 2013-01-17T15:18:27.803 回答