C++ push_back vs插入vs emplace

我目前正在制作一个使用C++向量的应用程序。C++ push_back vs插入vs emplace

我知道预优化是如何成为万恶的根源。

但我真的不禁好奇。

我将其他矢量的部分添加到另一个矢量中。
我们会说的载体将有一个大小永远的300

变化由于我一直追加到矢量

的到底是快做：
a.reserve(300);
a.insert(a.end(), b.begin(), b.end());

或者是否会更快地循环遍历我想追加的矢量，并分别在push_back或emplace之间单独添加每个项目（虽然仍在预先保留）。（不确定哪个更快）

任何人都可以帮助我吗？

来源

2013-02-21 Darkalfx

“有效STL”第5项：不想区间成员函数自己的单元素 – Cubbi 2013-02-21 18:19:57

去为更清晰的代码，用什么STL为您提供...不重复，除非你要。在大多数情况下重用代码将胜过这种简单操作的手工定制版本。这些功能在设计时考虑到了效率。 – eazar001 2013-02-21 18:22:32

'insert'可能更快，或者它可能差不多，但是（缺少一个不好的库实现）将永远不会比循环更糟糕。 – 2013-02-21 18:23:06

这里有一个基本原则：当库提供两种do_x_once和do_x_in_batch，则后者至少应尽可能快地在一个简单的循环中调用do_x_once。如果不是这样，那么这个库很难实现，因为一个简单的循环足以获得更快的版本。通常，这样的批次函数/方法可以执行额外的优化，因为他们具有数据结构内部的知识。

所以，insert应至少快在一个循环push_back。在这种情况下，智能实现insert可以为您想要插入的所有元素执行单个reserve。 push_back每次都必须检查向量的容量。不要试图智取图书馆:)

来源

2013-02-21 18:31:00

这确实对我有帮助。我对C++比较陌生。对于我想插入的所有元素，单个保留是什么意思？想你可以给我更多的细节？ – Darkalfx 2013-02-21 19:13:18

@Darkalfx：对于某些类型的迭代器，'insert'可以使用'b.begin（） - b.end（）'计算要插入的元素的数量。当它知道元素的数量时，它可以在矢量中为一个操作中的那个数字创建空间。 – 2013-02-21 19:30:11

正如larsmans所说，你在单个图书馆电话中做得越多，更有可能更有效率。在insert, 的情况下，该库通常至多会执行一次单独的重新分配，并且最多复制每个移位的元素一次。如果您使用循环和push_back，它可能会重新分配几次次，这可能会显着较慢（如大小为的次序）。

根据不同的类型，但是，它也可能会更快做类似：

a.resize(300); 
std::copy(b.begin(), b.end(), a.end() - 300);

我发现这是更快简单标量类型（如 int）使用G ++上英特尔机器。

来源

2013-02-21 18:40:26

作为一个方面说明：'resize'不应该循环为'push_back'（甚至一个功能，这是一个循环内内）内部调用（我假设'insert'）需要摊销固定的时间（指数增长步）而保守的“调整大小”打破了这一点。 – BCS 2013-09-26 23:00:10

@BCS'resize'通常会在循环之前调用，而不是在循环中调用。这里的问题是'resize' +'[]'vs.'reserve' +'push_back'。 – 2013-09-27 08:32:22

我想这确实取决于编译器（库实现），编译选项和体系结构。英特尔®至强®在VS2005做一个快速的基准，而不优化（/ 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项...“：

为 'B' 预留空间，然后循环使用b.push_back(a[i]);：0.808秒
调整大小 'B'，然后循环利用指标分配b[i] = a[i];：0.264秒
没有大小调整'b'，只是b.insert(b.end(), a.begin(), a.end());：0.021秒（与储备第一无显著差异）
std::copy(a.begin(), a.end(), std::back_inserter(b));：0.944秒（0.871与储备第一）
调整尺寸 'b'，然后MEMCOPY在基指针memcpy(&(b[0]), &(a[0]), 10000000*sizeof(int));：0.061秒

随着优化开启（/ OX），然而，这是一个不同的故事。我不得不增加尺寸为100 000 000，以获得更多的分化：

的push_back循环：0.659秒
指数环：0.482秒
插入：0.210秒（与储备第一无显著差异）
标准::复制：0.422秒，预留第一。没有它就得到了bad_alloc。
的memcpy：0.329秒

什么有趣的是，有或没有优化，插入方法线性缩放。其他方法在没有优化的情况下明显效率低下，但仍然无法与它们一样快。正如James Kanze指出的那样，它在g ++上有所不同。用自己的平台运行测试来验证。

来源

2013-03-22 14:56:23 OlivierD

C++ push_back vs插入vs emplace

回答

相关问题