C++ 全栈知识体系

第四章：序列式容器 vector

容器的概观与分类

容器，置物之所也。研究数据的特定排列方式，以利于搜寻或排序或其他特殊目的，这一专门学科称为数据结构。几乎可以说，任何特定的数据结构都是为了实现某种特定的算法。

容器分类

SGI STL的各个容器（本图以内缩方式来表达基层与衍生层的关系）。**这里所谓的，并非派生关系，而是内含关系。**例如，heap内含一个vector，priority-queue内含一个heap，stack和queue都内含一个deque，set/map/multiset/multimap都内含一个RB-tree，hash_set/hash_map/hash_multiset/hash_multimap都内含一个hashtabe。

vector概述

vector的数据安排以及操作方式，与array非常相似。两者的唯一差别在于空间的运用的灵活性。array是静态空间，一旦配置了就不能改变；vector的动态空间 ，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。vector的实现技术，关键在于对其大小的控制以及重新配置时的数据移动效率。

vector的内部定义如下：

class vector {
public:
  typedef T value_type;
  typedef value_type* pointer;
  typedef const value_type* const_pointer;
  typedef value_type* iterator;
  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;

protected:
  typedef simple_alloc<value_type, Alloc> data_allocator; // SGI STL 空间配置器接口
  iterator start;               // 表示目前使用空间的头
  iterator finish;              // 表示目前使用空间的尾
  iterator end_of_storage;      // 表示目前可用空间的尾
  void insert_aux(iterator position, const T& x);
  void deallocate() {           // 释放空间
    if (start) data_allocator::deallocate(start, end_of_storage - start);
  }

