C++中向量的初始容量

Question

在使用默认构造函数创建的 std::vector 中，capacity() 是什么？我知道 size() 为零。我们能否说明默认构造的向量不调用堆内存分配？

这样就可以使用单个分配创建具有任意保留的数组，例如 std::vector<int> iv; iv.reserve(2345);。假设出于某种原因，我不想将 size() 设为 2345。

例如，在 Linux (g++ 4.4.5, kernel 2.6.32 amd64) 上。

#include <iostream>
#include <vector>

int main()
{
  using namespace std;
  cout << vector<int>().capacity() << "," << vector<int>(10).capacity() << endl;
  return 0;
}

输出0,10。这是一个规则，还是与STL供应商有关？

- Notinlist

---

标准并没有规定向量（vector）的初始容量，但大多数实现会使用0作为初始容量。 - Mr.Anubis

不能保证，但我会严重质疑任何未经我请求就分配内存的实现的质量。 - Mike Seymour

不同意。一个真正高性能的实现可能包含一个小的内联缓冲区，在这种情况下，将initial capacity()设置为该值是有意义的。 - al45tair

使用 swap 时，所有迭代器和引用都保持有效（除了 end()）。这意味着内联缓冲不可行。 - Notinlist

Answer 1

标准未指定容器的初始capacity，因此您依赖于实现。一个常见的实现将从零开始容量，但没有保证。另一方面，没有比您的策略更好的方法：std::vector<int> iv; iv.reserve(2345);，因此请坚持使用。

- Mark Ransom

---

实用角度上，你知道有没有任何实现在默认构造函数中分配内存的向量吗？尽管标准没有保证，但正如Mike Seymour所指出的，如果不必要地触发分配，这将会是对于实现质量的一种不良迹象。 - David Rodríguez - dribeas

“那不是重点。前提是“你不能比现有策略做得更好，所以不要费心想可能存在的愚蠢实现方式”。如果前提是“不存在这样的实现方式，所以不必费心”，我会同意。结论恰好是正确的，但推论不成立。抱歉，也许我有点吹毛求疵。” - bitmask

如果存在一个在默认构造时分配内存的实现，那么按照你所说的做法可以将分配次数减半。但是vector::reserve并不等同于指定初始大小。那些带有初始大小参数的向量构造函数会初始化 n 个对象，因此具有线性复杂度。另一方面，仅调用reserve只意味着 如果 触发了重新分配，则只需复制/移动 size() 个元素。对于空向量，没有任何要复制的内容。因此，即使实现为默认构造向量分配内存，后者也可能是理想的选择。 - Praetorian

如果@bitmask对分配有如此关注，则应查看您特定的标准库实现，而不是依赖猜测。 - Mark Ransom

自从C++17以来，默认构造函数是noexcept (noexcept Allocator())。我认为只有在默认构造向量时没有保留容量时，这才能起作用。 - 463035818_is_not_a_number

Answer 2

std::vector的存储实现因实现不同而显著变化，但我遇到过的所有实现都从0开始。

以下代码：

#include <iostream>
#include <vector>

int main()
{
  using namespace std;
  
  vector<int> normal;
  cout << normal.capacity() << endl;
  
  for (unsigned int loop = 0; loop != 10; ++loop)
  {
      normal.push_back(1);
      cout << normal.capacity() << endl;
  }
  
  cin.get();
  return 0;
}

输出如下：

0
1
2
4
4
8
8
8
8
16
16

在GCC 5.1、11.2和Clang 12.0.1下：

0
1
2
3
4
6
6
9
9
9
13

在 MSVC 2013 下。

- metamorphosis

---

这真是被低估了 @Andrew - Valentin Mercier

你会发现几乎无论在哪里，为了提高速度，推荐的方法几乎总是使用向量。所以，如果你要处理稀疏数据的话... - Andrew

我真的很惊讶，第一次分配的容量会变成1字节，而不是至少分配给管理其块的分配器保留的字节数（在64位实现中为16字节）。更重要的是，大多数情况下，分配都会对齐，以便指针对于SSE4或甚至AVX512等内容进行对齐... - Alexis Wilke

@AlexisWilke 一个元素，不是一个字节。对于容器而言，元素可能是1000个字节。然而，我的容器总是基于sizeof(container)与sizeof(element)以及任何合理的因素来确定第一个分配块的大小(plf::)。 - metamorphosis

Clang 10.0.1和GCC 10.2与GCC 5.1在这个答案中达成了一致。https://godbolt.org/z/3nzG6n - s3cur3

Answer 3

