vector内存管理机制,vector存储性能和特性

　　一些好的公司校园招聘过程中（包括笔试、面试环节),经常会涉及到标准模板库中矢量的使用（主要是笔试)及其性能（面试)的分析。今天看了下相关文章，也写了几个小的测试程序跑了跑。算是总结下，希望对需要的人有帮助。

　　关于向量，简单地讲就是一个动态数组，里面有一个指针指向一片连续的内存空间，当空间不够装下数据时会自动申请另一片更大的空间，然后把原有数据拷贝过去，接着释放原来的那片空间；当释放或者说是删除里面的数据时，其存储空间并不会释放，仅仅只是清空了里面的数据。接下来，我会详细地说说这些。

　　备注：本文的相关程序都是在windows 7 VS2008环境下测试。

　　一、首先，看看矢量的内存分配机制：

　　向量内部数组

　　流wf( 1。txt’)；

　　for(int I=0；我我)

　　arr.push_back一);

　　wf capacity= arr.capacity()，size= arr。size()end；

　　wf。close()；

　　容量()返回的是当前矢量对象缓冲区（后面的对矢量维护的内存空间皆称为缓冲区)实际申请的空间大小，而大小()返回的是当前对象缓冲区中存储数据的个数，容量永远是大于等于大小的，当大小和容量相等时继续添加数据时矢量会扩容。

　　再来看看1.txt中的数据：

　　容量=1,大小=1

　　容量=2,大小=2

　　容量=3,大小=3

　　容量=4,大小=4

　　容量=6,大小=5

　　容量=6,大小=6

　　容量=9,大小=7

　　容量=9,大小=8

　　容量=9,大小=9

　　容量=13,大小=10

　　容量=13,大小=11

　　容量=13,大小=12

　　容量=13,大小=13

　　容量=19,大小=14

　　容量=19,大小=15

　　容量=19,大小=16

　　容量=19,大小=17

　　容量=19,大小=18

　　容量=19,大小=19

　　容量=28,尺寸=20

　　容量=28,尺寸=21

　　容量=28,尺寸=22

　　容量=28,大小=23

　　容量=28,尺寸=24

　　容量=28,尺寸=25

　　容量=28,尺寸=26

　　容量=28,大小=27

　　容量=28,大小=28

　　容量=42,尺寸=29

　　容量=42,尺寸=30

　　容量=42,尺寸=31

　　容量=42,尺寸=32

　　容量=42,尺寸=33

　　容量=42,尺寸=34

　　容量=42,尺寸=35

　　容量=42,尺寸=36

　　容量=42,尺寸=37

　　容量=42,尺寸=38

　　容量=42,尺寸=39

　　容量=42,尺寸=40

　　容量=42,尺寸=41

　　容量=42,大小=42

　　容量=63,大小=43

　　容量=63,尺寸=44

　　容量=63,尺寸=45

　　容量=63,尺寸=46

　　容量=63,尺寸=47

　　容量=63,尺寸=48

　　容量=63,尺寸=49

　　容量=63,尺寸=50

　　容量=63,尺寸=51

　　容量=63,尺寸=52

　　容量=63,大小=53

　　容量=63,尺寸=54

　　容量=63,尺寸=55

　　容量=63,尺寸=56

　　容量=63,尺寸=57

　　容量=63,尺寸=58

　　容量=63,尺寸=59

　　容量=63,尺寸=60

　　容量=63,大小=61

　　容量=63,大小=62

　　容量=63,大小=63

　　容量=94,大小=64

　　容量=94,尺寸=65

　　容量=94,尺寸=66

　　容量=94,尺寸=67

　　容量=94,尺寸=68

　　容量=94,尺寸=69

　　容量=94,尺寸=70

　　容量=94,尺寸=71

　　容量=94,尺寸=72

　　容量=94,尺寸=73

　　容量=94,大小=74

　　容量=94,尺寸=75

　　容量=94,尺寸=76

　　容量=94,尺寸=77

　　容量=94,尺寸=78

　　容量=94,尺寸=79

　　容量=94,大小=80

　　容量=94,大小=81

　　容量=94,大小=82

　　容量=94,大小=83

　　容量=94,大小=84

　　容量=94,大小=85

