C++向量，在堆栈上扩展/重新分配时会发生什么？

Question

我是C++的新手，正在我的项目中使用vector类。我发现这很有用，因为我可以拥有一个数组，每当需要时它会自动重新分配内存空间（例如，如果我想要添加一个元素到vector中，而且vector已经达到了它的最大容量，它就会向操作系统请求更多的内存空间），所以访问vector的元素非常快速（不像列表，我必须遍历前n个元素才能访问第n个元素）。

我发现这个问题非常有用，因为他们的答案完美地解释了当我想要将我的vector存储在堆栈上时，"内存分配器"如何工作：

[1] vector<Type> vect;
[2] vector<Type> *vect = new vector<Type>;
[3] vector<Type*> vect;

然而，有一个问题一直困扰着我，我找不到答案：每当我构造一个向量并开始推入大量的元素时，它会达到一个向量已满的时刻，所以为了继续增长它需要重新分配内存，在新位置上复制自身，然后继续推入元素（显然，这种重新分配在类的实现中是隐藏的，因此对我来说是完全透明的）。

好吧，如果我在堆上创建了这个向量[2]，我可以想象可能发生了什么：类vector调用malloc，获取新空间，然后将自身复制到新内存中，最后通过调用free删除旧内存。

然而，当我在栈上构造一个向量[1]时，有一个面纱隐藏了正在发生的事情：当向量必须重新分配时会发生什么？据我所知，每当在C/C++中进入一个新函数时，计算机都会查看变量的声明，然后扩展栈以获得放置这些变量所需的空间，但是当函数已经运行时，无法在栈上分配更多的空间。那么类vector如何解决这个问题呢？

注： [1] 在栈上构造一个向量，意味着简单地使用vector my_vector(n)（其中n是足够大的）。 [2] 在堆上构造向量，即使用vector* my_vector = new vector(n)。

- Karl

---

显然，那个问题中的答案根本没有完美地解释清楚，因为你得到了完全错误的想法。 - R. Martinho Fernandes

向量分配其数据到某个可以在运行时增长的位置。向量对象本身的大小保持不变，因为它保留了对动态分配数据的固定大小句柄。 - juanchopanza

好的，通过以下回答，我理解了vector对象的数据结构：正如@juanchopanza所说，它是一组指针，用于定义位于堆上并在其中存储对象的数组的大小。由于这个数组位于堆上，如果需要更多空间，它可能会被重新分配。顺便说一句，抱歉我的英语语法！我希望通过练习能够改善它！ - Karl

很常见的一个误解是认为，仅仅因为你写了 std::vector<...> myvect; 和 std::vector<...> *myvect = new std::vector<...>; 这两种不同的语句，你就会在前者中得到 栈分配 而在后者中得到 _堆分配_。事实并非如此；虽然对于 new ... 的情况，堆内存几乎是必然的，但容器类型的 内部实现 决定了当你在本地实例化它时会发生什么。只有某些容器（例如 std::array）会 嵌入 它们的内容。而 std::vector 则不会。 - FrankH.

Answer 1

你写道

[...] 将自己复制到新位置 [...]

这不是向量的工作方式。向量数据被复制到新位置，而不是向量本身。

我的回答应该让你了解向量的设计思路。

常见的std::vector布局*

注意：实际上，std::allocator 很可能是一个空类，std::vector 可能不包含此类的实例。对于任意分配器来说，这可能不是真的。

在大多数实现中，它由三个指针组成，其中

• begin 指向堆上向量数据内存的起始位置（如果不是 nullptr，则始终在堆上）
• end 指向向量数据的最后一个元素的下一个内存位置 -> size() == end-begin
• capacity 指向向量内存的最后一个元素的下一个内存位置 -> capacity() == capacity-begin

栈上的向量

我们声明一个类型为 std::vector<T,A> 的变量，其中 T 是任何类型，A 是 T 的分配器类型（即 std::allocator<T>）。

std::vector<T, A> vect1;

这在内存中是什么样子？

如我们所见：堆上没有任何事情发生，但变量占用了栈上所有成员所需的内存。它就在那里，并将保留在那里，直到 vect1 超出其作用域，因为 vect1 就像任何其他类型的对象（例如 double、int 等）一样，会坐在其栈位置等待被销毁，而不管它自己在堆上处理多少内存。

由于向量为空，vect1 的指针没有指向任何地方。

一个堆上的向量

现在我们需要一个指向向量的指针，并使用一些动态堆分配来创建向量。

std::vector<T, A> * vp = new std::vector<T, A>;

让我们再次看一下内存。

