STL之Vector

Posted on | Edited on

vector是STL中最常用的序列式容器，vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容乃新元素

vector的实现技术，关键在于对大小的控制以及重新配置时的数据移动效率

vector概览

1
2
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc>

可以看到，vector依赖于_Vector_base，其使用的空间配置器_Alloc依赖于stl_config.h中的配置

1
2
3
4
5
6
7
# ifndef __STL_DEFAULT_ALLOCATOR
#   ifdef __STL_USE_STD_ALLOCATORS
#     define __STL_DEFAULT_ALLOCATOR(T) allocator< T >
#   else
#     define __STL_DEFAULT_ALLOCATOR(T) alloc
#   endif
# endif

vector的迭代器

vector提供的是Random Access Iterator,普通指针就具备这种条件

vector的数据结构

vector使用两个iterator指向头部和尾部，指向尾部的包含指向可用空间的尾部和当前空间的尾部

1
2
3
_Tp* _M_start;
_Tp* _M_finish; //当前空间的尾部
_Tp* _M_end_of_storage; //可用空间的尾部

下面给出的begin和end获取的迭代器就是以上定义的指针

1
2
3
4
iterator begin() { return _M_start; }
const_iterator begin() const { return _M_start; }
iterator end() { return _M_finish; }
const_iterator end() const { return _M_finish; }

对于_M_end_of_storage,则是判断是否需要重新分配内存的依据

1
2
3
4
5
6
7
8
void push_back(const _Tp& __x) {
    if (_M_finish != _M_end_of_storage) { //是否有可用空间
      construct(_M_finish, __x); //在_M_finish所指向的位置上构造__x
      ++_M_finish;
    }
    else
      _M_insert_aux(end(), __x);//无可用空间，进入处理函数
  }

vector的空间管理

如果无可用空间，就会交给_M_insert_aux处理

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
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, _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; //如果vector为空，则配置一个元素大小的空间，如果不为空，就配置两倍于旧vector大小的空间
    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;
  }
}

从上面可以看出，所谓的动态分配不过是再次申请，因此对于vector的操作，一旦引起重新分配，iterator就会失效

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
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);
    destroy(__i, _M_finish);
    _M_finish = _M_finish - (__last - __first);
    return __first;
}
void resize(size_type __new_size, const _Tp& __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, _Tp()); }
void clear() { erase(begin(), end()); }

以上的都是比较简单的元素操作，大抵是进行拷贝，析构，调整边界之类的

不过insert就会比较复杂

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
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) {
      //检查空间够不够
    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;
    }
  }
}