c ++ Vector，当它在堆栈上扩展/重新分配时会发生什么？ [英] c++ Vector, what happens whenever it expands/reallocate on stack?

问题描述

我是C ++的新手，我在我的项目中使用向量类。我发现它非常有用，因为我可以有一个数组，每当有必要时自动重新分配（即，如果我想push_back一个项目和向量已达到其最大容量，它重新分配自己要求更多的内存空间到操作系统），所以，访问一个元素的向量是非常快的（它不像一个列表，到达第n元素，我必须通过n第一个元素）。

我发现此问题非常实用，因为他们的答案解释了当我想在堆/堆栈上存储我的向量时内存分配器的工作原理：

  [1] vector< Type> vect; 
 [2] vector< Type> * vect =新向量< Type> ;; 
 [3] vector< Type *> vect; 
  

但是，有一个疑问是我错了一段时间，我找不到答案：
每当我构造一个向量并开始推动很多的项目时，它会达到一个时刻，当向量将是满的，所以要继续增长它将需要重新分配，将自己复制到新的位置，然后继续推push_back项目（显然，这个重新分配它隐藏在类的实现，所以它是完全透明给我）

很好，如果我在堆上创建了向量[2]，我没有麻烦想象发生了什么：类向量调用malloc，获取新的空间，然后将自己复制到新的内存，最后删除旧的内存调用。

然而，面纱隐藏了在在堆栈上构造向量时发生的情况 [1]：当向量必须重新分配？ AFAIK，每当在C / C ++上输入一个新函数时，计算机将查看变量声明，然后展开堆栈以获得放置这些变量所需的空间，但不能分配当函数已经运行时在堆栈上有更多的空间。

解决方案

>

[...]

$ b

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

我的答案应该让你想到一个向量是如何设计的。

常见的std :: vector布局*

注意： std :: allocator 实际上可能是一个空类，而 std :: vector 可能不包含此类的实例。这可能不适用于任意分配器。

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

• begin 指向堆上向量的数据存储器的起始位置（如果不是 nullptr ）


• end 指向一个内存位置超过向量数据的最后一个元素
  - > size（）== end-begin


• capacity 向量存储器的最后一个元素 - > capacity（）== capacity-begin

堆栈上的向量

我们声明一个 std :: vector 其中 T 是任何类型， A 是 T （即 std :: allocator< T> ）。

  std :: vector< T，A> vect1; 
  

这在内存中如何？

我们看到：堆上没有发生任何事情，但是变量占用了堆栈中所有成员所需的内存。
它是，它会保留在那里，直到 vect1 超出范围，因为 vect1 只是一个对象类型 double ， int 或任何其他对象。

的指针将会被放置在堆栈位置，

堆上的向量

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

  std ::向量< T，A> * vp = new std :: vector< T，A>让我们再次查看内存。
 
 
 
  
 >  
 
 
 
在堆栈上有我们的vp变量，我们的向量现在在堆上。同样，向量本身不会在堆上移动，因为它的大小是不变的。只有指针（ begin ， end ， capacity ）如果发生重新分配，则移动以跟随存储器中的数据位置。让我们看看这个。
 
 
 
将元素推送到向量
 
 
 
现在我们可以开始将元素推入向量。让我们看看 vect1 。
  
 vect1.push_back（a）; 
  
  
 
 
 
变量 vect1 堆上的内存被分配为包含 T 的一个元素。
 
 
 
如果我们添加一个元素，会发生什么？ 
  vect1.push_back（a）; 
  
  
 
 
 
 
 
在数据元素的堆上分配的空间将不够
 
 
将为两个元素分配一个新的内存块
 
 
第一个元素将被复制/移动
 
 
 
 
 
我们可以看到：The new memory will be deallocated。新的内存位置是不同的。
 
 
 
要有额外的洞察力，让我们看看如果我们破坏最后一个元素的情况。
  vect1.pop_back（）; 
  
分配的内存将不会改变，但最后一个元素将调用其析构函数，一个位置向下。
 
 
 
  
 
 
 
