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

本文介绍了c ++ Vector,每当它在堆栈上扩展/重新分配时会发生什么?的处理方法,对大家解决问题具有一定的参考价值

问题描述

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

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;

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

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)

好吧,如果我在堆上创建了向量 [2],我可以想象会发生什么:类向量调用 malloc,获取新空间,然后将自身复制到新内存中,最后删除旧内存免费通话.

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.

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

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?

推荐答案

你写的

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

[...] 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.

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

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 指向堆上向量的数据内存的开始(如果不是nullptr,则始终在堆上)
  • end 指向向量数据最后一个元素之后的一个内存位置-> size() == end-begin
  • capacity 指向向量内存最后一个元素后的内存位置 -> capacity() == capacity-begin
  • 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

我们声明一个 std::vector 类型的变量,其中 T 是任意类型,A 是分配器类型对于T(即std::allocator).

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?

如我们所见:堆上什么都没有发生,但变量占用了堆栈上所有成员所需的内存.它就在那里,它会一直留在那里直到 vect1 超出范围,因为 vect1 只是一个对象,就像任何其他 double 类型的对象一样,int 之类的.不管它在堆上处理多少内存,它都会坐在它的堆栈位置上等待被销毁.

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.

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

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

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

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>;

让我们再看看内存.

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

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.

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

Now we can start pushing elements to a vector. Let's look at vect1.

T a;
vect1.push_back(a);

变量 vect1 仍在原来的位置,但堆上的内存被分配以包含 T 的一个元素.

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);

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

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

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.

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

这篇关于c ++ Vector,每当它在堆栈上扩展/重新分配时会发生什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,WP2

admin_action_{$_REQUEST[‘action’]}

do_action( "admin_action_{$_REQUEST[‘action’]}" )动作钩子::在发送“Action”请求变量时激发。Action Hook: Fires when an ‘action’ request variable is sent.目录锚点:#说明#源码说明(Description)钩子名称的动态部分$_REQUEST['action']引用从GET或POST请求派生的操作。源码(Source)更新版本源码位置使用被使用2.6.0 wp-admin/admin.php:...

日期:2020-09-02 17:44:16 浏览:1127

admin_footer-{$GLOBALS[‘hook_suffix’]}

do_action( "admin_footer-{$GLOBALS[‘hook_suffix’]}", string $hook_suffix )操作挂钩:在默认页脚脚本之后打印脚本或数据。Action Hook: Print scripts or data after the default footer scripts.目录锚点:#说明#参数#源码说明(Description)钩子名的动态部分,$GLOBALS['hook_suffix']引用当前页的全局钩子后缀。参数(Parameters)参数类...

日期:2020-09-02 17:44:20 浏览:1032

customize_save_{$this->id_data[‘base’]}

do_action( "customize_save_{$this-&gt;id_data[‘base’]}", WP_Customize_Setting $this )动作钩子::在调用WP_Customize_Setting::save()方法时激发。Action Hook: Fires when the WP_Customize_Setting::save() method is called.目录锚点:#说明#参数#源码说明(Description)钩子名称的动态部分,$this->id_data...

日期:2020-08-15 15:47:24 浏览:775

customize_value_{$this->id_data[‘base’]}

apply_filters( "customize_value_{$this-&gt;id_data[‘base’]}", mixed $default )过滤器::过滤未作为主题模式或选项处理的自定义设置值。Filter Hook: Filter a Customize setting value not handled as a theme_mod or option.目录锚点:#说明#参数#源码说明(Description)钩子名称的动态部分,$this->id_date['base'],指的是设置...

日期:2020-08-15 15:47:24 浏览:866

get_comment_author_url

过滤钩子:过滤评论作者的URL。Filter Hook: Filters the comment author’s URL.目录锚点:#源码源码(Source)更新版本源码位置使用被使用 wp-includes/comment-template.php:32610...

日期:2020-08-10 23:06:14 浏览:903

network_admin_edit_{$_GET[‘action’]}

do_action( "network_admin_edit_{$_GET[‘action’]}" )操作挂钩:启动请求的处理程序操作。Action Hook: Fires the requested handler action.目录锚点:#说明#源码说明(Description)钩子名称的动态部分$u GET['action']引用请求的操作的名称。源码(Source)更新版本源码位置使用被使用3.1.0 wp-admin/network/edit.php:3600...

日期:2020-08-02 09:56:09 浏览:848

network_sites_updated_message_{$_GET[‘updated’]}

apply_filters( "network_sites_updated_message_{$_GET[‘updated’]}", string $msg )筛选器挂钩:在网络管理中筛选特定的非默认站点更新消息。Filter Hook: Filters a specific, non-default site-updated message in the Network admin.目录锚点:#说明#参数#源码说明(Description)钩子名称的动态部分$_GET['updated']引用了非默认的...

日期:2020-08-02 09:56:03 浏览:834

pre_wp_is_site_initialized

过滤器::过滤在访问数据库之前是否初始化站点的检查。Filter Hook: Filters the check for whether a site is initialized before the database is accessed.目录锚点:#源码源码(Source)更新版本源码位置使用被使用 wp-includes/ms-site.php:93910...

日期:2020-07-29 10:15:38 浏览:809

WordPress 的SEO 教学:如何在网站中加入关键字(Meta Keywords)与Meta 描述(Meta Description)?

你想在WordPress 中添加关键字和meta 描述吗?关键字和meta 描述使你能够提高网站的SEO。在本文中,我们将向你展示如何在WordPress 中正确添加关键字和meta 描述。为什么要在WordPress 中添加关键字和Meta 描述?关键字和说明让搜寻引擎更了解您的帖子和页面的内容。关键词是人们寻找您发布的内容时,可能会搜索的重要词语或片语。而Meta Description则是对你的页面和文章的简要描述。如果你想要了解更多关于中继标签的资讯,可以参考Google的说明。Meta 关键字和描...

日期:2020-10-03 21:18:25 浏览:1619

谷歌的SEO是什么

SEO (Search Engine Optimization)中文是搜寻引擎最佳化,意思近于「关键字自然排序」、「网站排名优化」。简言之,SEO是以搜索引擎(如Google、Bing)为曝光媒体的行销手法。例如搜寻「wordpress教学」,会看到本站的「WordPress教学:12个课程…」排行Google第一:关键字:wordpress教学、wordpress课程…若搜寻「网站架设」,则会看到另一个网页排名第1:关键字:网站架设、架站…以上两个网页,每月从搜寻引擎导入自然流量,达2万4千:每月「有机搜...

日期:2020-10-30 17:23:57 浏览:1262