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

我是新来的C + +,我在我的项目上使用vector类。 我发现它非常有用,因为我可以有一个数组,在必要时自动重新分配(例如,如果我想push_back一个项目,并且vector已经达到了最大容量,它会重新分配自己,向操作系统请求更多的内存空间)访问vector的元素非常快(它不像列表,为了达到“第n个”元素,我必须通过“n”个第一个元素)。

我发现这个问题非常有用,因为他们的答案完美地解释了“内存分配器”是如何工作的,当我想把我的vector存储在堆/栈上时:

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

然而,有一个疑问是困扰我一段时间,我无法find答案:每当我构build一个向量,并开始推入大量的项目,它会达到vector将满的一刻,所以继续增长它将需要重新分配,复制自己到一个新的位置,然后继续push_back项目(显然,这个重新分配它隐藏在类的实现,所以它是完全透明的我)

好的,如果我已经在堆上创build了这个向量[2],我不会想象会发生什么事情:类向量调用malloc,获取新的空间,然后将自身复制到新的内存中,最后删除自由调用的旧内存。

然而,当我在栈上构造一个向量时,面纱隐藏了发生的事情:当向量必须重新分配时,会发生什么? AFAIK,无论何时在C / C ++中input一个新的函数,计算机都会查看variables的声明,然后展开堆栈以获得必要的空间来放置这些variables,但是在堆栈中不能分配更多的空间function已经在运行。 类vector如何解决这个问题?

你写了

[…]复制到一个新的位置

这不是一个vector的工作方式。 vector数据被复制到一个新的位置,而不是vector本身。

我的答案应该给你一个如何devise一个载体的想法。

常见的std :: vector布局*

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

std ::矢量布局

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

  • begin指向堆上的向量的数据存储器的开始(如果不是nullptr总是在堆上)
  • end点指向vector数据最后一个元素的一个内存位置 – > size() == end-begin
  • 通过向量内存的最后一个元素的内存位置上的capacity点 – > capacity() == capacity-begin

在堆栈上的vector

我们声明了std::vector<T,A>types的variables,其中T是任何types, AT的分配器types(即std::allocator<T> )。

 std::vector<T, A> vect1; 

这在内存中是怎样的?

std :: vector在堆栈上

正如我们所看到的:堆上没有任何事情发生,但variables占用了堆栈中所有成员所需的内存。 在那里,它会留在那里,直到vect1超出范围,因为vect1只是像任何其他types的对象typesdoubleint或其他。 它会坐在堆栈的位置,并等待被破坏,而不pipe它在堆上处理多less内存。

vect1的指针不指向任何地方,因为vector是空的。

在堆上的vector

现在我们需要一个指向vector的指针,并使用一些dynamic堆分配来创buildvector。

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

我们再来看看内存。

std ::堆上的矢量

我们有我们的vpvariables在堆栈上,我们的vector现在在堆上。 同样的vector本身不会在堆上移动,因为它的大小是不变的。 如果重新分配,只有指针( beginendcapacity )才会跟随内存中的数据位置。 我们来看看这个。

将元素推送到vector

现在我们可以开始将元素推向一个向量。 我们来看看vect1

 T a; vect1.push_back(a); 

单个push_back之后的std :: vector

variablesvect1仍然存在,但堆中的内存被分配以包含T一个元素。

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

 vect1.push_back(a); 

第二次推后std :: vector

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

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

如果我们摧毁最后一个元素,让我们来看看情况。

 vect1.pop_back(); 

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

std :: vector在2x推送和1x流行音乐之后

正如你所看到的: capacity() == capacity-begin == 2 size() == end-begin == 1

vector对象可以在堆栈中进行初始化,但vector中的数据将在堆上。

(普通的类class foo {int* data;};具有这个特性)

你构build你的vector(堆栈或堆)的方式并不重要。

请参阅std::vector的文档

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

当vector“增长”时,vector对象不会增长,只有内部dynamic数组发生变化。

至于它的实现,你可以看看GCC的vector实现。

为了简单_Vector_impl ,它将向量声明为带有一个 _Vector_impltypes的受保护成员的类。

正如你所看到的,它被声明为一个包含三个指针的结构:

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

你基本上是问一个vector的实现细节。 C ++标准没有定义如何实现一个vector – 它只是定义了一个vector应该做什么以及需要实现哪些操作。 没有人能100%准确地告诉你当一个vector被重新分配时会发生什么,因为每个编译器在理论上是不同的。

这就是说,了解一个vector是如何实现的并不难。 vector本身就是一个简单的数据结构,它具有指向存储在vector的实际数据的指针。 沿着这些线路的东西:

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

以上显然是psudocode,但你明白了。 在堆栈上(或在堆上)分配vector

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

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

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

当你push_back到一个完整的向量时,数据将被重新分配:

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

…vector指向新数据的指针现在将指向那里。

你也可以保留预期的大小,

 vect.reserve(10000); 

这将保留所使用types的10000个对象空间

一个向量不是一个元素的数组,或者是用来存储这些元素的内存。

一个向量pipe理一个元素数组,它分配的内存,取消分配,缩小和增长的需要。

你select如何分配vector本身与vector自己决定如何以及在哪里分配它为你pipe理的内存无关

我不想阻止你对这个向量在内部是如何工作的兴趣(这既有趣又有用),但是编写类和logging它们的关键在于你只需要理解接口而不是实现。