如你所见： capacity（）== capacity-begin == 2  while  size（）== end-begin == 1  
 
I'm new to C++ and I'm  using the vector class on my project. I found it quite useful because I can have an array that automatically reallocates whenever it is necessary (ie, if I want to push_back an item and the vector has reached it's maximum capacity, it reallocates itself asking more memory space to the OS), so access to an element of the vector is very quick (it's not like a list, that to reach the "n-th" element I must go through the "n" first elements).

I found this question very useful, because their answers explained perfectly how the "memory allocator" works when I want to store my vector on the heap/stack:
[1] vector<Type> vect;
[2] vector<Type> *vect = new vector<Type>;
[3] vector<Type*> vect;
However, a doubt is bugging me for a while, and I can't find its answer:
Whenever I construct a vector and begin pushing a lot of items in, it would reach a moment when the vector would be full, so to continue growing it would need to reallocate, copy itself to a new location and then continue pushing_back items (obviously, this reallocation it's hidden on the implementation of the  class, so it is completely transparent to me)

Fine, if I have created the vector on the heap [2], I have no troubles imagining what may be happening: class vector calls malloc, acquires new space and then copy itself into the new memory and finally deletes the old memory calling free.

However, a veil hides what is happening when I construct a vector on the stack [1]: What does it happens when the vector must reallocate? AFAIK, whenever on C/C++ you enter a new function, the computer would look at the declaration of variables and then expand the stack to get the necessary space to put these variables, but you can't allocate more space on the stack when the function is already running. How does the class vector solve this problem?
解决方案
You wrote 

  
[...] copy itself to a new location [...]
which is not the way a vector works. The vector data is copied to a new location, not the vector itself.

My answer should give you an idea of how a vector is designed.

The common std::vector layout*

Note: The std::allocator is actually likely to be an empty class and std::vector will probably not contain an instance of this class. This may not be true for an arbitrary allocator.



In most implementations it consists of three pointers where


begin points to the start of the data memory of the vector on the heap (always on the heap if not nullptr)
end points one memory location past the last element of the vector data 
-> size() == end-begin
capacity points on memory location past the last element of the vector memory -> capacity() == capacity-begin


A vector on the stack

We declare a variable of type std::vector<T,A> where T is any type and A is an allocator type for T (i.e. std::allocator<T>).
std::vector<T, A> vect1;
How does this look like in memory?



As we see: Nothing happens on the heap but the variable occupies the memory that is necessary for all of its members on the stack.
There it is and it will stay there until vect1 goes out of scope, since vect1 is just an object like any other object of type double, int or whatever. It will sit there on its stack position and wait to get destroyed, regardless of how much memory it handles itself on the heap.

The pointers of vect1 do not point anywhere, since the vector is empty.

A vector on the heap

Now we need a pointer to a vector and use some dynamic heap allocation to create the vector.
std::vector<T, A> * vp = new std::vector<T, A>;
Let's again look at the memory.



We have our vp variable on the stack and our vector is on the heap now. Again the vector itself will not move on the heap since its size is constant. Only the pointers (begin, end, capacity) will move to follow the data position in memory if a reallocation takes place. Let's have a look at that.

Pushing elements to a vector

Now we can start pushing elements to a vector. Let's look at vect1.
T a;
vect1.push_back(a);


The variable vect1 is still where it has been but memory on the heap was allocated to contain one element of T.

What happens if we add one further element?
vect1.push_back(a);



The space allocated on the heap for the data elements will not be enough (since it is only one memory positions, yet).
A new memory block will be allocated for two elements 
The first element will be copied/moved to the new storage.
The old memory will be deallocated.


We see: The new memory location is different.

To have additional insight let's look at the situation if we destroy the last element.
vect1.pop_back();
The memory allocated won't change but the last element will have its destructor called and the end pointer moves one position down.



As you can see: capacity() == capacity-begin == 2 while size() == end-begin == 1

                        
这篇关于c ++ Vector，当它在堆栈上扩展/重新分配时会发生什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！