网站公告 | 泰斗网校全新上线了,可以和论坛用户登录同步,如果遇到登录问题联系管理员解决
查看: 3598|回复: 10
收起左侧

[Wahh] 【浅谈C++】2.C++ STL容器的内存分配

[复制链接]

[Wahh] 【浅谈C++】2.C++ STL容器的内存分配[复制链接]

Wahh_1314 发表于 2017-9-14 10:24:08 [显示全部楼层] 回帖奖励 |倒序浏览 |阅读模式 回复:  10 浏览:  3598
本帖最后由 Wahh_1314 于 2017-9-14 10:24 编辑

一. 前言

这是C++系列文章的第二篇,主要讲解的是STL底层部分的内容,如果平时你经常用STL,但却没有深入了解,那么这篇文章让你对STL有全新认识。


二.正题:(ps : 阅读以下文章请先了解 : C++基本语法、STL、 模板 )


a.前言
在使用STL各类容器的时候,有时会出现迭代器失效,引用(指针)失效等情况的而发生,即使看似你的操作都是合法的情况下。
要了解问题的原因,我们就要了解C++中stl容器的内存分配策略。我们才知道在哪些操作下可能导致迭代器失效,引用(指针)失效。

b.问题分类
首先我们把以上的问题分成两类:
  • 容器的迭代器为什么会失效?
  • 容器元素的引用(指针)为什么会失效?
因为从内存角度上来讲,如果引用是失效了那么指针也就是失效了,也就是容器的该元素从这个内存地址搬家了!

c.第一类问题分析
问题: 容器的迭代器为什么会失效?
对于上面的问题我们可以换个说法:容器的元素在容器内部搬家了
我们可以把容器看做是一个小镇,有一个个的房子(无论是list,vector还是其他的,只是房子之间的联系关系不同。不过这不在我们目前考虑范围);
而元素就是相当于住在房子里面的人。
现在,假如小镇又搬进来一户人家。小镇自然需要为这户人家安排一户房子:
  • 假如是空房子还好(只需要住进去就行);
  • 如果新来的这户人家看中了已经居住的某户人家的房子,那么肯定需要之前那户人家搬出来,然后才能进去住。而某些容器中为了保证数据的顺序一致性,就会出现下面的情况:

很显然,如果出现了以上图片所示的情况,那么就相当于容器的元素在容器内部搬家了,因为或多或少的造成了其他元素搬家。
而迭代器相当于什么呢?恩,我们可以在这里把它当做是房子的门牌号(每个房子的门牌号都不一样)。
以前我们知道通过一户人家的门牌号就可以很容易找到这户人家。但是,如果该户人家搬家了呢?
对,正是这样的”搬家”导致容器的迭代器失效。
问题原因找出来了,我们下面就来总结一下,各类容器发生迭代器失效的情况:

可以看出来非线性表的适应性是最好的,因为不需要内存地址连续。
而线性表中,不适宜的插入删除位置会使得迭代器失效。(使得迭代器失效还有一种情况:容器存储空间的重新分配,我们后面来讲)
下面我来举个例子:
给定一个容器 vector< int >vi,删除容器中所有为3的元素。
下面是两个版本的代码:
代码1:
[C++] 纯文本查看 复制代码
for(auto it = vi.begin();it != vi.end();)
{
    if(*it == 3) it = vi.erase(it);
    else it ++;
}
代码2:
[C++] 纯文本查看 复制代码
auto end = vi.end();
for(auto it = vi.begin();it != end;)
{
    if(*it == 3) it = vi.erase(it);
    else it ++;
}
可能代码2的作者是考虑到每次循环都需要调用vi.end()的开销,于是就在循环外记录了尾后迭代器。
然而在上面的代码中。由于在循环内部可能会调用erase的函数;也就是说一旦发生删除,那么尾后迭代器就会失效。所以代码2是错误的!!
不过还有个地方值得注意:删除erase的时候会使得it迭代器失效,所以需要用it来接受erase函数的返回值。

d.第二类问题分析
问题: 容器元素的引用或指针为什么会失效?
这个问题就是涉及到了不同容器中如何去管理内存的。以下用 vector(string) 和 deque 来举例。
  • vector(string 可看做vector< char >)
    为了支持快速随机访问,vector只能将元素连续存储——每个元素紧挨着前一个元素存储。然而当我们向vector 或者string添加元素的时候;如果没有空间容纳新元素,容器不可能简单地把它添加在内存的其他位置——因为元素必须连续存储。容器就必须重新分配新的内存空间来保存已有的元素和新元素,将旧元素移动到新空间,然后添加新的元素。
  • deque
    deque看似和vector很相似,但是 deque 能高效的在首位进行元素的插入删除;并且 deque 也支持随机访问;说明 deque 的内部内存实现要比vector复杂得多。事实上 deque 采用的是动态内存块的策略,块的内部是一段连续的内存,但是块与块之间物理内存不一定连续。
    deque的元素数据采用分块的线性结构进行存储,如图所示。deque分成若干线性存储块,称为deque块。块的大小一般为512个字节,元素的数据类型所占用的字节数,决定了每个deque块可容纳的元素个数。
    所有的deque块使用一个Map块进行管理,每个Map数据项记录各个deque块的首地址。Map是deque的中心部件,将先于deque块,依照deque元素的个数计算出deque块数,作为Map块的数据项数,创建出Map块。以后,每创建一个deque块,都将deque块的首地址存入Map的相应数据项中。
    在Map和deque块的结构之下,deque使用了两个迭代器M_start和M_finish,对首个deque块和末deque块进行控制访问。迭代器iterator共有4个变量域,包括M_first、M_last、M_cur和M_node。M_node存放当前deque块的Map数据项地址,M_first和M_last分别存放该deque块的首尾元素的地址(M_last实际存放的是deque块的末尾字节的地址),M_cur则存放当前访问的deque双端队列的元素地址。

