STL漫游之vector

std::vector 源码分析 从源码视角观察 STL 设计,代码实现为 libstdc++(GCC 4.8.5).
由于只关注 vector 的实现,并且 vector 实现几乎全部在头文件中,可以用一个这样的方法里获取比较清爽的源码

// main.cpp #include int main() { std::vector v; v.emplace_back(1); }

g++ -E main.cpp -std=c++11 > vector.cpp
在 vscode 中打开 vector.cpp 使用正则 "#.*\n" 把所以编译器相关的行删除,这样再进行格式化,就可以把预编译指令全部过滤了,而且不依赖外部的实现,跳转也没有压力
allocator 对于一个 allocator 需要实现的 trait,至少需要
  • allocate 内存的分配
  • deallocate 内存的回收
allocator 分配的最小粒度为对象,故要增加一个最大分配的数量
  • max_size 最大分配数量
以上是实现一个分配器的最基础功能。在此基础上,扩展对象的构造和析构,对于需要使用分配器的地方比如 STL,容器自身就不用再关注对象的构造和析构的内存相关功能了。
  • construct 对象构造,意味着需要使用模版实现,通用化
  • destroy 对象销毁
综上,实现 allocator 具有的 alloc_traits 如下:
  • allocate 分配
  • deallocate 回收
  • construct 对象构造,意味着需要使用模版实现,通用化
  • destroy 对象销毁
  • max_size 最大分配数量
std::allocator
标准库的分配器实现比较简单,分配和回收使用 ::operator new/delete
pointer allocate(size_type __n, const void * = 0) { if (__n > this->max_size()) std::__throw_bad_alloc(); return static_cast<_Tp *>(::operator new(__n * sizeof(_Tp))); }void deallocate(pointer __p, size_type) { ::operator delete(__p); }

对于最大分配数量,整个进程空间(虚拟)都可以进行分配
// sizeof(size_t) = 进程地址宽度 size_type max_size() const throw() { return size_t(-1) / sizeof(_Tp); }

对于对象的构造和析构,则使用布置构造和析构函数
void construct(pointer __p, const _Tp &__val) { ::new ((void *)__p) _Tp(__val); }void destroy(pointer __p) { __p->~_Tp(); }

std::vector 通用顺序容器,支持自定义内存分配器;
基础实现
libstdc++ 对 vector 的定义如下,里面提供了:
template > class vector : protected _Vector_base<_Tp, _Alloc> {};

两个模版参数:一个容器内的元素类型,一个分配器类型,并且分配器类型不是必须参数。
使用 protected 继承 _Vector_base,不过这里并没有利用空基类优化(EBO), 更多的是做了类的隔离;
观察 _Vector_base 的实现,包含了一个 impl:
template struct _Vector_base { typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type; typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer pointer; struct _Vector_impl : public _Tp_alloc_type { pointer _M_start; pointer _M_finish; pointer _M_end_of_storage; }public: _Vector_impl _M_impl; }

_Vector_base 提供了 vector 的对内存的操作,包括分配内存和释放,_Vector_impl public 继承 _Tp_alloc_type(默认为 std::allocator<_Tp1>),从 C++ 的语义上说 _Vector_impl 也可以叫做一个分配器(事实也是)。
_Vector_impl _Vector_impl 实现比较简单,三个核心成员变量,作为 vector 的底层表达
  • _M_start 元素空间起始地址,data() 返回的地址
  • _M_finish 元空间结束地址, 和 size() 相关
  • _M_end_of_storage 元素可用空间结束地址,和 capacity() 相关
struct _Vector_impl : public _Tp_alloc_type { pointer _M_start; pointer _M_finish; pointer _M_end_of_storage; _Vector_impl() : _Tp_alloc_type(), _M_start(0), _M_finish(0), _M_end_of_storage(0) {}_Vector_impl(_Tp_alloc_type const &__a) : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0) {}void _M_swap_data(_Vector_impl &__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); } };

STL漫游之vector
文章图片

_Vector_base 【STL漫游之vector】_Vector_impl 已经提供了底层存储的表达,_Vector_base 则为对底层表达的初始化,及屏蔽内存的实现并对上层提供申请/释放接口
// 只选了一个构造函数展示 _Vector_base(size_t __n) : _M_impl() { _M_create_storage(__n); }void _M_create_storage(size_t __n) { this->_M_impl._M_start = this->_M_allocate(__n); this->_M_impl._M_finish = this->_M_impl._M_start; this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; }// 释放内存 ~_Vector_base() { _M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start); }pointer _M_allocate(size_t __n) { return __n != 0 ? _M_impl.allocate(__n) : 0; }void _M_deallocate(pointer __p, size_t __n) { if (__p) _M_impl.deallocate(__p, __n); }

