STL 源码剖析

发表于 分类于 ， 阅读次数： Waline： 本文字数： 4.5k 阅读时长 ≈ 4 分钟

源码推荐读SGI STL源码，可以自行下载

SGI STL

这里我从容器开始看起，不要太关注allocator和Iterators等细节，而去关注数据结构和算法的实现。

学习完一遍容器后再回来学。

STL 六大组件的交互关系：容器通过配置器取得数据存储空间，算法通过迭代器存取容器内容，仿函数可以协助算法完成不同的策略变化，配接器可以修饰或套接仿函数。

容器

容器分为序列式容器和关联器容器

序列式容器

所谓序列式容器，其中的元素都可序，但未必有序。

vector

vector与array非常相似。array是静态空间，一旦配置了就不能改变；如果满了想换个更大的，首先要配置一块新空间，然后将元素从旧址一一搬往新地址，再把原来的空间释放给系统。vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。

  • vector 与 array 唯一区别是空间的运用的灵活性。
  • array 是静态空间，一旦配置了就不能改变。
  • vector 维护的是一个连续线性空间，所以不论其元素类型为何，普通指针都可以作为 vector 的迭代器而满足所有必要条件。
  • 增加新元素，如果超过当时的容量，则容量会扩充至两倍。
  • <stl_vector.h> 会调用 <stl_bvector.h> 的函数。

vector 上的常见操作复杂度

  • 随机访问——常数 O(1)
  • 在末尾插入或移除元素——均摊常数 O(1)
  • 插入或移除元素到 vector 结尾的距离成线性 O(n)

vector 的迭代器涵盖了指针所有的算术能力(operator*，operator->，operator++，operator--，operator+，operator-，operator+=，operator-=)， 同时 vector 支持随机存取，所以 vector 提供是 Random Access Iterator。

平时我们使用vector时，声明如下：

1
2
3
std::vector<int> vec0;
std::vector<int> vec1(10);
std::vector<int> vec2(10, 1);

那么它们是如何在源码中定义的，我们看下源码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

template <class _Tp, class _Alloc> 
class _Vector_base {
public:
  typedef _Alloc allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }

  // 初始化
  _Vector_base(const _Alloc&)
    : _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
  // 初始化，分配空间
  _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;
  }
	
  // 析构函数， 释放空间
  ~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }

protected:
  _Tp* _M_start;						// 表示目前使用空间的头
  _Tp* _M_finish;						// 表示目前使用空间的尾
  _Tp* _M_end_of_storage;		// 表示目前可用空间的尾

...
  
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> 
{
  // requirements:

  __STL_CLASS_REQUIRES(_Tp, _Assignable);

private:
  typedef _Vector_base<_Tp, _Alloc> _Base;
public:
  // vector 的嵌套类型定义
  typedef _Tp value_type;
  typedef value_type* pointer;  
  typedef const value_type* const_pointer;
  typedef value_type* iterator; // vector 的迭代器是普通指针
  typedef const value_type* const_iterator;
  typedef value_type& reference;
  typedef const value_type& const_reference;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
...

可以看到vector 是继承_Vector_base

vec0 是通过默认构造函数进行初始化，vec1通过_Vector_base(const _Alloc&)来初始化为0，vec2则先初始化为0，然后再赋值

基本函数实现

** 1. 构造函数**

  • vector()：创建一个空的vector
  • vector(int nSize)：创建一个vector,元素个数为nSize
  • vector(int nSize, const t& t):创建一个vector,元素个数为nSize，且值均为t
  • vector(const vector&):复制构造函数
  • vector(begin, end):复制[begin, end]区间内另一个数组的元素到vector中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 // 构造拥有 n 个有值 value 的元素的容器
  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()); }
  
  // 拷贝构造，构造拥有 __x 内容的容器
  vector(const vector<_Tp, _Alloc>& __x) 
    : _Base(__x.size(), __x.get_allocator())
    { _M_finish = uninitialized_copy(__x.begin(), __x.end(), _M_start); }

#ifdef __STL_MEMBER_TEMPLATES
  // Check whether it's an integral type.  If so, it's not an iterator.
  // 构造拥有范围 [first, last) 内容的容器。
  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);
  }

  template <class _InputIterator>
  void _M_initialize_aux(_InputIterator __first, _InputIterator __last,
                         __false_type) {
    _M_range_initialize(__first, __last, __ITERATOR_CATEGORY(__first));
  }

#else
  vector(const _Tp* __first, const _Tp* __last,
         const allocator_type& __a = allocator_type())
    : _Base(__last - __first, __a) 
    { _M_finish = uninitialized_copy(__first, __last, _M_start); }
#endif /* __STL_MEMBER_TEMPLATES */