从零开始学C++之STL（二）：实现简单容器模板类Vec（vector capacity 增长问题、allocator 内存分配器）

aspnetwinform

浏览: 92152 次
性别:
来自: 武汉

最近访客更多访客>>

380071587

zc690739629

standalone

wuyue

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

首先，vector 在VC 2008 中的实现比较复杂，虽然vector 的声明跟VC6.0 是一致的，如下：

C++ Code

1 2

template<class_Ty,class_Ax=allocator<_Ty>>
classvector;

但在VC2008 中vector 还有基类，如下：

C++ Code

1 2 3 4 5 6 7

//TEMPLATECLASSvector
template<class_Ty,
class_Ax>
classvector
:public_Vector_val<_Ty,_Ax>
{
};

稍微来看一下基类_Vector_val：

C++ Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

//TEMPLATECLASS_Vector_val
template<class_Ty,
class_Alloc>
class_Vector_val
:public_CONTAINER_BASE_AUX_ALLOC<_Alloc>
{
//baseclassforvectortoholdallocator_Alval
protected:
_Vector_val(_Alloc_Al=_Alloc())
:_CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al),_Alval(_Al)
{
//constructallocatorfrom_Al
}

typedeftypename_Alloc::template
rebind<_Ty>::other_Alty;

_Alty_Alval;//allocatorobjectforvalues
};

为了理解_Alty 的类型，还得看一下allocator模板类：

C++ Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

template<class_Ty>classallocator
{

template<>class_CRTIMP2_PUREallocator<void>
{
//genericallocatorfortypevoid
public:
template<class_Other>
structrebind
{
//convertanallocator<void>toanallocator<_Other>
typedefallocator<_Other>other;
};
....
};
...
};

typedeftypename_Alloc::templaterebind<_Ty>::other_Alty; 整体来看是类型定义，假设现在我们这样使用

vector<int>，那么_Ty 即 int, _Ax 即 allocator<int>，由vector 类传递给基类_Vector_val，则_Alloc 即

allocator<int> ；可以看到allocator<void> 是allocator 模板类的特化，rebind<_Ty>是成员模板类，other是成员模板类

中自定义类型，_Ty 即是int ，那么other 类型也就是allocator<int>，也就是说_Alty 是类型allocator<int> 。

_Alty _Alval; 即基类定义了一个allocator<int> 类型的成员，被vector 继承后以后用于为vector 里面元素分配内存等操作。

如iteratornew_dataalloc.allocate(new_size); 注意，标准的vector::iterator 是以模板类实现的，下面的实现简单地将其等同为指针，

实际上真正的iterator 类的实现是内部有一个指针成员，指向容器元素。

××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××

对比list 的实现，继承它的基类_List_nod 的一个成员 allocator<_Node> _Alnod; 如下：

typename _Alloc::template rebind<_Node>::other _Alnod; // allocator object for nodes

其中 _Node有三个成员，如下：

_Nodeptr _Next; // successor node, or first element if head

_Nodeptr _Prev; // predecessor node, or last element if head

_Ty _Myval; // the stored value, unused if head

如果是list<int> ，那么_Ty 即是int 类型。双向链表在创建一个新结点时，这样实现：

_Nodeptr _Pnode = this->_Alnod.allocate(1); // 即分配一个节点的空间，返回指向这个节点的指针。

实际上list 还继承另外两个基类的两个成员，如下：

typename _Alloc::template rebind<_Nodeptr>::other _Alptr;// allocator object for pointers to nodes

typename _Alloc::template rebind<_Ty>::other _Alty _Alval; // allocator object for values stored in nodes

×××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××

在VC6.0 vector 的实现，_Alval 是直接作为vector 自身的成员存在的。此外还有一个比较大的不同点在于，两个版本对于capacity 也就是容量的

计算方式不同，接下去的测试可以看到这种不同，在这里可以先说明一下：

VC2008：容量每次增长为原先容量 + 原先容量 / 2;

VC6.0 ：容量每次增长为原先容量的2倍。

容量跟vector 大小的概念是不一样的，capacity 》= size，如下图所示：

size 指的是avail - data 的区间；capacity 指的是 limit - data 的区间；也就是说存在尚未使用的空间。

******************************************************************************************************************************************************

data, avail 和 limit 是vector 类的三个指针成员，对比list 的实现，自身也许只有两个成员，如下：

Nodeptr _Myhead; // pointer to head node

size_type _Mysize; // number of elements

*******************************************************************************************************************************************************

下面是模仿VC6.0 中vector 的实现写的Vec 类，程序主要参考《Accelerated C++》，略有修改，比如将接口修改成与VC6.0 一致，

这样做的好处是可以传递第二个参数，也就是说可以自己决定内存的分配管理方式；实现capacity() 函数等；

Vec.h：

C++ Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191

/*************************************************************************
>FileName:template_class_Vec.h
>Author:Simba
>Mail:dameng34@163.com
>CreatedTime:Thu07Feb201306:51:12PMCST
************************************************************************/