我们的vp变量在栈上，而我们的向量现在在堆上。由于向量的大小是固定的，所以向量本身不会在堆上移动。只有指针（begin、end、capacity）会在重新分配时跟随数据位置在内存中移动。让我们来看一下这个过程。

向向量中添加元素

现在我们可以开始向向量中添加元素了。让我们看一下vect1。

T a;
vect1.push_back(a);

变量vect1仍然保持不变，但是在堆上分配了内存来容纳一个T元素。

如果我们再添加一个元素会发生什么？

vect1.push_back(a);

• 由于仅有一个内存位置，堆上为数据元素分配的空间将不足。
• 新的内存块将被分配用于两个元素。
• 第一个元素将被复制/移动到新的存储位置。
• 旧的内存将被释放。

我们发现：新的内存位置是不同的。

为了获得更多的见解，让我们看一下如果我们销毁最后一个元素的情况。

vect1.pop_back();

分配的内存不会改变，但最后一个元素将调用其析构函数，并且结束指针向下移动一个位置。

如您所见：capacity() == capacity-begin == 2，而size() == end-begin == 1。

- Pixelchemist

---

嗯...我想我的第一印象是错误的，关于实现：由于向量的数据具有固定大小，无论向量有多大，它都可以在堆栈上存储而不会出现任何问题：分配器将请求更多的堆大小并且数据指针将更改。现在我明白为什么使用GDB查看存储在向量中的数据不那么直观了。谢谢@Pixelchemist！ - Karl

@Karl：如果你想要一个栈分配的“向量”，请使用std::array。缺点是...它无法调整大小。确切地说，由于std:array（容器和其内容）都驻留在堆栈上，因此“在堆栈中移动”是不可能的。 - FrankH.

你确定“分配器对象”占用堆栈空间吗？在32位和64位架构中，sizeof(std::vector<int>)分别返回12和24。（x86_64，Ubuntu 13.04，gcc 4.7.3） - stanm

@stanm：std::allocator 可能为空，但您可以拥有一个需要实例的用户定义分配器。例如，在 MSVS 中，如果 std::vector 不为空，则包含分配器的实例。 - Pixelchemist

@Pixelchemist：哦，我明白了，std::vector<int, special_allocator> 本质上是一个不同于 std::vector<int> 的类。当然，你需要在某个地方保存那个分配器。谢谢。 - stanm

Answer 2

向量对象可能在堆栈上被实例化，但是向量内的数据将存储在堆中。

（这个特点适用于简单类 class foo {int* data;};）

- Bathsheba

---

事实上，如果一个foo实例在堆栈上创建，那么你的琐碎类就有一个指针在堆栈上。这是所有指针类型变量声明共有的特征。即使int * data;也是如此。 - Pixelchemist

是的，你说得对，但我的观点是数据指向的内存（可能）是堆分配的。通俗地说，这就是STL向量可以工作的方式。 - Bathsheba

Answer 3

你构建向量的方式（堆栈或堆）对此并不重要。

请查看std::vector的文档。

引用：

内部，向量使用动态分配的数组来存储其元素。当插入新元素时，可能需要重新分配此数组以增大其大小，这意味着需要分配一个新数组并将所有元素移动到其中。

当向量“增长”时，向量对象不会增长，只有内部动态数组会发生变化。

至于其实现，您可以查看GCC的向量实现。

为了保持简单，它将向量声明为具有一个受保护成员的类, 类型为{{link3：_Vector_impl}}。

正如您所看到的，它被声明为一个包含三个指针的结构：

• 一个指向存储（和数据开头）的开头
• 一个指向数据结尾
• 一个指向存储结尾的指针

- JBL

---

是的，我明白向量的内容存储在堆上（在我提出问题的每种情况下），但是...第一种情况下实例化在堆栈上的向量对象的内部数据是什么？我想它可能是一个“指针数组”（就像C语言中的经典数组），每当您push_back一个项目时，向量类会在堆上分配新的内存，然后将指针添加到这个指针数组中。 - Karl

@Karl，这可能只是一个指向数据的指针，加上用于大小和容量的数据成员。 - juanchopanza

“内容”（即实际支持向量的数组，也称为std::vector::data()）始终是堆分配的。对于堆栈分配的类似向量的容器，您需要使用std::array - 它具有与std::vector相同的迭代器和访问器，但无法调整大小，并且它是由大小模板化的。 - FrankH.

