std::vector和复制构造函数

Question

vector<X> v;
X x;
v.push_back(x); v.push_back(x); v.push_back(x);

为什么这段代码会调用类 X 的拷贝构造函数6次？（使用g++ 4.7.2 STL）

请告诉我，关于这个特定的STL，在幕后发生了什么 确切的事情。

- Cartesius00

---

很可能是由于某些重定位（一个向量的所有元素必须在连续的内存块中）的原因。 - Kiril Kirov

@KirilKirov 是的，那肯定没错，但我想确切地知道底层发生了什么。 - Cartesius00

这是实现定义的。据我所知，标准对此没有任何规定。 - Kiril Kirov

尝试调用v.reserve(3)，这应该会减少复制构造函数的调用次数。 - 0x26res

Answer 1

使用push_back()插入x时，内存最终会被重新分配以为新元素腾出空间。已插入的成员必须使用复制构造函数X(const X&)进行复制。

如果您插入

v.reserve(3);

至少在前三个push_back()操作中会防止重分配，结果只会有三次调用X(const X&)

- Olaf Dietsche

---

一般来说，那是对的，但我提供了一个更准确的答案。 - Cartesius00

Answer 2

您可以使用向量保留来提前在向量中创建空间，以加快向向量添加元素的速度，并防止这种情况发生。

- const_ref

---

resize 实际上会创建新的对象，因此在 3 个新对象上调用默认构造函数。push_back 将新创建的对象添加到列表末尾，他最终将在向量中拥有 6 个项目。reserve 是他在这里需要的。 - emartel

Answer 3

正确的答案是，std::vector 是使用双倍数组实现的（参见：http://en.wikipedia.org/wiki/Dynamic_array），它大约调用了 2 * N 次复制构造函数。

例如，对于 N = 100,000，它会调用复制构造函数 231,071 次。正如已经指出的那样，可以通过调用 v.reserve() 来减少重新分配的次数。

- Cartesius00

---

“正确答案”是您编译器实现的std::vector是使用双倍数组实现的。标准并不要求这样做。 - Angew is no longer proud of SO

@Angew 我只考虑gcc的实现。请看问题。 - Cartesius00

如果向量每次大小不足时都加倍，那么您大约会产生log(N)次复制构造函数调用，而不是2*N次。 - Stefano Falasca

Answer 4

这是发生的事情：

在第一次 push_back 之前，向量的容量（它已分配空间中适合的元素数）为0。所以当您进行第一个push_back时，它会分配一个项目的空间并调用复制构造函数（第一次调用）。

现在容量为1，您告诉它添加另一个项目。因此，它必须再次分配更多的空间，本例中为另一个项目分配空间并将原始项目复制到新空间（第二次调用）。第二个push_back再次调用了复制构造函数（第三次调用）。

现在容量为2，您告诉它添加另一个项目。因此，它必须再次分配更多的空间并将项目复制到新空间（第四次和第五次调用）。然后第三个 push_back 再次调用了复制构造函数（第六次调用）。

正如其他人指出的那样，您可以使用 reserve 来预先分配空间，避免重新分配和因此调用复制构造函数的需求。

- MikMik