构造函数 拿了三个构造函数的实现来看,后面两者需要注意构造的时候就会有 size() 个复制的代价
L174 默认构造函数,除了基础的初始化什么都不做
L209 构造拥有 initializer_list init 内容的容器
L214 构造拥有范围 [first, last) 内容的容器
174explicit vector(const allocator_type &__a) : _Base(__a) {}209vector(initializer_list __l, 210const allocator_type &__a = allocator_type()) 211: _Base(__a) { 212_M_range_initialize(__l.begin(), __l.end(), random_access_iterator_tag()); 213}214template > 216vector(_InputIterator __first, _InputIterator __last, 217const allocator_type &__a = allocator_type()) 218: _Base(__a) { 219_M_initialize_dispatch(__first, __last, __false_type()); 220}

方法
搞明白 std::vector 的底层实现,后面直接看提供的方法了,最基本的增删改查大小。
大小相关 size() 内部的元素个数,实现为
size_type size() const { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }

capacity() 可用空间的大小,实现为
size_type capacity() const { return size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_start); }

push_back push_back 是使用最频繁的方法,搞清楚它的实现,整个 vector 的变化策略都会比较清晰。
60void push_back(const value_type &__x) { 61if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) { 62_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x); 63++this->_M_impl._M_finish; 64} else 65_M_emplace_back_aux(__x); 66} 67 68void push_back(value_type &&__x) { emplace_back(std::move(__x)); }85template 86template 87void vector<_Tp, _Alloc>::emplace_back(_Args && ...__args) { 88if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) { 89_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, 90std::forward<_Args>(__args)...); 91++this->_M_impl._M_finish; 92} else 93_M_emplace_back_aux(std::forward<_Args>(__args)...); 94}

push_back() 底层有使用 emplace_back(c++11) 优化的情况:
size() < capacity() 的情况下,直接在最后一个元素后的位置进行复制/移动构造,底层地址偏移+1.
size() == capacity() 的情况下,需要先申请一块新的内存后,再插入新的元素并且需要将之前的元素也移动至新的内存中,实现如下,忽略了异常处理和不需要的分支处理。
11template 12template 13void vector<_Tp, _Alloc>::_M_emplace_back_aux(_Args && ...__args) { 14const size_type __len = 15_M_check_len(size_type(1), "vector::_M_emplace_back_aux"); 16pointer __new_start(this->_M_allocate(__len)); 17pointer __new_finish(__new_start); 19_Alloc_traits::construct(this->_M_impl, __new_start + size(), 20std::forward<_Args>(__args)...); 21__new_finish = 0; 22__new_finish = std::__uninitialized_move_if_noexcept_a( 23this->_M_impl._M_start, this->_M_impl._M_finish, __new_start, 24_M_get_Tp_allocator()); 25++__new_finish; 26std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 27_M_get_Tp_allocator()); 28_M_deallocate(this->_M_impl._M_start, 29this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 30this->_M_impl._M_start = __new_start; 31this->_M_impl._M_finish = __new_finish; 32this->_M_impl._M_end_of_storage = __new_start + __len; 33}

_M_check_len 校验是否有足够的空间进行分配,并且返回增长后的大小,实现如下
size_type _M_check_len(size_type __n, const char *__s) const { if (max_size() - size() < __n) __throw_length_error((__s)); const size_type __len = size() + std::max(size(), __n); return (__len < size() || __len > max_size()) ? max_size() : __len; }

可以得知,第一次 push_back 后,size() == capacity() == 1,第二次为2,后面依次 *2,最大为 size_t(-1)/sizeof(T).
L14 获取需要分配的的空间大小
L16 申请一块新的内存
L19 对新的元素进行构造
L22 对旧的元素,复制/移动构造至新的内存中
L26 对旧的元素进行析构
L28 对旧的空间进行释放
L30-L32 更新底层实现的索引
所以可以看到 vector 的底层实现一定是顺序表,可以在栈上(自己实现分配器)也可以在堆上(默认)。
关于扩容,增长因子为 2,并且有最大大小限制,还考虑了整数溢出的情况。
关于构造函数,每次插入都会有一个复制构造函数的调用
insert 插入元素到容器中的指定位置。
insert 和 push_back 实现差别不大,多了(size() - pos)次复制/移动构造函数
resize 改变容器中可存储元素的个数
这里只看默认初始化新元素值的实现
298void resize(size_type __new_size) { 299if (__new_size > size()) 300_M_default_append(__new_size - size()); 301else if (__new_size < size()) 302_M_erase_at_end(this->_M_impl._M_start + __new_size); 303}525void _M_erase_at_end(pointer __pos) { 526std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator()); 527this->_M_impl._M_finish = __pos; 528}408void vector<_Tp, _Alloc>::_M_default_append(size_type __n) { 409if (__n != 0) { 410if (size_type(this->_M_impl._M_end_of_storage - 411this->_M_impl._M_finish) >= __n) { 412std::__uninitialized_default_n_a(this->_M_impl._M_finish, __n, 413_M_get_Tp_allocator()); 414this->_M_impl._M_finish += __n; 415} else { 416const size_type __len = _M_check_len(__n, "vector::_M_default_append"); 417const size_type __old_size = this->size(); 418pointer __new_start(this->_M_allocate(__len)); 419pointer __new_finish(__new_start); 420try { 421__new_finish = std::__uninitialized_move_if_noexcept_a( 422this->_M_impl._M_start, this->_M_impl._M_finish, __new_start, 423_M_get_Tp_allocator()); 424std::__uninitialized_default_n_a(__new_finish, __n, 425_M_get_Tp_allocator()); 426__new_finish += __n; 427} catch (...) { 428std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator()); 429_M_deallocate(__new_start, __len); 430throw; 431} 432std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 433_M_get_Tp_allocator()); 434_M_deallocate(this->_M_impl._M_start, 435this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 436this->_M_impl._M_start = __new_start; 437this->_M_impl._M_finish = __new_finish; 438this->_M_impl._M_end_of_storage = __new_start + __len; 439} 440} 441}

