- 1 相关头文件
- 2 内存分配
- 3 vector的缓冲区
- 4 vector的迭代器
- 5 vector的API实现
- 5.1 默认构造函数
- 5.2 从size和初始值构造vector
- 5.3 复制构造函数
- 5.4 从迭代器构造vector
- 5.5 析构函数
- 5.6 push_back
- 5.7 其他
1 相关头文件
stl_vector.h vector.h vector
2 内存分配
vector默认使用__default_alloc_template分配内存，该分配器是线程安全的，具体可见STL源码分析-内存分配
3 vector的缓冲区
vector是_Vector_base的派生类，_Vector_base有三个成员变量
protected: _Tp* _M_start; _Tp* _M_finish; _Tp* _M_end_of_storage;
我们都知道，vector是一种更高级的数组，而数组必然包含一段连续的缓冲区。如下所示，_M_start表示这段缓冲区内数据区的左实边界，_M_finish表示缓冲区内数据区的右虚边界，_M_end_of_storage指向内存缓冲区的右虚边界 ``
4 vector的迭代器
vector使用连续的物理内存空间，因此迭代器直接使用原始指针表示
typedef _Tp value_type; typedef value_type* iterator; // vector的迭代器是普通指针 typedef const value_type* const_iterator; typedef reverse_iterator<const_iterator> const_reverse_iterator; typedef reverse_iterator<iterator> reverse_iterator;
reverse_iterator的定义在stl_iterator.h中，反向迭代器其实是对正向迭代器的一层封装。
5 vector的API实现
5.1 默认构造函数
例如vector<int> a; 这种情况下，vector大小为零，为了节约内存空间，vector<int>不会主动申请内存、创建缓冲区。
explicit vector(const allocator_type& __a = allocator_type()) : _Base(__a) {} _Vector_base(const _Alloc&) : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
5.2 从size和初始值构造vector
例如vector<int> a(100, 0)，这种情况下，_Vector_base首先使用_Alloc类型的内存分配器分配n*sizeof(Tp)的内存，然后在Vector构造函数中填充初始值
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_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; }
5.3 复制构造函数
例如
vector<int> a(100, 0); vector<int> b(a); // 复制构造函数
_Vector_base首先使用_Alloc类型的分配器分配n*sizeof(Tp)的内存，然后Vector构造函数将__x的值复制到本地缓冲区中。
vector(const vector<_Tp, _Alloc>& __x) : _Base(__x.size(), __x.get_allocator()) { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }
5.4 从迭代器构造vector
例如
vector<int> a(100, 0); vector<int> b(a.begin(), a.begin() + 10);
注意这里_Vector_base并没有提前申请长度为last-first的内存，而是在vector::_M_range_initialize中调用_M_allocate来申请内存的。TODO 注意，这里需要区分_InputIterator是否为整数类型
// Check whether it's an integral type. If so, it's not an iterator. template <class _InputIterator> vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a = allocator_type()) : _Base(__a) { typedef typename _Is_integer<_InputIterator>::_Integral _Integral; _M_initialize_aux(__first, __last, _Integral()); } template <class _Integer> void _M_initialize_aux(_Integer __n, _Integer __value, __true_type) { _M_start = _M_allocate(__n); _M_end_of_storage = _M_start + __n; _M_finish = uninitialized_fill_n(_M_start, __n, __value); }
5.5 析构函数
例如vector<int> a(100, 0); 当a被回收时，首先调用vector::~vector将包含的所有元素回收，然后调用_Vector_base::~_Vector_base释放已申请的内存。
~vector() { destroy(_M_start, _M_finish); } ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
5.6 push_back
分两种情况，
- 如果还有可用缓冲区，在缓冲区上执行
inplacement new
- 如果没有可用缓冲区，重新执行
realloc生成新缓冲区, 将旧缓冲区上的数据复制到新缓冲区
代码细节：首先判断是否有空闲内存，如果有，则在空闲内存上执行inplacement new
void push_back(const _Tp& __x) { if (_M_finish != _M_end_of_storage) { construct(_M_finish, __x); ++_M_finish; } else _M_insert_aux(end(), __x); } template <class _T1, class _T2> inline void _Construct(_T1* __p, const _T2& __value) { new ((void*) __p) _T1(__value); }
如果没有空闲内存，则执行_M_insert_aux，接着进入else分支，可以看到，如果push_back之前capacity为0, 扩展后的capacity为1，否则新capacity是旧capacity的两倍。
template <class _Tp, class _Alloc> void vector<_Tp, _Alloc>::_M_insert_aux(iterator __position) { if (_M_finish != _M_end_of_storage) { construct(_M_finish, *(_M_finish - 1)); ++_M_finish; copy_backward(__position, _M_finish - 2, _M_finish - 1); *__position = _Tp(); } else { 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); ++__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; } }
内存分配的调用链路为
_M_allocate -> simple_alloc<_Tp, _Alloc>::allocate -> _Alloc::allocate (_Alloc默认为__STL_DEFAULT_ALLOCATOR(_Tp)) -> allocator<_Tp> -> __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0>
而__default_alloc_template的实现细节见STL源码分析-内存分配
5.7 其他
- begin, 返回数据区左边界的指针
- end, 返回数据区右虚边界指针
- rbegin, 返回数据区右虚边界对应的反向迭代器
- rend, 返回数据区左边界对应的反向迭代器
- size, 返回end()-begin(), 即数据区元素个数
- max_size, 返回size_type类型的最大数, 也就是size_t能够表示的最大值
- capacity, 返回_M_end_of_storage - begin(); 即缓冲区能够容纳的元素个数
- swap, 交换
_M_start，_M_finish，_M_end_of_storage这三个指针即可
- insert, 同
push_back, 不同点在于insert需要移动插入位置之后的所有元素
- pop_back, 销毁末尾元素
- erase, 销毁指定元素或者区间，然后将被销毁元素之后的所有元素向头部复制
- resize，分两种情况
- 新size比现在大，插入
new_size - old_size个0值 - 新size比现在小，对尾部
old_size - new_size个元素执行erase，需要注意的是，resize并不会释放缓冲区上可用内存
- operator=, 假设将b赋值给a, 分三种情况
- 如果b.size > a.capacity, a先执行_M_allocate_and_copy申请并初始化新缓冲区，再执行_M_deallocate释放旧缓冲区
- 如果a.size > b.size, 直接复制b到a, 并销毁a中多余的对象
- 如果a.size < b.size < a.capacity, 先复制b的前a.size个元素到a, 然后执行uninitialized_copy复制b的后b.size-a.size个元素到a中
- reserve, 申请新内存，反向复制所有元素并释放旧内存
- assign(n, val) 实现上也分三种情况
- n > a.capacity, 构造新vector(假设为tmp), 并执行
a.swap(tmp) - a.size < n < a.capacity, 同
operator= - n < a.size, 同
operator=