#include<iostream>
#include<cstddef>
#include<memory>
#include<algorithm>

template<classT,classA_=std::allocator<T>>
classVec
{

public://interface
typedefT*iterator;
typedefconstT*const_iterator;
typedefsize_tsize_type;
typedefTvalue_type;
typedefstd::ptrdiff_tdifference_type;
typedefT&reference;
typedefconstT&const_reference;

Vec()
{
create();//defaultconstructor
}
//constT&t=T();意思是默认参数，当没有传递参数时，T() 即定义一个类型为T的无名对象（参数为空会调用默认构造函数）

// 也就是 t 引用着这个无名对象。

//explicit表示不允许构造函数进行隐式类型转换
explicitVec(size_typen,constT&val=T())
{
create(n,val);
}
Vec(constVec&v)
{
create(v.begin(),v.end());//copyconstructor
}
Vec&operator=(constVec&);//assigmentoperator
~Vec()
{
uncreate();//destructor
}

size_typesize()const
{
returnavail-data;//avalueofptrdiff_t
}
size_typecapacity()const
{
return(data==0?0:limit-data);
}
T&operator[](size_typei)
{
returndata[i];
}
/*becausetheirleftoperandisdifferent(const),wecanoverloadtheoperation*/
constT&operator[](size_typei)const
{
returndata[i];
}

iteratorbegin()
{
returndata;
}
const_iteratorbegin()const
{
returndata;
}
iteratorend()
{
returnavail;
}
const_iteratorend()const
{
returnavail;
}

voidpush_back(constT&val)
{
if(avail==limit)//getspaceifneeded
grow();
unchecked_append(val);//appendthenewelement
}
voidclear()
{
uncreate();
}
voidempty()
{
returndata==avail;
}

private:
iteratordata;//firstelementintheVec
iteratoravail;//onepastthelastconstructedelementintheVec
iteratorlimit;//onepastthelastavailableelement

A_alloc;//objecttohandlememoryallocation
//allocateandinitializetheunderlyingarray
voidcreate();
voidcreate(size_type,constT&);
voidcreate(const_iterator,const_iterator);

//destorytheelementinthearrayandfreethememory
voiduncreate();
//supportfunctionsforpush_back
voidgrow();
voidunchecked_append(constT&);

};

template<classT,classA_>
Vec<T,A_>&Vec<T,A_>::operator=(constVec<T,A_>&rhs)
{
//checkforself-assigment
if(&rhs!=this)
{
uncreate();
create(rhs.begin(),rhs.end());
}

return*this;
}

template<classT,classA_>
voidVec<T,A_>::create()
{
data=avail=limit=0;
}

template<classT,classA_>
voidVec<T,A_>::create(size_typen,constT&val)
{
data=alloc.allocate(n);
limit=avail=data+n;
std::uninitialized_fill(data,limit,val);
}

template<classT,classA_>
voidVec<T,A_>::create(const_iteratori,const_iteratorj)
{
data=alloc.allocate(j-i);
limit=avail=std::uninitialized_copy(i,j,data);
/*returnapointerto(onepast)thelastelementthatitinitialized*/
}

template<classT,classA_>
voidVec<T,A_>::uncreate()
{
if(data)
{
//destroy(inreverseorder)theelementsthatwereconstructed
iteratorit=avail;
while(it!=data)
//destoryrunsT'sdestructorforthatobject,renderingthestorageuninitializedagain
alloc.destroy(--it);

alloc.deallocate(data,limit-data);
}
//resetpointerstoindicatethatVecisemptyagain
data=limit=avail=0;
}

template<classT,classA_>
voidVec<T,A_>::grow()
{
//whengrowing,allocatetwiceasmuchspaceascurrentlyinuse
size_typenew_size=std::max(2*(limit-data),ptrdiff_t(1));

//allocatenewspaceandcopyelementstothenewspace
iteratornew_data=alloc.allocate(new_size);
iteratornew_avail=std::uninitialized_copy(data,avail,new_data);

//returntheoldspace
uncreate();

//resetpointerstopointtothenewlyallocatedspace
data=new_data;
avail=new_avail;
limit=data+new_size;
}

template<classT,classA_>
//errorC4519:仅允许在类模板上使用默认模板参数
voidVec<T,A_>::unchecked_append(constT&val)
{
alloc.construct(avail++,val);
}

先介绍一下用到的一些类和函数：

allocator 模板类：

C++ Code

1 2 3 4 5 6 7 8 9 10

#include<memory>
template<classT>classallocator
{
public:
T*allocate(size_t);
voiddeallocate(T*,size_t);
voidconstruct(T*,size_t);
voiddestroy(T*);
//.......
};

当然实际的接口没实现没那么简单，但大概实现的功能差不多:

allocate 调用operator new ；deallocate 调用 operator delete; construct 调用placement new （即在分配好的内

存上调用拷贝构造函数），destroy 调用析构函数。

两个std函数：

C++ Code

1 2 3 4 5

template<classIn,classFor>
Foruninitialized_copy(In,In,For);

