上篇文章中很粗略的角度讲解了一下stl_deque的设计思想,以及涉及到得浅显的STL内存管理方面,至少我们看得到的冰山一角.
这篇文章中关于vector的分析,我将将一些问题细化一下,对一些函数做细致的分析.有些时候,有些问题还是说清楚比较好.
打开stl_vector的源码,发现vector的设计思路和stl_deque如出一辙,想想这样是很合理的,保持实现的一致性.只是stl_vector没有提供一个确定的
模板类Iterator去实现迭代器,而是在vector模板类中实现了迭代. 但是和deque基本没有什么大的不同.下面来看看源码:
1. 这次就不讲解设计部分了,主要讲解实现部分.如果没有看前面一篇文章,我尽力做到和前一篇文章没有关系,但是最好还是去了解一下设计部分.详细
可参考这篇文章:C++ Standard Stl -- SGI STL源码学习笔记(04) stl_deque && 初涉STL内存管理.
2. vector的内存管理模板类:_Vector_alloc_base. 它是一个模板类,但是有一个特化的版本,区别在于对分配器Allocator(不知道这种分配器的叫法
是否合适,以前阅读apache源码分析的时候,里面对于allocator称作分配子,但是这两者的作用和概念都是不同的.)对象是否为成员变量.
好吧,对于通用_Vector_alloc_base模板类和特化_Vector_alloc_base模板类,我们从内存操作的方法上面区分一下:
通用_Vector_alloc_base模板内存操作方法:
_Tp* _M_allocate(size_t __n) // 使用成员变量实现内存操作
{ return _M_data_allocator.allocate(__n); }
void _M_deallocate(_Tp* __p, size_t __n)
{ if (__p) _M_data_allocator.deallocate(__p, __n); }
特化_Vector_alloc_base内存操作方法:
typedef typename _Alloc_traits<_Tp, _Allocator>::_Alloc_type _Alloc_type; // 使用方法直接操作,没有作为成员变量
_Tp* _M_allocate(size_t __n)
{ return _Alloc_type::allocate(__n); }
void _M_deallocate(_Tp* __p, size_t __n)
{ _Alloc_type::deallocate(__p, __n);}
当然,无论是通用模板类还是特化模板类,都使用了traits技术.
3. vector的成员变量:
_Tp* _M_start; // start _Tp* _M_finish; // 初始化的时候_M_finish = _M_start _Tp* _M_end_of_storage // 指向最后一个元素的下一个位置. 注意不是最后一个元素.
这三个成员变量都是vector继承自基类, 这三个指针指向三个不同的位置. 可以从构造函数中看得到:
_Vector_base(size_t __n, const _Alloc&)
: _M_start(0), _M_finish(0), _M_end_of_storage(0)
{
_M_start = _M_allocate(__n);
_M_finish = _M_start;
_M_end_of_storage = _M_start + __n;
}
根据初始化的长度_n初始化_M_start, _M_finish, _M_end_of_storage.
explicit vector(const allocator_type& __a = allocator_type())
: _Base(__a) {}
vector(size_type __n, const _Tp& __value,
const allocator_type& __a = allocator_type())
: _Base(__n, __a)
{ _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
explicit vector(size_type __n)
: _Base(__n, allocator_type())
{ _M_finish = uninitialized_fill_n(_M_start, __n, _Tp()); }
vector(const vector<_Tp, _Alloc>& __x)
: _Base(__x.size(), __x.get_allocator())
{ _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
由vector提供的构造函数可以看得出,都是使用基类_vector_base的构造函数进行初始化.由于vector模板类提供了一个默认参数,可以使用默认
分配器allocator.
inline T* allocate(ptrdiff_t size, T*) {
set_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_start得到了allocate函数的返回指针,而M_finish默认初始化和M_start相同.看看对于_M_finish的处理.
由宏uninitialized_fill_n处理,进行跳转,到__uninitialized_fill_n,再到__uninitialized_fill_n_aux.
SGI STL在这里做了相当复杂的处理,主要是判断vector里面的元素类型判断,是POD类型还是不是POD类型.(POD? Plain Old Data,朴素的旧式数据,built-in类型就是POD
可以参开<<c++必知必会>> 条款11 编译期会在类中放东西. 其中讲到了类多态中的v-table,考虑是不是写一篇随笔介绍一下.)
template <class _ForwardIter, class _Size, class _Tp, class _Tp1>
inline _ForwardIter
__uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x, _Tp1*)
{
typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
return __uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
}
_type_traits模板类提供了很多偏特化,都是处理这种build-in类型. 对于build-in POD is_POD_type都是_true_type.
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n,
const _Tp& __x, __true_type)
{
return fill_n(__first, __n, __x);
}
template <class _ForwardIter, class _Size, class _Tp>
_ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n,
const _Tp& __x, __false_type)
{
_ForwardIter __cur = __first;
__STL_TRY {
for ( ; __n > 0; --__n, ++__cur)
_Construct(&*__cur, __x);
return __cur;
}
__STL_UNWIND(_Destroy(__first, __cur));
}
这里是对_M_finish的最终实现.补充fill_n的源码:
template <class _OutputIter, class _Size, class _Tp>
_OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value) {
__STL_REQUIRES(_OutputIter, _OutputIterator);
for ( ; __n > 0; --__n, ++__first)
*__first = __value;
return __first;
}
不管vector中的元素类型是否是POD,都是移动_M_start,而且还做了相应的初始化.