简单介绍了 vector 和 deque 的内存管理策略之后;我们知道,如果当容器中进行了内存重新分配。那么元素的物理存储地址必然改变,所以这就是导致引用和指针失效的原因!!
我们下面就来总结一下,各类容器发生引用(指针)失效的情况:

e.后话
值得注意的是,不同的编译器对于stl内存管理策略可能略有差别。下面拿 vector 举例:
我们知道 vector 的内存管理策略是:当push_back的时候发现容量不够存储新的元素就需要去开辟一个更大的内存,然后将旧元素复制过去,然后再加入新元素。
那么有个问题是:当容量不够的时候需要开辟一个多大的内存呢?这个实现机制在不同的编译器中就可能有不同。
目前我见过有三个版本的:
  • VS2013自带G++编译器 : 每次开辟新内存比原来多一个元素内存。
  • VS2010自带G++编译器: 每次开闭新内存比原来容量多一半。(*150%)
  • CodeBlocks自带GCC编译器: 每次开辟新内存为原来容量的一倍。(*200%)
不管开辟内存的策略如何,总需要满足一个定则:
在一个初始化为空的 vector 上调用n次push_back来创建一个n个元素的vector,所花费时间不能超过n的常数倍。
还有一个值得注意的地方就是:
对于vector的 pop_back 或者 erase ,clear 只会减小容器的元素个数,并不会减少容器的容量。resize也是一样,如果小于size。只会使得容器元素个数减小,容器的容量不会减小。
换句话来说,一个vector容器对象容量是只增不减的。只会在析构函数的时候对占用内存进行释放。
当然以上问题也不是不可以解决的:
使用swap函数可以使得两个vector对象内部元素甚至所占内存空间都互换。
比如想释放vector< int > vt 占用的内存:

  • 清空所有元素,释放所有容量
    vector<int>
    ().swap(vt);

  • 元素不改变,释放多余的容量
    vector<int>
    (vt).swap(vt);

从第二段代码我们也可以得知,vector 的拷贝构造函数只是会将元素拷贝过来,而容量也只是会初始化为和元素个数一样。
还值得注意的一个地方是:
如果会需要向一个vector中插入很多记录,比如说100000条,为了避免在插入过程中移动内存,咱实现向系统预订一段足够的连续的空间,例如:
a.reserve(100000)

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

评分

参与人数 1泰斗币 +8 收起 理由
泰课_robin + 8 很给力!

查看全部评分

+1
3601°C
10
  • 泰课_robin
  • suifengm2015
  • gzjsoft
  • Liangzz
  • 梦幻星移
过: 他们
因分享而快乐,学习以自强!
泰课_robin 发表于 2017-9-14 11:47:23 显示全部楼层
不错的分享
因分享而快乐,学习以自强!
suifengm2015 发表于 2017-9-16 15:21:57 显示全部楼层
很基础,对初学者还是有很多帮助的
因分享而快乐,学习以自强!
gzjsoft 发表于 2017-9-17 03:31:44 显示全部楼层
很给力的干货
因分享而快乐,学习以自强!
Liangzz 发表于 2017-9-17 15:41:30 显示全部楼层
来学习的,点个赞
因分享而快乐,学习以自强!
梦幻星移 发表于 2017-9-18 02:31:52 显示全部楼层
我来加个温支持一下
因分享而快乐,学习以自强!
feelbug 发表于 2017-9-18 13:22:13 显示全部楼层
给力,我来学习了
因分享而快乐,学习以自强!
jacob 发表于 2017-9-18 19:12:14 显示全部楼层
涨姿势了~~~
因分享而快乐,学习以自强!
甲壳虫 发表于 2017-9-19 01:02:14 显示全部楼层
多谢大佬,学习下
因分享而快乐,学习以自强!
AlbertWong0610 发表于 2017-11-25 11:58:40 显示全部楼层
收藏了,慢慢学习
因分享而快乐,学习以自强!
kingtopchina 发表于 2018-8-15 10:47:18 显示全部楼层
好帖子,分析的很透彻!
因分享而快乐,学习以自强!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

VR/AR版块|Unity3d|Unreal4|新手报道|小黑屋|站点地图|沪ICP备14023207号-9|【泰斗社区】-专注互联网游戏和应用的开发者平台 ( 浙ICP 备 13006852号-15 )|网站地图

© 2001-2013 Comsenz Inc.  Powered by Discuz! X3.4

1
QQ