C++vector容器源码分析
vector源码解析
//继承关系
class vector :protected _Vector_ba<_Tp, _Alloc>;
emplate <class _Tp,class _Alloc>
class _Vector_ba {}
template<class _Tp,class _Allocator>
class _Vector_alloc_ba<_Tp, _Allocator,true>
{
public:
typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
allocator_type;
//获取空间配置器类型
allocator_type get_allocator()const{return allocator_type();}
_Vector_alloc_ba(const allocator_type&)
:_M_start(0),_M_finish(0),_M_end_of_storage(0)
{}
protected:
_Tp* _M_start;
_Tp* _M_finish;
_Tp* _M_end_of_storage;
};
权威翻译公司
_M_start是指向第⼀个元素的指针，等同于begin()，_M_finish是指向最后⼀个元素的下⼀个位置 _M_finish-_M_start=size(); _M_end_of_storage；等同于获取当前容器的容量，指向容器的最尾部。
vector迭代器其实是⼀个类对象指针，重载了⼀系列指针的操作。
typedef _Tp value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type* iterator;
typedef const value_type* const_iterator;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
allocator_type get_allocator()const{return _Ba::get_allocator();}
//显⽰调⽤了⽗类的成员函数，获取空间配置器类型
//stl对其做了⼀个类型萃取
类型萃取帮助我们提取出⾃定义类型进⾏深拷贝，⽽内置类型统⼀进⾏浅拷贝，也就是所谓的值拷贝。
构造函数1
vector(size_type __n,const _Tp& __value)
:_Ba(__n, __a)//对⽗类进⾏了构造
//typedef _Vector_ba<_Tp, _Alloc> _Ba;⽗类别名
//const allocator_type& __a = allocator_type())；为了申请空间⽽服务的
{
_M_finish =uninitialized_fill_n(_M_start, __n, __value);
}
const allocator_type& __a =allocator_type();//缺省参数选择性忽略
vector空间配置器申请空间，_ba(n,a)；具体实现如下
_Vector_ba(size_t __n,const allocator_type& __a):_Ba(__a)
{
_M_start =_M_allocate(__n);//申请空间
//-------------------函数实现--------------------------------
_Tp*_M_allocate(size_t __n)
allocated{
return _M_data_allocator.allocate(__n);
}
/
/allocate实现如下
template<class T>inline T*allocate(ptrdiff_t size, T*)
{
t_new_handler(0);
T* tmp =(T*)(::operator new((size_t)(size *sizeof(T))));//申请内存空间if(tmp ==0)
{
cerr <<"out of memory"<< endl;
exit(1);
}
return tmp;
}
/
/------------------------分割线实现如下------------------------
_M_finish = _M_start;
_M_end_of_storage = _M_start + __n;
}
构造函数2
可以传递⼀个范围，迭代器类型，或者内置类型初始化
vector(const _Tp* __first,const _Tp* __last)
:_Ba(__last - __first, __a)//对空间申请进⾏操作，确定申请空间的范围
{
_M_finish =uninitialized_copy(__first, __last, _M_start);
//函数实现uninitialized_copy-------------------------------
}
//
inline char*uninitialized_copy(const char* __first,const char* __last,char* __result) {
//进⾏内存拷贝操作
memmove(__result, __first, __last - __first);
return __result +(__last - __first);
}
构造函数3
可以传递⼀个vector来初始化
vector(const vector<_Tp, _Alloc>& __x)
:_Ba(__x.size(), __x.get_allocator())
{
_M_finish =uninitialized_copy(__x.begin(), __x.end(), _M_start);
}
构造函数4
可以传递⼀个size_t类型的，来直接初始化⼀⽚空间为0
explicit vector(size_type __n)
:_Ba(__n,allocator_type())
{
_M_finish =uninitialized_fill_n(_M_start, __n,_Tp());
}
赋值运算符重载
vector<_Tp, _Alloc>&operator=(const vector<_Tp, _Alloc>& __x);
void rerve(size_type __n)
{
if(capacity()< __n)//获取当前容量数量注1
{
const size_type __old_size =size();//获取⽼的元素个数
iterator __tmp =_M_allocate_and_copy(__n, _M_start, _M_finish);
//__tmp迭代器类型注2
destroy(_M_start, _M_finish);
//注3vkt
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __tmp;
_M_finish = __tmp + __old_size;
_M_end_of_storage = _M_start + __n;
}
}
注1：
从性能考虑，重新分配内存空间效率不⾼。如果预先知道元素的数量，可以使⽤rerve()函数来消除重新分配。
注2：
iterator _M_allocate_and_copy(size_type __n, const_iterator __first,
const_iterator __last)
{
iterator __result =_M_allocate(__n);
__STL_TRY
{
uninitialized_copy(__first, __last, __result);
return __result;
}
__STL_UNWIND(_M_deallocate(__result, __n));
}
注3：
template<class _Tp>
德福报名官网>coroerinline void_Destroy(_Tp* __pointer)
{
__pointer->~_Tp();
}
Increa the capacity of the vector to a value that’s greater or equal to new_cap. If new_cap is greater than the current , new storage is allocated, otherwi the method does nothing.
rerve() does not change the size of the vector.
尝试将把vector扩容到⼤于或等于new_cap。
如果new_cap⼤于当前容量，则重新分配。
**rerve()**并不改变vector。
这⾥涉及到vector的优化策略
将原有空间进⾏扩容，并不重新分配空间，将原来空间中的数据清空。
inrt函数的动态扩容
inrt函数在vector中⾄关重要，push_back()的动态扩容和inrt有很⼤区别
先抛出结论
inrt不知道需要插⼊多个元素，如果按照sizex2去扩容，⼀旦插⼊数据过多，会需要扩容很多造成效率上的降低。Linux系统下经过测试
t是当前元素个数–m=要插⼊的个数，n是总容量，m是待插⼊个数
1：n-t<m<t 按照2xt⽅式去扩容
2：当m<n-t 不需要扩容
3：m>n 按照t+m⽅式进⾏扩容
inrt ⽅式1，插⼊单个数据，⽆需考虑上述过程
iterator inrt(iterator __position,const _Tp& __x)
{
size_type __n = __position -begin();//从要插⼊的位置，计算好距离begin()的偏移
if(_M_finish != _M_end_of_storage && __position ==end())
{//如果是在尾部进⾏插⼊，并且当前容量够⽤的情况下
//如果不是vector数组本⾝之后的位置，就证明肯定容量是够⽤的太棒了英文
construct(_M_finish, __x);//注4
++_M_finish;//在中间插⼊的，偏移⼀次，继续指向最后⼀个元素的下⼀个元素
}
el
{//在尾部进⾏插⼊
_M_inrt_aux(__position, __x);//注5
}
return begin()+ __n;
}
注4：
template<class _T1,class _T2>
inline void construct(_T1* __p,const _T2& __value){
_Construct(__p, __value);
}
//第⼀层调⽤
template<class _T1,class _T2>
inline void_Construct(_T1* __p,const _T2& __value)
{
new((void*) __p)_T1(__value);//new定位符，在指定空间申请内存
/
/直接构建对象
}
//第⼆层调⽤
注5：
M_inrt_aux动态扩容实现
template<class _Tp,class _Alloc>
void
vector<_Tp, _Alloc>::_M_inrt_aux(iterator __position,const _Tp& __x) {
if(_M_finish != _M_end_of_storage)//如果当前容量仍然够⽤的情况下
{
construct(_M_finish,*(_M_finish -1));//申请空间
++_M_finish;//将其后移，始终指向当前最后⼀个元素的下⼀个点
美国恐怖故事 第二季_Tp __x_copy = __x;//将传进来待插⼊的value保存好
copy_backward(__position, _M_finish -2, _M_finish -1);
//注6
*__position = __x_copy;
}
el//容量不⾜的情况下需要考虑申请空间了
{专四成绩什么时候出来
const size_type __old_size =size();
const size_type __len = __old_size !=0?2* __old_size :1;
iterator __new_start =_M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY {
__new_finish =uninitialized_copy(_M_start, __position, __new_start);
construct(__new_finish, __x);
++__new_finish;
__new_finish =uninitialized_copy(__position, _M_finish, __new_finish); }
__STL_UNWIND((destroy(__new_start,__new_finish),
_M_deallocate(__new_start,__len)));
destroy(begin(),end());
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
注6
功能：将每个元素都往后移动⼀位，直到要插⼊的位置
template<class _BI1,class _BI2>
inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
{
return__copy_backward(__first, __last, __result,
__ITERATOR_CATEGORY(__first),
__DISTANCE_TYPE(__first));
}
//第⼀层调⽤masonry
template<class _BidirectionalIter1,class _BidirectionalIter2,
class _Distance>
inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first,
_BidirectionalIter1 __last,
_BidirectionalIter2 __result,
bidirectional_iterator_tag,
_Distance*)
{
while(__first != __last)
*--__result =*--__last;
return __result;
}管鲍之交翻译
//第⼆层调⽤
