c++ - 如何在 C++ vector 中存储内容

Question

几乎所有关于在线判断的问题都需要存储一堆值然后处理它们的基本工作。我通常将 std::vector 用于这些，但我担心使用 push_back() 存储每个元素对性能不利。

目前我这样做:

vector<int> vec;
int x;
for(int i=0;i<10;i++)
{
 cin>>x;
 vec.push_back(x);
}

但是我想如果这样会更好

vector<int> vec;
int x;
vec.reserve(10);
for(int i=0;i<10;i++)
 cin>>vec[i];

哪个更合适？ ，性能有什么区别吗？假设我有充分的理由避免使用 C 样式数组，是的，我事先知道 vector 的初始大小。

Answer 1

首先，请注意，在您的第二个示例中有一个明显的错误:reserve 扩展了 vector 的容量，即您可以放入其中的元素数量没有 vector 执行重新分配，但不影响其逻辑大小。出于这个原因，如果您执行 reserve，您仍然必须执行 push_back，否则您将访问循环中逻辑上不存在的元素。您的意思可能是 resize，它将逻辑大小和容量都扩展到请求的大小。

现在开始表演:

普通 push_back 与 reserve + push_back:大部分相同(如果拷贝便宜)

即使没有reserve， vector 也将在摊销常数时间内达到所需的容量(实际上是在 O(log N) 时间内，无论如何隐藏在循环的 O(N) 中)。

好的，如果您已经确定您的 vector 将占用的大小，它将避免重新分配，但不要跳过箍来确定要保留多少。

异常(exception):具有昂贵复制构造函数的类型(C++11 中的移动构造函数)。如果您要存储复制/移动成本高昂的对象，您将希望避免重新分配，因此 reserve 在这里可能会有所帮助(尽管通常您通过指针存储此类类型，以避免出现问题)。

resize + operator[]:“简单”类型更快

我实际看到在处理简单类型(通常是 POD，或一般具有极其简单的构造函数/赋值运算符的东西)时稍微提高性能的方法是预先执行 resize，然后通过 [] 运算符进行赋值。

这避免了 push_back 的额外复杂性，它必须检查容量并增加“逻辑大小”；通过下标运算符 OTOH 进行赋值，优化后解析为少量汇编指令。

当然，当您有复杂类型时，您不希望调整大小和分配，其中初始默认构造和分配抵消了push_back必须进行的轻量记账做。