本文共 7545 字,大约阅读时间需要 25 分钟。
一些好的公司校园招聘过程中(包括笔试、面试环节),经常会涉及到STL中vector的使用(主要是笔试)及其性能(面试)的分析。今天看了下相关文章,也写了几个小的测试程序跑了跑。算是总结下,希望对需要的人有帮助。
关于vector,简单地讲就是一个动态数组,里面有一个指针指向一片连续的内存空间,当空间不够装下数据时会自动申请另一片更大的空间,然后把原有数据拷贝过去,接着释放原来的那片空间;当释放或者说是删除里面的数据时,其存储空间并不会释放,仅仅只是清空了里面的数据。接下来,我会详细地说说这些。
备注:本文的相关程序都是在windows 7+VS2008环境下测试。
一、首先,看看vector的内存分配机制:
vector<int> arr;
ofstream wf("1.txt");
for(int i=0;i<100;++i)
{
arr.push_back(i);
wf<<"capacity="<<arr.capacity()<<",size="<<arr.size()<<end;
}
wf.close();
capacity()返回的是当前vector对象缓冲区(后面的对vector维护的内存空间皆称为缓冲区)实际申请的空间大小,而size()返回的是当前对象缓冲区中存储数据的个数,capacity永远是大于等于size的,当size和capacity相等时继续添加数据时vector会扩容。
再来看看1.txt中的数据:
capacity=1,size=1
capacity=2,size=2 capacity=3,size=3 capacity=4,size=4 capacity=6,size=5 capacity=6,size=6 capacity=9,size=7 capacity=9,size=8 capacity=9,size=9 capacity=13,size=10 capacity=13,size=11 capacity=13,size=12 capacity=13,size=13 capacity=19,size=14 capacity=19,size=15 capacity=19,size=16 capacity=19,size=17 capacity=19,size=18 capacity=19,size=19 capacity=28,size=20 capacity=28,size=21 capacity=28,size=22 capacity=28,size=23 capacity=28,size=24 capacity=28,size=25 capacity=28,size=26 capacity=28,size=27 capacity=28,size=28 capacity=42,size=29 capacity=42,size=30 capacity=42,size=31 capacity=42,size=32 capacity=42,size=33 capacity=42,size=34 capacity=42,size=35 capacity=42,size=36 capacity=42,size=37 capacity=42,size=38 capacity=42,size=39 capacity=42,size=40 capacity=42,size=41 capacity=42,size=42 capacity=63,size=43 capacity=63,size=44 capacity=63,size=45 capacity=63,size=46 capacity=63,size=47 capacity=63,size=48 capacity=63,size=49 capacity=63,size=50 capacity=63,size=51 capacity=63,size=52 capacity=63,size=53 capacity=63,size=54 capacity=63,size=55 capacity=63,size=56 capacity=63,size=57 capacity=63,size=58 capacity=63,size=59 capacity=63,size=60 capacity=63,size=61 capacity=63,size=62 capacity=63,size=63 capacity=94,size=64 capacity=94,size=65 capacity=94,size=66 capacity=94,size=67 capacity=94,size=68 capacity=94,size=69 capacity=94,size=70 capacity=94,size=71 capacity=94,size=72 capacity=94,size=73 capacity=94,size=74 capacity=94,size=75 capacity=94,size=76 capacity=94,size=77 capacity=94,size=78 capacity=94,size=79 capacity=94,size=80 capacity=94,size=81 capacity=94,size=82 capacity=94,size=83 capacity=94,size=84 capacity=94,size=85 capacity=94,size=86 capacity=94,size=87 capacity=94,size=88 capacity=94,size=89 capacity=94,size=90 capacity=94,size=91 capacity=94,size=92 capacity=94,size=93 capacity=94,size=94 capacity=141,size=95 capacity=141,size=96 capacity=141,size=97 capacity=141,size=98 capacity=141,size=99 capacity=141,size=100数据有点多,提炼下就是这样的:
capacity=1
capacity=2 capacity=3 capacity=4 capacity=6 capacity=9 capacity=13 capacity=19 capacity=28 capacity=42 capacity=63 capacity=94 capacity=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)//编译器可以申请的最大容量也装不下,抛出异常_THROW(length_error, "vector<T> too long");
_Xlen(); // result too long
else if (_Capacity < size() + _Count)//当前空间不足,需要扩容
{ // not enough room, reallocate
_Capacity = max_size() - _Capacity / 2 < _Capacity
? 0 : _Capacity + _Capacity / 2; // try to grow by 50%,扩容50%
if (_Capacity < size() + _Count)//扩容50%后依然不够容下,则使容量等于当前数据个数加上新增数据个数
_Capacity = size() + _Count;
pointer _Newvec = this->_Alval.allocate(_Capacity);//申请新的空间
pointer _Ptr = _Newvec;
_TRY_BEGIN
_Ptr = _Umove(_Myfirst, _VEC_ITER_BASE(_Where),
_Newvec); // copy prefix <span style="white-space:pre"> </span>//拷贝原有数据到新的内存中
_Ptr = _Ucopy(_First, _Last, _Ptr); // add new stuff<span style="white-space:pre"> </span>//拷贝新增数据到新的内存的后面
_Umove(_VEC_ITER_BASE(_Where), _Mylast, _Ptr); // copy suffix
_CATCH_ALL
_Destroy(_Newvec, _Ptr);
this->_Alval.deallocate(_Newvec, _Capacity);//释放原来申请的内存
_RERAISE;
_CATCH_END
对的,就是每次扩容50%。至于删除容器中数据的时候,缓冲区大小并不会改变,仅仅只是清楚了其中的数据,只有在析构函数调用的时候vector才会自动释放缓冲区。
看看它的析构代码:
~vector()
{ // destroy the object
_Tidy();
}
void _Tidy()
{// free all storage
if (_Myfirst != 0)
{// something to free, destroy and deallocate it
#if _HAS_ITERATOR_DEBUGGING
this->_Orphan_all();
#endif /* _HAS_ITERATOR_DEBUGGING */
_Destroy(_Myfirst, _Mylast);//应该是销毁vector中的每一个元素吧
this->_Alval.deallocate(_Myfirst, _Myend - _Myfirst);//释放缓冲区的空间
}
_Myfirst = 0, _Mylast = 0, _Myend = 0;//指针全部归零
}
那么,我们可以在需要的时候强制释放缓冲区不?
二、如何强制释放vector的缓冲区:
答案是可以的,既然析构时会释放空间,那么我们就可以换个方式调用析构函数。
// //方法一、
vector<int>().swap(arr); //交换后
//方法二、
{
vector<int> temp;//临时对象未初始化,其缓冲区大小为0,没有数据
arr.swap(temp);//与我们的对象交换数据,arr的缓冲区就没了。
}//临时变量会被析构,temp调用vector析构函数释放空间
三、如何使用提高性能:
为了比较,我们用了三种方式来把100个数据存入vector中,分别是:1、直接每次push_back();2、使用resize()提前分配100个空间,然后push_back;3、使用reserve提前分配100个存储空间。MSDN中,这两个个函数的说明分别是:
reserve Reserves a minimum length of storage for a vector object, allocating space if necessary.
resize Specifies a new size for a vector.
在这里我们初始化的时候使用感觉好像是差不多。
clock_t start=clock();
for(int num=0;num<10000;++num)
{
vector<int> v1;
for(int i=0;i<100;++i)
v1.push_back(i);
}
cout<<"直接push循环10000次用时:"<<clock()-start<<endl;
start=clock();
for(int num=0;num<10000;++num)
{
vector<int> v2;
v2.resize(100);
for(int i=0;i<100;++i)
v2.push_back(i);
}
cout<<"先resize预设大小再push循环10000次用时:"<<clock()-start<<endl;
start=clock();
for(int num=0;num<10000;++num)
{
vector<int> v3;
v3.reserve(100);
for(int i=0;i<100;++i)
v3.push_back(i);
}
cout<<"先reserve预设大小再push循环10000次用时:"<<clock()-start<<endl;
reserve只是保持一个最小的空间大小,而resize则是对缓冲区进行重新分配,里面涉及到的判断和内存处理比较多,当然了在这里由于最初都是空的所以差别不大。
两者的区别查看:。
由此可见,对于数据数目可以确定的时候,先预设空间大小是很有必要的。直接push_back数据频繁移动很是耗时(当然了,数据小的可以忽略的)。
真个测试程序的完整代码如下
#include "stdafx.h"
#include "btree.h"
#include <vector>
#include <iostream>
#include <Windows.h>
#include <fstream>
#include <time.h>
using std::ofstream;
using std::cout;
using std::endl;
using std::vector;
int _tmain(int argc, _TCHAR* argv[])
{
/************************************************************************/
/* vector如何强制释放内存空间 */
/* 默认只有析构时才会释放 */
/************************************************************************/
vector<int> arr;
cout<<"默认情况未初始化时,capacity="<<arr.capacity()<<endl;
arr.resize(100,100);
arr.reserve(50);
arr.resize(50);
cout<<"现在,capacity="<<arr.capacity()<<endl;
vector<int>::iterator itor=arr.begin()+10;
arr.erase(arr.begin(),itor);
cout<<"capacity="<<arr.capacity()<<",size="<<arr.size()<<endl;
// //方法一、
vector<int>().swap(arr); //强制释放空间
//方法二、
{
vector<int> temp;
arr.swap(temp);
}//临时变量会被析构
cout<<"capacity="<<arr.capacity()<<",size="<<arr.size()<<endl;
clock_t start=clock();
for(int num=0;num<10000;++num)
{
vector<int> v1;
for(int i=0;i<100;++i)
v1.push_back(i);
}
cout<<"直接push循环10000次用时:"<<clock()-start<<endl;
start=clock();
for(int num=0;num<10000;++num)
{
vector<int> v2;
v2.resize(100);
for(int i=0;i<100;++i)
v2[i] = i;
}
cout<<"先resize预设大小再push循环10000次用时:"<<clock()-start<<endl;
start=clock();
for(int num=0;num<10000;++num)
{
vector<int> v3;
v3.reserve(100);
for(int i=0;i<100;++i)
v3.push_back(i);
}
cout<<"先reserve预设大小再push循环10000次用时:"<<clock()-start<<endl;
vector<int> v4;
ofstream wf("2.txt");
int nFlag=v4.capacity();
for(int i=0;i<100;++i)
{
v4.push_back(i);
if(nFlag!=v4.capacity())
{
nFlag=v4.capacity();
cout<<"new buffer size="<<nFlag<<endl;
wf<<"capacity="<<nFlag<<endl;
}
}
wf.close();
cout<<"max_size="<<arr.max_size()<<endl;
return 0;
}
转载地址:http://oghmi.baihongyu.com/