  void fill_initialize(size_type n, const T& value) {
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
  }
public:
  // 各种迭代器
  iterator begin() { return start; }
  const_iterator begin() const { return start; }
  iterator end() { return finish; }
  const_iterator end() const { return 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、max_size、capacity、empty
  size_type size() const { return size_type(end() - begin()); }
  size_type max_size() const { return size_type(-1) / sizeof(T); }
  size_type capacity() const { return size_type(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); }


  // 构造函数，大都调用 fill_initialize
  vector() : start(0), finish(0), end_of_storage(0) {}
  vector(size_type n, const T& value) { fill_initialize(n, value); }
  vector(int n, const T& value) { fill_initialize(n, value); }
  vector(long n, const T& value) { fill_initialize(n, value); }
  explicit vector(size_type n) { fill_initialize(n, T()); }


  // 析构函数
  ~vector() { 
    destroy(start, finish);
    deallocate();
  }

  // 首尾元素
  reference front() { return *begin(); }
  const_reference front() const { return *begin(); }
  reference back() { return *(end() - 1); }
  const_reference back() const { return *(end() - 1); }

  void push_back(const T& x) {
    if (finish != end_of_storage) {
      construct(finish, x);
      ++finish;
    }
    else
      insert_aux(end(), x);
  }

  // 插入操作
  iterator insert(iterator position, const T& x) {
    size_type n = position - begin();
    if (finish != end_of_storage && position == end()) {
      construct(finish, x);
      ++finish;
    }
    else
      insert_aux(position, x);
    return begin() + n;
  }

  // 删除最尾端元素
  void pop_back() {
    --finish;
    destroy(finish);
  }

  //清除某位置上的元素
  iterator erase(iterator position) {
    if (position + 1 != end())
      copy(position + 1, finish, position); // 后续元素往前移动
    --finish;
    destroy(finish);
    return position;
  }

  // 清除迭代器所指定的区间的元素
  iterator erase(iterator first, iterator last) {
    iterator i = copy(last, finish, first);
    destroy(i, finish);
    finish = finish - (last - first);
    return first;
  }

  // 重新设置 vector 大小，若设置值 new_size 大于当前 size，在尾端插入 x
  void resize(size_type new_size, const T& x) {
    if (new_size < size()) 
      erase(begin() + new_size, end());
    else
      insert(end(), new_size - size(), x);
  }
  void resize(size_type new_size) { resize(new_size, T()); }
  void clear() { erase(begin(), end()); }

protected:
  // 配置空间并填满内容，其中__STL_TRY、__STL_UNWIND 为异常相关的宏，在 stl_config.h 中定义
  iterator allocate_and_fill(size_type n, const T& x) {
    iterator result = data_allocator::allocate(n);
    __STL_TRY {
      uninitialized_fill_n(result, n, x);
      return result;
    }
    __STL_UNWIND(data_allocator::deallocate(result, n));
  }

};
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

# vector 的迭代器

vector 维护的是一个连续的线性空间，所以不论其元素型别如何，普通指针 都可以作为 vector 的迭代器而满足所有必要条件，因为 vector 迭代器所需要的操作行为，如 operator*，operator->，operator++， operator–， operator+，operator-，operator+=， operator-=，普通指针天生就具备。vector 支持随机存取，而普通指针正有这样的能力。所以，vector 提供的是 Random Access Iterators。

template <class T, class Alloc = alloc>
class vector
{
public:
    typedef T             value_type;
    typedef value_type*   iterator;
    ...
}
1
2
3
4
5
6
7
8

根据定义，如果客户端写出这样的代码：

vector<int>::iterator ivite;
vector<Shape>::iterator svite;
1
2

ivite 型别就是 int*，svite 的型别就是 Shape*。

# vector数据结构

vector采用线性连续空间的数据结构。它以两个迭代器start和finish分别指向配置的来的连续空间中目前已被使用的范围，并以迭代器end_of_storage指向整块连续空间（含备用空间）的尾端:

template<class T,class Alloc = alloc>  
class vector{  
...  
protected :  
      iterator start ; //表示目前使用空间的头  
      iterator finish ; // 表示目前使用空间的尾  
      iterator end_of_storage ; //表示目前可用空间的尾  
};
1
2
3
4
5
6
7
8

为了降低空间配置时的速度成本，vector 实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量（capacity）的概念。添加新元素时，如果超出当时的容量，则容量会扩充至两倍，如果两倍容量仍不足，就扩充至足够大的容量。上述容量的扩张必须经历**“重新配置、元素移动、释放空间”**等过程。vector数据插入过程的示意图如下:

vector示意图

vector构造与内存管理

vector缺省使用alloc作为空间配置器，并据此另外定义了一个data_allocator，为的是更方便以元素大小为配置单位：

template<class T, class Alloc = alloc>  
class vector{
protected:
    typedef simple_alloc<value_type,Alloc> data_allocator;
    ...
}
1
2
3
4
5
6

于是，data_allocator::allocate(n)表示配置n个元素空间。

当我们以push_back()将新元素插入vector尾端时，该函数先检查是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器finish，使vector变大。如果没有备用空间，就扩充空间（重新配置、移动数据、释放原空间）：

void push_back(const T& x) {
    if (finish != end_of_storage) {
      construct(finish, x);
      ++finish;
    }
    else
      insert_aux(end(), x);
}

template<class T, class Alloc>  
  void vector<T, Alloc>::insert_aux(iterator position, const T&x){  
      if (finish != end_of_storage){//还有备用空间  
          construct(finish, *(finish - 1)); //在备用空间起始处构造一个元素，以vector最后一个元素值为其初值  
          ++finish; //调整finish迭代器  
          T x_copy = x;  
          copy_backward(position, finish - 2, finish - 1);  
          *position = x_copy;  
      }  
      else{//没有备用空间  
          const size_type old_size = size();  
          const size_type new_size = old_size != 0 ? 2 * old_size : 1;  
          iterator new_start = data_allocator::allocate(new_size);  
          iterator new_finish = new_start;  
          try{  
              new_finish = uninitialized_copy(start, position, new_start);//将原vector的内容拷贝到新vector  
              construct(new_finish, x);  
              ++new_finish;  
              new_finish = uninitialzed_copy(position, finish, new_finish);//将安插点的原内容也拷贝过来  
          }  
          catch (excetion e){  
              destroy(new_start, new_finish);//如果发生异常，析构移动的元素，释放新空间  
              data_allocator::deallocate(new_start, new_size);  
          }//析构并释放原空间  
          destroy(begin(), end());  
          deallocator();  
          start = new_start; //调整迭代器  
          finish = new_finish;  
          end_of_storage = new_start + new_size;//调整迭代器  
      }  
  }
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

补充：

template<class BidirectionalIterator1, class BidirectionalIterator2>
  BidirectionalIterator2 copy_backward ( BidirectionalIterator1 first,
                                         BidirectionalIterator1 last,
                                         BidirectionalIterator2 result);

