前言
最近开始看《STL源码剖析》，由于是第一次看，所以开个文章记录和总结下该书印象笔记深刻和重要的知识点。本文主要介绍第三章序列式容器中的vector。
序列式容器
序列式容器为程序员提供了控制元素存储和顺序访问的能力，这种顺序不依赖于元素的值，而是与元素加入容器上的位置想对应。C++语言本身就提供了一个序列式容器array，STL提供vector、list、deque、stack、queue等序列式容器。
序列式容器的衍生关系如上图所示，衍生是内含关系（即底层实现）。可以看到heap(堆)是由vector衍生而来，而priority-queue（优先队列）则由heap衍生而来。stack和queue都有deque（双端队列）衍生而来。
vector概述
vector的数据安排以及操作方式与array十分相似，两者唯一差别在于空间运用的灵活性。array是静态空间，一旦配置后则不能改变。而vector是动态空间，随着元素的加入，它内部机制会自行扩充空间以容纳新元素。
vector迭代器
vector维护的是一个连续的线性空间，所以不论其元素为何，普通指针都可以作为vector的迭代器而满足所有必要条件。vector迭代器需要的操作有*，->，++，--，+，-，+=，-+，而普通指针天生就具备这样的能力，所以vector提供的是随机访问迭代器（Random Access Iterators）。
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc>
{
typedef _Tp value_type;
typedef value_type* iterator; // 可以看出，vector的迭代器是由普通指针实现
}
vector的数据结构与内存管理
vector的数据结构非常简单：线性连续空间，用三个迭代器分别表示其空间可使用和已使用范围，start和finish指向连续空间中已使用的头和尾，end_of_storage则指向整块连续空间（包括已使用和未使用）的尾端。
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc>
{
protected:
#ifdef __STL_HAS_NAMESPACES
....
using _Base::_M_start; // 表示目前使用的空间头
using _Base::_M_finish; // 表示目前使用的空间尾
using _Base::_M_end_of_storage; // 表示目前可用的空间的尾
#endif /* __STL_HAS_NAMESPACES */
}
利用这三个迭代器，便可轻易实现首位标示、大小、容量、判空、[]运算子等功能。
public:
iterator begin() { return _M_start; }
const_iterator begin() const { return _M_start; }
iterator end() { return _M_finish; }
const_iterator end() const { return _M_finish; }
reverse_iterator rbegin()
{ return reverse_iterator(end()); }
const_reverse_iterator rbegin() const
{ return const_reverse_iterator(end()); }
reverse_iterator rend()
{ return reverse_iterator(begin()); }
const_reverse_iterator rend() const
{ return const_reverse_iterator(begin()); }
size_type size() const
{ return size_type(end() - begin()); }
size_type capacity() const
{ return size_type(_M_end_of_storage - begin()); }
bool empty() const
{ return begin() == end(); }
reference operator[](size_type __n) { return *(begin() + __n); }
const_reference operator[](size_type __n) const { return *(begin() + __n); }
vector构造、内存管理及其元素操作
vector默认使用alloc作为空间配置器，并据此另外定义一个data_allocator,以便以元素大小为配置单位。
typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;
构造时空间分配
vector提供许多构造函数（constructors），默认构造函数会为vector配置0个空间，其中还有一个构造函数允许我们指定配置的空间大小及其初值。
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); }
push_back时空间分配
vector的动态增加大小，并不是在原空间后接着增加新空间（无法保证原空间后尚有可供配置的空间），而是重新配置一块大小为原来的两倍的空间，然后将原内容拷贝过来并在其之后构造新元素，并释放原空间。因此，对vector进行操作后若引起空间的重新配置，则指向原vector的所有迭代器都失效（前面说过vector的迭代器是普通指针，这里是因空间释放导致指针失效)。
进行push_back()操作时，该函数会检查空间中是否还有未使用的空间，如果有则在其上面构造元素，并调整finish迭代器。如果没有则扩充空间（重新配置、移动数据、释放原空间）
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 _Tp, class _Alloc>
void
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
if (_M_finish != _M_end_of_storage) { //还有备用空间，push_back该段不会执行
construct(_M_finish, *(_M_finish - 1)); //在备用空间起始处构造一个元素，并以vector最后一个元素作为其初值
++_M_finish;//调整finish
_Tp __x_copy = __x;
copy_backward(__position, _M_finish - 2, _M_finish - 1); //
*__position = __x_copy;
}
else {
const size_type __old_size = size();
const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
//配置原则，若原大小为0，则配置空间大小为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;
}
}
erase操作
erase有两种形式，一种是清处某个位置上的元素，另一种是
清处某个区间上的元素。处理方式都比较简单，将后面的元素覆盖要移除的元素上，并释放多余的空间。vector的clear操作也是通过erase的局部清楚操作实现。
//清除某一位置的元素
iterator erase(iterator __position) {
if (__position + 1 != end())
copy(__position + 1, _M_finish, __position);
--_M_finish;
destroy(_M_finish);
return __position;
}
//清楚某一区间内的元素
iterator erase(iterator __first, iterator __last) {
iterator __i = copy(__last, _M_finish, __first);
destroy(__i, _M_finish);
_M_finish = _M_finish - (__last - __first);
return __first;
}
void clear() { erase(begin(), end()); }
insert操作
insert操作执行时分为三种情况，一种是插入元素小于插入点后现有元素，另一种是插入元素大于插入点后现有元素，还要就是备用空间不够的情况。下面先放这三种情况的图解，看完图解再看代码会便于理解。
代码实现如下
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
copy_backward(__position, __old_finish - __n, __old_finish);
fill(__position, __position + __n, __x_copy);
代码实现如下
uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
_M_finish += __n - __elems_after;
uninitialized_copy(__position, __old_finish, _M_finish);
_M_finish += __elems_after;
fill(__position, __old_finish, __x_copy);
以上两种情况都是基于备用空间够用的情况下，当备用空间不够用时，操作如下图所示
代码实现如下
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);//新空间大小决策
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_fill_n(__new_finish, __n, __x);
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish),
_M_deallocate(__new_start,__len)));
destroy(_M_start, _M_finish);
_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;
insert完整代码实现
void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n, const _Tp& __x)
{
if (__n != 0) {
// 备用空间大于新增元素个数
if (size_type(_M_end_of_storage - _M_finish) >= __n) {
_Tp __x_copy = __x;
// 计算插入点之后的现有元素个数。
const size_type __elems_after = _M_finish - __position;
iterator __old_finish = _M_finish;
if (__elems_after > __n) {
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
_M_finish += __n;
copy_backward(__position, __old_finish - __n, __old_finish);
fill(__position, __position + __n, __x_copy);
}
else {
uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
_M_finish += __n - __elems_after;
uninitialized_copy(__position, __old_finish, _M_finish);
_M_finish += __elems_after;
fill(__position, __old_finish, __x_copy);
}
}
else {
const size_type __old_size = size();
const size_type __len = __old_size + max(__old_size, __n);
iterator __new_start = _M_allocate(__len);
iterator __new_finish = __new_start;
__STL_TRY {
__new_finish = uninitialized_copy(_M_start, __position, __new_start);
__new_finish = uninitialized_fill_n(__new_finish, __n, __x);
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
}
__STL_UNWIND((destroy(__new_start,__new_finish),
_M_deallocate(__new_start,__len)));
destroy(_M_start, _M_finish);
_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;
}
}
}
总结
vector的基本操作还有很多无法逐一列举，不过从中我们了解到了其动态变化和其迭代器的本质。动态扩展空间是通过重新分配空间，数据复制和释放原空间三步完成。因为vector迭代器是通过普通指针实现，当重新分配空间后，原指针自然也就失效。vector的操作也是在这两个基础上进行相关的实现。
注：文中图片来源于《STL源码剖析》
