c ++ Vector,每当它在堆栈上扩展/重新分配时会发生什么？

Question

我是C++的新手,我在项目中使用了矢量类.我发现它非常有用,因为我可以有一个数组,只要有必要就会自动重新分配(例如,如果我想推送一个项目并且向量已达到它的最大容量,它会重新分配自己,为操作系统提供更多的内存空间),所以对向量元素的访问非常快(它不像列表,要达到"第n"元素,我必须通过"n"个第一个元素).

我发现这个问题非常有用,因为当我想将我的向量存储在堆/堆栈上时,他们的答案完全解释了"内存分配器"是如何工作的:

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

然而,怀疑是困扰我一段时间,我找不到它的答案:每当我构建一个向量并开始推入大量项目时,它将达到向量将满的时刻,因此继续增长它需要重新分配,将自身复制到一个新位置,然后继续push_back项(显然,这个重新分配它隐藏在类的实现上,所以它对我来说是完全透明的)

好吧,如果我在堆上创建了向量[2],我没有想象可能发生的事情:类向量调用malloc,获取新空间然后将自身复制到新内存中,最后删除调用free的旧内存.

然而,当我在堆栈上构造一个向量时,面纱会隐藏正在发生的事情[1]:当向量必须重新分配时会发生什么？AFAIK,无论何时在C/C++上输入一个新函数,计算机都会查看变量声明,然后展开堆栈以获得放置这些变量所需的空间,但是当你在堆栈中分配更多空间时功能已在运行.类向量如何解决这个问题？

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(ie std::allocator<T>)的分配器类型.

std::vector<T, A> vect1;

这在内存中看起来如何？

我们看到:堆上没有任何事情发生,但变量占用了堆栈上所有成员所需的内存.在那里,它会一直存在,直到vect1超出范围,因为vect1它只是一个像任何其他类型的对象double,int或任何其他对象.它将位于其堆栈位置并等待被破坏,无论它在堆上处理多少内存.

指针vect1不指向任何地方,因为向量是空的.

在堆的传染媒介

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

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

让我们再看看记忆.

我们在堆栈上有我们的vp变量,我们的vector现在在堆上.同样,向量本身不会在堆上移动,因为它的大小是常量.只有指针(begin,end,capacity)将移动到跟随在内存中的数据位置,如果重新分配发生.我们来看看.

将元素推向矢量

现在我们可以开始将元素推送到向量.我们来看看吧vect1.

T a;
vect1.push_back(a);

该变量vect1仍然存在,但堆上的内存被分配为包含一个元素T.

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

vect1.push_back(a);

• 在堆上为数据元素分配的空间是不够的(因为它只是一个内存位置).
• 将为两个元素分配新的内存块
• 第一个元素将被复制/移动到新存储.
• 旧的内存将被释放.

我们看到:新的内存位置不同.

为了获得额外的洞察力,让我们看一下如果我们销毁最后一个元素的情况.

vect1.pop_back();

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

如你所见:capacity() == capacity-begin == 2whilesize() == end-begin == 1

Answer 2

矢量对象很可能在堆栈中被实现,但向量中的数据将在堆上.

(琐碎的班级class foo {int* data;};有这个特点)

Answer 3

构造向量(堆栈或堆)的方式对此无关紧要.

请参阅文档 std::vector

在内部,向量使用动态分配的数组来存储它们的元素.可能需要重新分配此数组,以便在插入新元素时增大大小,这意味着分配新数组并将所有元素移动到该数组.

当矢量"增长"时,矢量对象不会增长,只有内部动态数组会发生变化.

至于它的实现,你可以看看GCC的矢量实现.

为了简单起见,它将vector声明为一个具有一个受保护成员类的类_Vector_impl.

如您所见,它被声明为包含三个指针的结构:

• 一个指向存储开始(和数据的开头)
• 一个指向数据末尾的
• 一个用于存储结束