C++ push_back vs Insert vs emplace

Question

我目前正在使用带有C++的向量来创建应用程序.

我知道预先优化是多么邪恶的根源.

但我真的不禁好奇.

我正在将其他矢量的一部分添加到另一个矢量中.
我们会说矢量的大小永远不会改变300.

因为我总是附加到向量的末尾

做得更快:
a.reserve(300);
a.insert(a.end(), b.begin(), b.end());

或者会是通过我想与追加和单独添加每个项目(同时仍保留事前)矢量更快的循环push_back或emplace.(不确定哪个更快)

有人可以帮我吗？

Answer 1

这是一个一般原则:当一个库同时提供do_x_once和时do_x_in_batch,后者应该至少与do_x_once在一个简单的循环中调用一样快.如果不是,那么库的实现非常糟糕,因为简单的循环足以获得更快的版本.通常,这样的批处理函数/方法可以执行额外的优化,因为它们具有数据结构内部的知识.

所以,insert应该至少是同样快如push_back在一个循环.在这种特殊情况下,智能实现insert可以reserve为您要插入的所有元素执行单个实现.push_back每次都必须检查矢量的容量.不要试图超越图书馆:)

Answer 2

我想这真的取决于编译器（库实现）、编译选项和架构。在 VS2005 中进行快速基准测试，无需在 Intel Xeon 上进行优化 (/Od)：

std::vector<int> a;
std::vector<int> b;

// fill 'a' with random values for giggles

timer.start()
// copy values from 'a' to 'b'
timer.stop()

我使用这些不同的“复制值...”方法获得了 10 000 000 个项目的这些结果：

1. 为“b”保留空间，然后使用b.push_back(a[i]);：0.808 秒进行循环
2. 调整“b”的大小，然后使用索引分配进行循环b[i] = a[i];：0.264 秒
3. 没有重新调整大小 'b'，只是b.insert(b.end(), a.begin(), a.end());：0.021 秒（与保留优先没有显着差异）
4. std::copy(a.begin(), a.end(), std::back_inserter(b));：0.944 秒（0.871 保留优先）
5. 调整“b”的大小，然后在基指针上进行内存复制memcpy(&(b[0]), &(a[0]), 10000000*sizeof(int));：0.061 秒

但是，在启用优化 (/Ox) 后，情况就不同了。我不得不将大小增加到 100 000 000 以获得更多差异化：

1. push_back 循环：0.659 秒
2. 索引循环：0.482 秒
3. 插入：0.210 秒（与保留优先没有显着差异）
4. std::copy: 0.422 秒，保留优先。没有它就得到了一个 bad_alloc。
5. memcpy：0.329 秒

值得注意的是，无论有没有优化，插入方法都是线性缩放的。其他方法在没有优化的情况下显然效率低下，但仍然无法快速使用它们。正如 James Kanze 所指出的，它在 g++ 上有所不同。使用您自己的平台运行测试以进行验证。