STL 序列容器

2020年6月5日星期四, 发表于深圳

如果你对本文有任何的建议或者疑问, 可以在这里给我提 Issues, 谢谢! :)

STL 序列容器在工作中使用的频次很高，最近在回顾 «STL源码剖析» 的过程中，再次熟悉一下STL序列容器的实现原理，并且记录一下

1. vector
2. list

1. vector

1.1 vector类声明

// 默认走这里，vector base 构造函数和析构函数
// vector 继承 _Vector_base
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; // 表示目前可用空间的尾

  // simple_alloc 是 SGI STL 的空间配置器
  typedef simple_alloc<_Tp, _Alloc> _M_data_allocator;  // 以元素大小为配置单位
  _Tp* _M_allocate(size_t __n)
    { return _M_data_allocator::allocate(__n); }
  void _M_deallocate(_Tp* __p, size_t __n) 
    { _M_data_allocator::deallocate(__p, __n); }
};

vector使用连续空间，使用start, finish, end_of_storage来表示空间的头，使用空间的尾，可用空间的尾。

vector在使用的时候，分配的空间通常比暂时要用的空间多，在后续有新元素加入进去的时候，可以不用重新分配空间，如果使用元素空间超过当前分配超过空间，需要

分配新的空间，一般空间容量是目前空间容量的的两倍
将所有的元素从旧的空间拷贝到新空间
销毁掉旧空间的对象
回收旧的空间

1.2 vector的insert操作

push_back实际上是调动的 insert操作 , 学习一下insert的源代码

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;
    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;
  }
}

如果可用空间还有剩余，调用 copy_backward 拷贝position后面的元素到下一个位置， stl实现的比较巧妙的是从后向前拷贝
如果容量没有剩余，可需要进行 1.1中说的4步操作，构造，拷贝，析构，清理空间，其中拷贝是分两部分拷贝

1.3 vector的erase操作

earse函数的声明如下：

  // 清除某个位置上的元素
  iterator erase(iterator __position) {
    if (__position + 1 != end())
      copy(__position + 1, _M_finish, __position); // 全局函数
    --_M_finish;
    destroy(_M_finish);
    return __position;
  }
  
  // 清除 [first, last) 中的所有元素
  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;
  }

erase函数会将其他位置的元素copy前一个位置，然后析构掉最后一个位置的元素

2. list

STL 中List仅仅使用一个指针，就可以完整的表现整个链表, 真的太巧妙了。

iterator begin()           { return (_Node*)(_M_node->_M_next); }
iterator end()             { return _M_node; }
bool empty() const         { return _M_node->_M_next == _M_node; }

2.1 list的insert操作

insert操作的关键在于如何桥接前后两个双向链表，因为固定有一个_M_node节点，所以少了很多前后判断空指针的操作

  // 在 __position 位置前，插入元素 __x
  iterator insert(iterator __position, const _Tp& __x) {
    _Node* __tmp = _M_create_node(__x);
    __tmp->_M_next = __position._M_node;  // list为双向链表
    __tmp->_M_prev = __position._M_node->_M_prev;
    __position._M_node->_M_prev->_M_next = __tmp;
    __position._M_node->_M_prev = __tmp;
    return __tmp;
  }

2.2 list的erase操作

删除其实实现也比较简洁，获取前后节点，进行连接

  // 移除迭代器 position 所指节点
  iterator erase(iterator __position) {
    _List_node_base* __next_node = __position._M_node->_M_next;
    _List_node_base* __prev_node = __position._M_node->_M_prev;
    _Node* __n = (_Node*) __position._M_node;
    __prev_node->_M_next = __next_node;
    __next_node->_M_prev = __prev_node;
    _Destroy(&__n->_M_data);
    _M_put_node(__n);
    return iterator((_Node*) __next_node);
  }

2.3 list的splice操作

splice操作用来连接两个链表

  // 将 [first, last) 内所有元素接合于 __position 所指位置之前
void splice(iterator __position, list&, iterator __first, iterator __last) 
{
    if (__first != __last) 
    this->transfer(__position, __first, __last);
}
    // 将 [first, last) 内的所有元素移动到 position 之前
void transfer(iterator __position, iterator __first, iterator __last) 
{
    if (__position != __last) {
      // Remove [first, last) from its old position.
      __last._M_node->_M_prev->_M_next     = __position._M_node;
      __first._M_node->_M_prev->_M_next    = __last._M_node;
      __position._M_node->_M_prev->_M_next = __first._M_node; 

      // Splice [first, last) into its new position.
      _List_node_base* __tmp      = __position._M_node->_M_prev;
      __position._M_node->_M_prev = __last._M_node->_M_prev;
      __last._M_node->_M_prev     = __first._M_node->_M_prev; 
      __first._M_node->_M_prev    = __tmp;
    }
  }

关键是在于处理，前后的两个部分链接，注意到 last是开区间

2.4 list的merge操作

// 将 __x 合并到 *this 身上，两个 list 的内容都已经经过递增排序，最终合并后是一个递增排序链表
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::merge(list<_Tp, _Alloc>& __x)
{
  iterator __first1 = begin();
  iterator __last1 = end();
  iterator __first2 = __x.begin();
  iterator __last2 = __x.end();
  while (__first1 != __last1 && __first2 != __last2)
    if (*__first2 < *__first1) {
      iterator __next = __first2;
      transfer(__first1, __first2, ++__next);
      __first2 = __next;
    }
    else
      ++__first1;
  if (__first2 != __last2) transfer(__last1, __first2, __last2); // 将剩余的list2连接到list1上
}

2.5 list的sort操作

list 自己封装了sort操作

// quick sort
template <class _Tp, class _Alloc>
void list<_Tp, _Alloc>::sort()
{
  // Do nothing if the list has length 0 or 1.
  if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) {
    list<_Tp, _Alloc> __carry;
    list<_Tp, _Alloc> __counter[64];
    int __fill = 0;
    while (!empty()) {
      __carry.splice(__carry.begin(), *this, begin());
      int __i = 0;
      while(__i < __fill && !__counter[__i].empty()) {
        __counter[__i].merge(__carry);
        __carry.swap(__counter[__i++]);
      }
      __carry.swap(__counter[__i]);         
      if (__i == __fill) ++__fill;
    } 

    for (int __i = 1; __i < __fill; ++__i)
      __counter[__i].merge(__counter[__i-1]);
    swap(__counter[__fill-1]);
  }
}

illx10000

青春不是年华，而是心境