据我理解标准（尽管我无法引用参考资料），容器实例化和内存分配被有意地解耦，这是有很好的原因的。因此，您需要不同的、独立的调用来完成以下操作:

- constructor 来创建容器本身 - reserve() 来预先分配一个足够大的内存块，以容纳至少给定数量的对象

这是非常有道理的。 reserve() 的唯一存在理由是为了让您有机会编写可能昂贵的重新分配代码，以便扩大向量。为了有用，您必须知道要存储的对象数量或至少需要能够做出合理的猜测。如果没有这个条件，最好远离 reserve()，因为您只会将重新分配变为浪费的内存。

所以把它们整合起来:

- 标准有意地 不 指定允许您预先分配特定数量对象的内存块的构造函数（这至少比在底层分配一个实现特定的固定“something”更为可取）。 - 分配不应该是隐式的。因此，要预先分配一个块，您需要通过调用 reserve() 进行单独操作，并且这不需要在同一位置进行构建（当然可以稍后，在您意识到所需大小时）。 - 因此，如果向量总是预先分配实现定义大小的内存块，那么 reserve() 的预期作用就无法实现了，不是吗？ - 如果 STL 自然无法知道向量的预期用途和大小，那么预分配块的优点是什么？它将相当荒谬，如果不是适得其反。 - 正确的解决方案是使用第一个 push_back() 分配实现特定的块——如果之前没有被显式地由 reserve() 分配。 - 在必要时重新分配块的增加大小也是实现特定的。我所知道的向量实现都从指数上升开始，但会将增加率限制在某个最大值以避免浪费大量内存甚至爆炸。

只有在不受分配构造函数的干扰时，所有这些才能完全发挥作用和优势。对于常见情景，您有合理的默认值，可以通过reserve()（和shrink_to_fit()）根据需要进行覆盖。因此，即使标准没有显式说明，我相信假设新构造的向量不会预先分配是当前所有实现的一个相当安全的选择。

- Don Pedro

Answer 4

作为对其他答案的轻微补充，我发现在使用Visual Studio进行调试时，即使容量从零开始，一个默认构造的向量仍然会在堆上分配内存。

具体来说，如果_ITERATOR_DEBUG_LEVEL != 0，则向量将分配一些空间以帮助迭代器检查。

https://learn.microsoft.com/en-gb/cpp/standard-library/iterator-debug-level

我刚发现这有点令人烦恼，因为我当时正在使用自定义分配器，没有预料到会有额外的分配。

- David Woo

---

有趣的是，它们打破了noexcept保证（至少对于C+17，之前的版本呢？）：http://en.cppreference.com/w/cpp/container/vector/vector - Deduplicator

Answer 5

这是一个老问题，所有答案都已经正确地解释了标准的观点和使用 std::vector::reserve 以便以便以便以便在可移植的方式下获取初始容量的方法;

然而，我将解释为什么 对于任何STL实现来说，在构造一个 std::vector<T> 对象时分配内存是没有意义的;

1. std::vector<T> of incomplete types;

   Prior to C++17, it was undefined behavior to construct a std::vector<T> if the definition of T is still unknown at point of instantiation. However, that constraint was relaxed in C++17.

   In order to efficiently allocate memory for an object, you need to know its size. From C++17 and beyond, your clients may have cases where your std::vector<T> class does not know the size of T. Does it makes sense to have memory allocation characteristics dependent on type completeness?

2. Unwanted Memory allocations

   There are many, many, many times you'll need model a graph in software. (A tree is a graph); You are most likely going to model it like:

   class Node {
       ....
       std::vector<Node> children; //or std::vector< *some pointer type* > children;
       ....
    };
   

   Now think for a moment and imagine if you had lots of terminal nodes. You would be very pissed if your STL implementation allocates extra memory simply in anticipation of having objects in children.

   This is just one example, feel free to think of more...

- WhiZTiM

Answer 6

标准没有指定容量的初始值，但STL容器会自动增长以容纳您放入的数据，前提是不要超过最大大小（使用max_size成员函数了解）。 对于vector和string，每当需要更多空间时，增长都由realloc处理。假设您想创建一个包含值1-1000的向量。如果没有使用reserve，则代码通常会在以下循环期间导致2到18次重新分配：

vector<int> v;
for ( int i = 1; i <= 1000; i++) v.push_back(i);

修改代码使用reserve可能会导致循环期间产生0次分配：

vector<int> v;
v.reserve(1000);

for ( int i = 1; i <= 1000; i++) v.push_back(i);

大致来说，向量和字符串的容量每次增长1.5到2倍。

- Archie Yalakki