resize 中也存在三种情况
当需要重置大小等于目前容器的大小时,忽略
当重置大小小于目前容器大小时,处理简单,释放内存,修改 finish 的值
当重置大小大于目前容器大小时:
  1. 当前重置小于等于容器的容量,直接在尾部以默认构造函数额外的元素
  2. 当重置的大小大于容器的容器,和push_back一样,需要先申请内存,再复制/移动元素,再重复1的步骤
    L416-L412 为申请新的内存,并且复制/移动元素
    L424 为在尾部以默认构造函数额外的元素
clear 清除容器内的元素,之后 size() = 0
实现较为简单
521void clear() noexcept { _M_erase_at_end(this->_M_impl._M_start); }525void _M_erase_at_end(pointer __pos) { 526std::_Destroy(__pos, this->_M_impl._M_finish, _M_get_Tp_allocator()); 527this->_M_impl._M_finish = __pos; 528}

reserve 预留存储空间, 增加 vector 的容量到(大于或)等于 new_cap 的值.
实现也比较简单,new_cap 的值大于容器的容量时,进行重新分配,再复制/移动到新的内存中,最后更新底层数据结构
566template 567void vector<_Tp, _Alloc>::reserve(size_type __n) { 568if (__n > this->max_size()) 569__throw_length_error(("vector::reserve")); 570if (this->capacity() < __n) { 571const size_type __old_size = size(); 572pointer __tmp = _M_allocate_and_copy( 573__n, std::__make_move_if_noexcept_iterator(this->_M_impl._M_start), 574std::__make_move_if_noexcept_iterator(this->_M_impl._M_finish)); 575std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, 576_M_get_Tp_allocator()); 577_M_deallocate(this->_M_impl._M_start, 578this->_M_impl._M_end_of_storage - this->_M_impl._M_start); 579this->_M_impl._M_start = __tmp; 580this->_M_impl._M_finish = __tmp + __old_size; 581this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; 582} 583}

shrink_to_fit 请求移除未使用的容量
void shrink_to_fit() { _M_shrink_to_fit(); }template bool vector<_Tp, _Alloc>::_M_shrink_to_fit() { if (capacity() == size()) return false; return std::__shrink_to_fit_aux::_S_do_it(*this); }template struct __shrink_to_fit_aux<_Tp, true> { _Tp(__make_move_if_noexcept_iterator(__c.begin()), __make_move_if_noexcept_iterator(__c.end()), __c.get_allocator()) .swap(__c); return true; };

模板太多看起来费劲,换一种表达
std::vector v; v.push_back(1); // size()=1 capacity()=1 v.push_back(1); // size()=2 capacity()=2 v.push_back(1); // size()=3 capacity()=4std::vector(v.begin(), v.end()).swap(v); // size()=3 capacity()=3

时间复杂度分析
复杂度 方法 说明
\(O(1)\) size() 变量相减
\(O(1)\) capacity() 变量相减
\(O(1)\) push_back() 均摊最坏情况为3
\(O(n)\) insert() 操作需要对size()-pos进行拷贝
\(O(n)\) clear() size() 次析构
\(O(n)\) reserve() 扩容需要size()次拷贝
\(O(n)\) shrink_to_fit() 构造需要size()拷贝,swap()为常数
push_back 复杂度证明 以libstdc++为准备,vector的增长因子为2,分析对一个空的 vector 执行 n 个 push_back 的复杂度。
第 \(i\) 个操作的需要的复制构造次数的 \(c_i\),分为两种情况:
  • size() < capacity(), \(c_i=1\)
  • size() == capacity(),vector 进行扩张,\(c_i=i\)
得到每次的次数为:

\[c_i=\left\{ \begin{aligned} i, & 若 i-1 恰为 2 的幂 \\ 1, & 其他 \end{aligned} \right. \]
n 个 push_back 总的复制构造函数的次数为

\[\sum_{i=1}^nc_i \le n + \sum_{j=0}^{\lfloor lgn \rfloor}2^j \le n+2n = 3n \]
n个push_back的上界为 3n,单一的摊还次数为 3,所以复杂度为 \(O(1)\)

    推荐阅读