@Karl：vector的常见实现只有三个指针成员（非调试版本）T *begin,*end,*capacity;（如果无法优化，则可能还有一个分配器）。vector不包含所有元素的指针，而是一个指向第一个元素的单一指针和两个哨兵来确定有效元素停止的位置（end）和容量结束的位置（capacity）。添加更多元素将需要增长，这将重新设置三个指针为不同的值，但堆栈中的结构（即std::vector<int> v;中的v）大小不会改变。 - David Rodríguez - dribeas

@juanchopanza：你的评论不应该让人困惑。选择使用三个指针（如果需要还包括分配器）或者一个指针和两个 size_type 成员变量来追踪 size() 和 capacity() 是一种实现细节。这不应该影响到你，重要的是你确实需要追踪三个信息。关于分配器：默认分配器和很多/大多数符合 C++03 标准的分配器基本上是无状态的，并且可以进行空基类优化（empty base optimization），但是从概念上说（对于有状态的分配器也是实际的），容器必须持有一个分配器。 - David Rodríguez - dribeas

Answer 4

您正在询问有关实现vector的详细信息。 C ++标准没有定义vector应如何实现-它仅定义了vector应该执行什么操作以及需要实现哪些操作。由于每个编译器理论上都不同，没有人可以以100％的准确度告诉您vector重新分配时会发生什么。

话虽如此，理解vector通常是如何实现的并不难。向量本身只是一种数据结构，具有指向存储在vector中的实际数据的指针。 大致如下：

template <typename Val> class vector
{
public:
  void push_back (const Val& val);
private:
  Val* mData;
}

上述内容显然是伪代码，但你已经明白了。当一个vector被分配在栈上（或堆上）时：

vector<int> v;
v.push_back (42);

内存最终可能会看起来像这样：

+=======+        
| v     |
+=======+       +=======+
| mData | --->  |  42   |
+=======+       +=======+

当你向一个已满的vector执行push_back操作时，数据会被重新分配：

+=======+        
| v     |
+=======+       +=======+
| mData | --->  |  42   |
+=======+       +-------+
                |  43   |
                +-------+
                |  44   |
                +-------+
                |  45   |
                +=======+

...并且向量指针现在将指向新数据。

- John Dibling

---

我有一些疑问，如果我们在向量中push_back一个rvalue，那么会调用移动构造函数。如果容量耗尽会发生什么？我的意思是，移动通常会执行static_cast并将对象标记为rvalue，但在这种情况下，向量是否会分配内存并复制指针？ - unbesiegbar

Answer 5

一个向量不是元素数组，也不是用于存储这样元素的内存。

一个向量管理元素数组，为此分配、释放、缩小和增长所需的内存。

你如何分配向量本身的选择与向量自己关于如何在哪里分配它所管理的内存的决策没有任何联系。

我不想阻止你对向量内部工作方式的兴趣（它既有趣又有用），但是……编写类并记录它们的整个目的是你只需要了解接口，而不是实现。

- Useless

---

谢谢！你的回答补充了@juanchopanza的评论。是的，我同意编写类和文档的整个重点是专注于接口。然而，我认为人们必须至少对类的实现有一个模糊的概念，才能编写良好的代码并预测可能的错误：没有小精灵来做内存分配的肮脏工作！ - Karl

Answer 6

您还可以保留预期大小以供后续使用。

vect.reserve(10000);

这将保留使用的类型的10000个对象空间。

- aah134

Answer 7

如果您从空的状态开始创建一个可变大小的向量，将使用倍增策略和大部分时候是重新分配内存，例如在使用整数1到10000和clang(std=2a -O3)时，会得到这样的结果。这只是为了娱乐而已，展示了使用reserve的重要性。vector::begin()指向实际数组的开头，而vector::capacity显示实际容量。另一方面，迭代器失效也被展示出来了。

std::vector<int> my_vec;
auto it=my_vec.begin();
for (int i=0;i<10000;++i) {
    auto cap=my_vec.capacity();
    my_vec.push_back(i);
    if(it!=my_vec.begin()) {
        std::cout<<"it!=my_vec.begin() :";
        it=my_vec.begin();
    }
    if(cap!=my_vec.capacity())std::cout<<my_vec.capacity()<<'\n';
}

这将产生以下结果：

it!=my_vec.begin() :1
it!=my_vec.begin() :2
it!=my_vec.begin() :4
it!=my_vec.begin() :8
it!=my_vec.begin() :16
it!=my_vec.begin() :32
it!=my_vec.begin() :64
it!=my_vec.begin() :128
it!=my_vec.begin() :256
it!=my_vec.begin() :512
it!=my_vec.begin() :1024
it!=my_vec.begin() :2048
it!=my_vec.begin() :4096
it!=my_vec.begin() :8192
it!=my_vec.begin() :16384

- Helvio Hild