　　容量=94,大小=86

　　容量=94,大小=87

　　容量=94,尺寸=88

　　容量=94,尺寸=89

　　容量=94,大小=90

　　容量=94,大小=91

　　容量=94,大小=92

　　容量=94,大小=93

　　容量=94,大小=94

　　容量=141,尺寸=95

　　容量=141,尺寸=96

　　容量=141,尺寸=97

　　容量=141,尺寸=98

　　容量=141,尺寸=99

　　容量=141,大小=100

　　数据有点多，提炼下就是这样的：

　　容量=1

　　容量=2

　　容量=3

　　容量=4

　　容量=6

　　容量=9

　　容量=13

　　容量=19

　　容量=28

　　容量=42

　　容量=63

　　容量=94

　　容量=141

　　看出其中的规律没？对，就是每次扩容都是增加当前空间的50%(第一次除外);

　　9 9/2=13;13 13/2=19;19 19/2=28……

　　其实我们都能看到STL的源代码，具体在你说安装的编译器目录里。比如我的VS2008在：安装目录\VC\include下。也可以直接在VS中选择#include vector，右键打开。当然windows上的STL源代码是P.J. Plauger写的(PS:优秀的B博士，百度你懂的)。大家都说可读性极强，我也这么认为。我们这些菜鸟还不如看GCC里的STL源代码。

　　\VC\include\vector是这样展开的：

　　If (_Count==0)//这里做一个判断，但是什么都不做。我想知道为什么？

　　else if(max _ size()-size()_ count)//编译器能申请的最大容量装不下。抛出exception _ throw (length _ error， vector t too long )；

　　_ Xlen()；//结果太长

　　else if(_ capacity size()_ count)//目前空间不够，需要扩展。