 参数:

       first, last
       指出被复制的元素的区间范围[first，last).
       result
       指出复制到目标区间的具体位置[result-(last-first),result)

 返回值：

        返回一个迭代器，指出已被复制元素区间的起始位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

所谓动态增加大小，并不是在原空间之后接续空间（因为无法包装原空间之后尚有可配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原来内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。

vector的元素操作

pop_back()实现：

void pop_back(){
      --finish;            //将尾端标记往前移一格，表示放弃尾端元素
      destory(finish);     //finish原来指向容器尾部[strat,finish),--后指向最后一个元素，然后析构
  }
1
2
3
4

erase()实现：

 //清除[first,last]中的所有元素
  iterator erase(iterator first,iterator last){
      iterator i=copy(last,finish,first);
      destroy(i,finish);
      finish=finish-(last-first);
  }
  //清除某个位置上的元素
  iterator erase(iterator position){
      if(position+1!=end())
          copoy(position+1,finish,position);
      --finish;
      destory(finish);
      return position;
  }
  //清除所有元素
  void clear() {erase(begin(),end());}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

copy函数具体实现：

//InputIterator 版本
template<class InputIterator, class OutputIterator>
inline OutputIterator __copy(InputIterator first, InputIterator last, OutputIterator result, input_iterator_tag){
//如果只是 InputIterator 的话，以迭代器赞同与否，决定循环是否继续、速度慢
for( ; first != last; ++result, ++first)
*result = *first;
return result;
}
即

for( ; last != finish; ++first, ++last)
*first = *last;  //即将last开始的元素接到first后面
1
2
3
4
5
6
7
8
9
10
11
12

insert()实现，根据备用空间和插入元素的多少分为以下三种情况：

template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
  // 当 n != 0 才进行以下所有操作
  if (n != 0) {
    // 备用空间大于等于新增元素个数
    if (size_type(end_of_storage - finish) >= n) {
      T x_copy = x;
      const size_type elems_after = finish - position;
      iterator old_finish = finish;
      // 针对插入点后现有元素与新增元素个数的数量采取不同的操作
      // 插入点后现有元素个数大于新增元素个数
      if (elems_after > n) {
        uninitialized_copy(finish - n, finish, finish);
        finish += n;
        copy_backward(position, old_finish - n, old_finish);
        fill(position, position + n, x_copy);
      }
      // 插入点后现有元素个数小于等于新增元素个数
      else {
        uninitialized_fill_n(finish, n - elems_after, x_copy);
        finish += n - elems_after;
        uninitialized_copy(position, old_finish, finish);
        finish += elems_after;
        fill(position, old_finish, x_copy);
      }
    }
    else {
      // 备用空间小于新增元素个数（必须配置额外的内存）
      // 首先决定新长度：旧长度的2倍，或者旧长度+新增元素个数
      const size_type old_size = size();        
      const size_type len = old_size + max(old_size, n);
      // 配置新的 vector 空间
      iterator new_start = data_allocator::allocate(len);
      iterator new_finish = new_start;
      __STL_TRY {
        new_finish = uninitialized_copy(start, position, new_start);
        new_finish = uninitialized_fill_n(new_finish, n, x);
        new_finish = uninitialized_copy(position, finish, new_finish);
      }
#         ifdef  __STL_USE_EXCEPTIONS 
      catch(...) {
        // 如有异常发生，实现 commit or rollback 语义
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
      }
#         endif /* __STL_USE_EXCEPTIONS */
      // 清除并释放旧的 vector
      destroy(start, finish);
      deallocate();
      // 调整迭代器
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}
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
51
52
53
54
55
56
57

insert-1

insert-2

insert-3

← 第四章：序列式容器 list →