std::vector push_back() 语义学

Question

我理解std::vector中的push_back将传递的对象的副本放置在末尾。

让我们考虑这个简单的例子。

class Foo
{
public:
  Foo(int i=-1) :i_(i) {std::cout << "Foo:" << i_ << std::endl;}

  Foo(const Foo& rhs) 
  {
    i_ = rhs.i_;
    std::cout << "Foo copy CTOR:" << i_ <<  std::endl;
  }

  ~Foo() {std::cout << "~Foo:" << i_ << std::endl;}

private:
  int i_;
};

这段代码片段如下：

void testObjects()
{
  std::vector<Foo> vFoo;

  for (int i=0; i < 3; i++)
  {
    std::cout << std::endl;
    Foo aFoo(i+100);
    vFoo.push_back(aFoo);
    std::cout << "i=" << i << " vector size=" << vFoo.size() 
              << std::endl;
  }
  std::cout << "end of loop - vector size=" << vFoo.size() 
            << std::endl << std::endl;
}

我得到的结果是：

Foo:100
Foo copy CTOR:100
i=0 vector size=1
~Foo:100

Foo:101
Foo copy CTOR:100
Foo copy CTOR:101
~Foo:100
i=1 vector size=2
~Foo:101

Foo:102
Foo copy CTOR:100
Foo copy CTOR:101
Foo copy CTOR:102
~Foo:100
~Foo:101
i=2 vector size=3
~Foo:102
end of loop - vector size=3

~Foo:100
~Foo:101
~Foo:102

我印象中向量增加了一个元素（符合预期），并且其内容被移位（向下？），导致额外的拷贝构造。我的理解正确吗？

提前感谢您的时间。

敬礼

- user2857891

---

是的，你是正确的。如果你想要证明，加一个reserve调用然后看看有什么变化。 - David Schwartz

Answer 1

如果向量的内容发生了移动，push_back() 就无法实现平摊常数时间。

根据输出结果，我认为你的 std::vector 实现从容量为 0 或 1 开始，并且每当容量超过当前大小时就会使容量加倍。你看到的不是向量内容的移动，而是内存缓冲区的重新分配。

要验证这一点，请在声明 vFoo 后添加以下行：

vFoo.reserve(16);

在此之后，您不应该再看到额外的复制构造函数调用。

或者，您可以将测试代码运行至更高的向量大小（至少到4），并验证所有元素的复制构造发生次数越来越少。长期来看，N个插入应该只有最多O(log N)次重新分配。

如果上述情况不成立，则说明您正在使用损坏的std::vector实现，该实现不符合C++标准。

- Krzysztof Kosiński

---

Krzysztof：你说得完全正确。调用“reserve”使打印语句的行为符合预期。那么，在插入之前总是预留容量是一个好习惯吗？特别是当我有一个要推送的元素数量的估计时（例如，保留到比预期大小大的最小2次幂...） - user2857891

@user2857891 并不总是需要使用 reserve。如果您事先不知道要插入多少元素，则无法有意义地调用 reserve。它也不需要是二的幂。如果您知道要插入多少元素，请 reserve 相应的空间。否则，只需让向量在增长时重新分配内存，它会尝试以高效的方式执行此操作。 - jalf

虽然使用保留更安全（下限总是安全的），但最好猜测一下。它在渐近意义下并不更有效，但如果你猜得接近，可以节省约一半的时间。 - Theo Belaire