　　{ //空间不足，请重新分配

　　_ Capacity=max _ size()-_ Capacity/2 _ Capacity

　　？0:_ Capacity _ Capacity/2；//尝试增长50%，容量扩展50%

　　If (_Capacity size() _Count)//如果扩容50%后容量不够，则使容量等于当前数据号加上新数据号。

　　_ Capacity=size()_ Count；

　　pointer _ new vec=this-_ alval . allocate(_ Capacity)；//申请新的空间

　　pointer _ Ptr=_ Newvec

　　_尝试_开始

　　_Ptr=_Umove(_Myfirst，_VEC_ITER_BASE(_Where)，

　　_ new vec)；//复制前缀//将原数据复制到新内存中。

　　_Ptr=_Ucopy(_First，_Last，_ Ptr)；//add newstuff//将新数据复制到新内存的后面。

　　_ u move(_ VEC _ ITER _基地(_哪里)，_Mylast，_ Ptr)；//复制后缀

　　_CATCH_ALL

　　_Destroy(_Newvec，_ Ptr)；

　　this- _Alval.deallocate(_Newvec，_ Capacity)；//释放最初请求的内存。

　　_ RERAISE

　　_CATCH_END

　　是的，每次都是50%的扩张。至于删除容器中的数据，缓冲区大小不会改变，只知道里面的数据，vector只有在调用析构函数的时候才会自动释放缓冲区。

　　看看它的析构函数代码：

　　~向量()

　　{ //销毁对象

　　_ Tidy()；

　　}

　　void _Tidy()

　　{//释放所有存储空间

　　if (_Myfirst！=0)

　　{//释放、销毁和释放它的东西

　　_Destroy(_Myfirst，_ my last)；//应该是破坏向量中的每一个元素。

　　this-_ alval . deallocate(_ my first，_ Myend-_ my first)；//释放缓冲区空间

　　_Myfirst=0，_Mylast=0，_ Myend=0；//所有指针都重置为零

　　那么，是否可以在需要的时候强行释放缓冲呢？

　　二、如何强行释放vector的缓冲区：

　　答案是肯定的，既然析构的时候会释放空间，那么我们可以换一种方式调用析构函数。

　　////方法1，

　　vector int()。互换(arr)；//交换后

　　//方法二，

　　矢量int temp//临时对象未初始化，缓冲区大小为0，没有数据。

　　arr . swap(temp)；//和我们的对象交换数据，arr的缓冲区就没了。

　　}//临时变量会被析构，temp调用vector析构函数释放空间。

　　三。如何使用它来提高性能：

　　为了比较，我们使用了三种方式将100个数据存储到vector中，即：1。每次直接push _ back()；2.用resize()提前分配100个空格，然后push _ back3.使用reserve预先分配100个存储空间。在MSDN，对这两种功能的描述是：

　　reserve为vector对象保留最小长度的存储，必要时分配空间。

　　size指定向量的新大小。

　　在这里，当我们初始化它时，感觉是相似的。

　　clock _ t start=clock()；

　　for(int num=0；num 10000数字)

　　向量整数

　　for(int I=0；我我)

　　v1 . push _ back(I)；

　　 Cout 直推循环耗时10000次： clock()-start endl；

　　start=时钟()；

　　for(int num=0；num 10000数字)

　　向量整数

　　v2 . resize(100)；

　　for(int I=0；我我)

　　v2 . push _ back(I)；

　　 Cout 先调整预设大小再推循环10000次： clock()-start endl；

　　start=时钟()；

　　for(int num=0；num 10000数字)

　　向量整数

　　v3 .储备(100)；

　　for(int I=0；我我)

　　v3 . push _ back(I)；

　　 Cout 先保留预设大小再推循环10000次： clock()-start endl；

　　但是结果不一样。

　　保留只是保持一个最小的空间大小，而调整大小则是对缓冲区进行重新分配，里面涉及到的判断和内存处理比较多，当然了在这里由于最初都是空的所以差别不大。

　　两者的区别查看：向量：保留和向量：调整大小的区别。

　　由此可见，对于数据数目可以确定的时候，先预设空间大小是很有必要的。直接推回数据频繁移动很是耗时（当然了，数据小的可以忽略的)。

　　真个测试程序的完整代码如下

　　#include stdafx.h

　　#包含btree.h

　　#包含矢量

　　#包括输入输出流

　　#包含Windows.h

　　#包括文件操作

　　#包含时间。h

　　使用STD:of stream；

　　使用STD:cout；

　　使用STD:endl；

　　使用STD:vector；

　　int _tmain(int argc，_TCHAR* argv[])

　　/************************************************************************/

　　/*矢量如何强制释放内存空间*/

　　/* 默认只有析构时才会释放*/

　　/************************************************************************/

　　向量内部数组

　　cout 默认情况未初始化时，容量= arr。capacity()endl；

　　arr.resize(100，100)；

　　预备队(50人);

　　由…改编调整大小(50)；

　　cout 现在，容量= arr。capacity()endl；

　　vector int:iterator itor=arr。begin()10；

　　arr.erase(arr.begin()，itor)；

　　cout capacity= arr.capacity()，size= arr。size()endl；

　　////方法一、

　　向量int().互换(arr)；//strong制释放空间

　　//方法二、

　　矢量内部温度

　　由…改编交换(临时)；

　　}//临时变量会被析构

　　cout capacity= arr.capacity()，size= arr。size()endl；

　　clock _ t start=clock()；

　　for(int num=0；编号10000数字)

　　向量整数

　　for(int I=0；我我)

　　v1。push _ back(一)；

　　cout 直接推循环10000次用时： clock()-start endl；

　　开始=时钟();

　　for(int num=0；编号10000数字)

　　向量整数

　　v2。调整大小(100)；

　　for(int I=0；我我)

　　v2。push _ back(一)；

　　cout 先调整大小预设大小再推循环10000次用时： clock()-start endl；

　　开始=时钟();

　　for(int num=0；编号10000数字)

　　向量整数

　　v3。储备(100);

　　for(int I=0；我我)

　　v3。push _ back(一)；

　　cout 先保留预设大小再推循环10000次用时： clock()-start endl；

　　向量整数

　　流wf( 2。txt’)；

　　int nFlag=v4。容量()；

　　for(int I=0；我我)

　　v4。push _ back(一)；

　　如果(nFlag！=v4.capacity())

　　nFlag=v4。容量()；

　　cout 新缓冲区大小= nFlag endl

　　wf capacity= nFlag endl

　　wf。close()；

　　cout max _ size= arr。max _ size()endl；

　　返回0;

　　}

　　参考了一些前辈的文章，能力有限，欢迎指教，相互学习。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。