【深度探索STL】详解 vector 内部机制
前面初步介绍了序列式容器 vector ：初识序列式容器vector，这里试图通过简单剖析源码来了解 vector 的内部机制，参考资料：《STL 源码剖析》(侯捷)
·
前面初步介绍了序列式容器 vector ：初识序列式容器vector，这里试图通过剖析源码来了解 vector 的内部机制，看看其内部是如何高效运作的。借用侯捷老师的一句话：源码面前，了无秘密。参考资料：《STL 源码剖析》
- 对象的构造和析构 ：http://blog.csdn.net/wenqian1991/article/details/19545049
- 空间配置器之第一级配置器：http://blog.csdn.net/wenqian1991/article/details/19566499
- 空间配置器之第二级配置器：http://blog.csdn.net/wenqian1991/article/details/19605727
- 空间配置器之内存处理工具：http://blog.csdn.net/wenqian1991/article/details/19676159
了解前面四个部分，再去了解容器的内部实现就轻松多了。这里针对前面博文（【STL】序列式容器：vector） 里的程序再结合源码穿针引线来学习 vector 的内部机制。
先了解几个必要成员及函数：
//对源码略作调整
iterator _M_start; //表示目前使用空间的头
iterator _M_finish; //表示目前使用空间的尾（尾：最后一个元素的下一个位置）
iterator _M_end_of_storage; //表示目前可用空间的尾
iterator begin() { return _M_start; }
iterator end() { return _M_finish; }
size_type size() const //目前空间元素的个数
{
return size_type(end() - begin());
}
size_type max_size() const
{
return size_type(-1) / sizeof(_Tp);
}
size_type capacity() const //容量
{
return size_type(_M_end_of_storage - begin());
}
bool empty() const
{
return begin() == end();
}
这里先学习 insert() 函数（后面介绍另一个版本的 insert()：插入n个指定元素）：关于 construc() 函数的介绍可以参见博文【深度探索STL】空间配置器(一) 构造和析构。
iterator insert(iterator __position, const _Tp& __x)
{
size_type __n = __position - begin(); //插入位置与头的距离
if (_M_finish != _M_end_of_storage && __position == end()) //还有剩余空间，且插入位置恰为尾端
{
construct(_M_finish, __x); //直接构造新元素
++_M_finish; //调整迭代器
}
else
_M_insert_aux(__position, __x); //没有剩余空间或插入位置为尾前面，则则调用_M_insert_aux()
return begin() + __n; //返回插入位置
}
template <class _Tp, class _Alloc>
void
vector<_Tp, _Alloc>::_M_insert_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; //赋值对象
//下面的copy_backward()感觉有问题：__position == end() 又 (_M_finish - 1) == end();
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时)的两倍
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); //在指定的插入位置构造新对象，并为新元素设定初值__X
++__new_finish; //调整迭代器位置
//将插入位置后的元素复制到新空间插入元素位置的后面，完成最后的插入操作
__new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
} //捕捉异常，如有一个复制出错，则析构并释放空间
__STL_UNWIND((destroy(__new_start, __new_finish), _M_deallocate(__new_start, __len)));
//析构并释放原 vector
destroy(begin(), end());
_M_deallocate(_M_start, _M_end_of_storage - _M_start);
//调整迭代器，指向新 vector
_M_start = __new_start;
_M_finish = __new_finish;
_M_end_of_storage = __new_start + __len;
}
}
STL 提供了两个版本的 push_back() 函数，
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); //如果没有备用空间，则调用_M_insert_aux()
}
void push_back() {
if (_M_finish != _M_end_of_storage) {
construct(_M_finish); //单纯构造并不初始化数据
++_M_finish;
}
else
_M_insert_aux(end());
}push_back() 与 insert() 都有调用_M_insert_aux() 的情况，二者不同的是，push_back() 只从尾端插入元素，相当于push_back() 是 insert() 函数的一个特例。或许 push_back() 应该定义为：
void push_back(const _Tp& __x)
{
insert(vector<_Tp>::end(), const _Tp& __x);
}从上面可知，vector 增加（插入）新元素时，如果未超过当时的容量，则还有剩余空间，那么直接添加到最后（插入指定位置），然后调整迭代器，这里的 construct() 前面有介绍，是在已分配好的内存上构造对象，这里已分配好的内存定位到剩余空间的起始位置。如果没有剩余空间了，则会重新配置原有元素个数的两倍空间，然后将原空间元素通过复制的方式初始化新空间，再向新空间增加元素，最后析构并释放原空间。
下面学习 pop_back() ，erase()，clear() 等函数的内部实现：
void pop_back() {
--_M_finish; //调整迭代器位置
destroy(_M_finish); //析构空间最后一个元素
}
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); //复制last后面的元素到待擦除段
destroy(__i, _M_finish); //擦除后面,清楚 __i 的位置
_M_finish = _M_finish - (__last - __first); //调整迭代器位置
return __first;
}
void clear() { erase(begin(), end()); }
这里继续学习 insert() 的另一个版本，往指定位置插入 n 个指定元素：insert(position, n, x)
void insert(iterator __pos, size_type __n, const _Tp& __x)
{
_M_fill_insert(__pos, __n, __x);
}
template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_fill_insert(iterator __position, size_type __n, const _Tp& __x)
{
if (__n != 0) //插入元素个数不为 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) { //插入位置后面的元素个数 N 大于插入元素的个数 n，N>n
uninitialized_copy(_M_finish - __n, _M_finish, _M_finish); //将尾端前面的n个元素复制到尾端后面
_M_finish += __n; //调整尾端位置
//逆向复制，将插入位置position后面的 N-n 个元素复制到原尾端位置前面
//这样，插入位置后面的均复制到了最后，留下 n 个空间供插入
copy_backward(__position, __old_finish - __n, __old_finish);
fill(__position, __position + __n, __x_copy); //往插入位置后填进 n 个指定元素
}
else { //插入位置后面的元素个数 N 不大于 插入元素个数，N<=n
uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);//尾端位置后面填进 n-N 个元素
_M_finish += __n - __elems_after; //调整尾端位置到原尾端位置后面第 n-N 个位置
uninitialized_copy(__position, __old_finish, _M_finish); //将插入位置后的元素复制到调整后的尾端位置后
_M_finish += __elems_after; //调整尾端位置
fill(__position, __old_finish, __x_copy); //插入位置到原尾端位置N个元素赋值，前面已赋值n-N个
}
}
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); //填补 n 个元素
__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;
}
}
}
最后再学习 resize()，reserve() 和 swap()函数的内部实现
//将vector大小重置为 __new_size
void resize(size_type __new_size, const _Tp& __x)
{
if (__new_size < size()) //如果新空间大小小于原空间
erase(begin() + __new_size, end()); //则只保留前面 __new_size 个元素
else
insert(end(), __new_size - size(), __x); //如果新空间大一些，则将大于的部分置为指定值
}
//预留至少共容纳 __n 个元素的空间
vector<_Tp, _Alloc>& operator=(const vector<_Tp, _Alloc>& __x);
void reserve(size_type __n) {
if (capacity() < __n) { //当前容量小于需要预留的空间时，才进行以下操作
const size_type __old_size = size(); //记录元素个数
//分配__n大小的空间，然后将原空间元素复制初始化
iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
destroy(_M_start, _M_finish); //析构原空间元素
_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;
}
}
//交换两个 vector 中的元素
//其实就是交换彼此的迭代器指向位置（迭代器的巧妙功能）
void swap(vector<_Tp, _Alloc>& __x) {
__STD::swap(_M_start, __x._M_start);
__STD::swap(_M_finish, __x._M_finish);
__STD::swap(_M_end_of_storage, __x._M_end_of_storage);
}
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
4
0- 0
已为社区贡献3条内容
所有评论(0)