template<classFor,classT>
voiduninitialized_fill(For,For,constT&);

如std::uninitialized_copy(i,j,data); 即将i ~ j 指向区间的数值都拷贝到data 指向的区间，返回的是最后一个初始化值的下一个位置。

std::uninitialized_fill(data,limit,val); 即将 data ~ limit 指向的区间都初始化为val 。

为了理解push_back 的工作原理，写个小程序测试一下：

C++ Code

#include<iostream>
#include"Vec.h"

usingnamespacestd;

classTest
{
public:
Test()
{
cout<<"Test..."<<endl;
}
Test(constTest&other)
{
cout<<"copyTest..."<<endl;
}
~Test()
{
cout<<"~Test..."<<endl;
}
};

intmain(void)
{
vector<Test>v2;
Testt1;
Testt2;
Testt3;
v2.push_back(t1);
v2.push_back(t2);
v2.push_back(t3);

return0;
}

从输出可以看出，构造函数调用3次，拷贝构造函数调用6次，析构函数调用9次，下面来分析一下，首先看下图：

首先定义t1, t2, t3的时候调用三次构造函数，这个没什么好说的；接着第一次调用push_back，调用grow进而调用alloc.allocate，

allocate 函数调用operator new 分配一块内存，第一次uncreate 没有效果，接着push_back 里面调用uncheck_append，进而调用

alloc.construct，即调用placement new（new (_Vptr) _T1(_Val); ），在原先分配好的内存上调用一次拷贝构造函数。

接着第二次调用push_back，一样的流程，这次先分配两块内存，将t1 拷贝到第一个位置，调用uncreate()，先调用alloc.destroy，即

调用一次析构函数，接着调用alloc.deallcate，即调用operator delete 释放内存，最后调用uncheck_append将t2 拷贝到第二个位置。

第三次调用push_back，也一样分配三块内存，将t1, t2 拷贝下来，然后分别析构，最后将t3 拷贝上去。

程序结束包括定义的三个Test 对象t1, t2, t3 ，析构3次，Vec<Test> v2; v2是局部对象，生存期到则调用析构函数~Vec(); 里面调用

uncreate()，调用3次Test 对象的析构函数，调用operator delete 释放3个对象的内存。故总共析构了6次。

在VC2008 中换成vector<Test> v2; 来测试的话，输出略有不同，如下：

输出的次数是一致的，只是拷贝的顺序有所不同而已，比如第二次调用push_back 的时候，VC2008 中的vector 是先拷贝t2, 接着拷

贝t1, 然后将t1 释放掉。

最后再来提一下关于capacity 的计算，如下的测试程序：

C++ Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

#include<iostream>
#include"Vec.h"

usingnamespacestd;

intmain(void)
{
Vec<int>v;

v.push_back(1);
cout<<v.capacity()<<endl;
v.push_back(1);
cout<<v.capacity()<<endl;
v.push_back(1);
cout<<v.capacity()<<endl;
v.push_back(1);
cout<<v.capacity()<<endl;
v.push_back(1);
cout<<v.capacity()<<endl;
v.push_back(1);
cout<<v.capacity()<<endl;
v.push_back(1);
cout<<v.capacity()<<endl;
}

输出为 1 2 4 4 8 8 8 即在不够的情况下每次增长为原来的2倍。

如果换成 vector<int> v; 测试，那么输出是 1 2 3 4 6 6 9，即在不够的情况每次增长为原来大小 + 原来大小 / 2；

看到这里，有些朋友会疑惑了，由1怎么会增长到2呢？按照原则不是还是1？其实只要看一下vector 的源码就清楚了：

C++ Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

void_Insert_n(const_iterator_Where,
size_type_Count,const_Ty&_Val)
{
//insert_Count*_Valat_Where

.....
size_type_Capacity=capacity();
.....
elseif(_Capacity<size()+_Count)
{
//notenoughroom,reallocate
_Capacity=max_size()-_Capacity/2<_Capacity
?0:_Capacity+_Capacity/2;//trytogrowby50%
if(_Capacity<size()+_Count)
_Capacity=size()+_Count;
pointer_Newvec=this->_Alval.allocate(_Capacity);
pointer_Ptr=_Newvec;
.....
}
}

_Insert_n 是被push_back 调用的，当我们试图增长为_Capacity+_Capacity/2; 时，下面还有一个判断：

if(_Capacity<size()+_Count)

_Capacity=size()+_Count;

现在试图增长为 1 + 1/ 2 = 1；此时因为 1 < 1 + 1 ; 所以_Capacity = 1 + 1 = 2;

其他情况都是直接按公式增长。

从上面的分析也可以看出，当push_back 的时候往往带有拷贝和析构多个操作，所以一下子分配比size() 大的空间capacity，可以减

轻频繁操作造成的效率问题。

参考：

C++ primer 第四版
Effective C++ 3rd
C++编程规范

分享到：

圣殿骑士博文索引 | Hibernate从入门到精通（八）一对多单向关 ...

2013-07-23 18:23
浏览 998
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论