STL源码笔记（12）—序列式容器之deque（二）

╰+攻爆jí腚メ 2022-08-21 07:57 5阅读 0赞

# STL源码笔记（12）—序列式容器之deque（二） #

## 再谈deque数据结构 ##

我们知道deque是通过map管理很多个互相独立连续空间，由于对deque\_iterator的特殊设计，使得在使用的时候就好像连续一样。有了deque\_iterator的基础（例如重载的操作符等），对于我们实现容器的一些方法就十分方便了。与vector一样，deque也维护一个start，和finish两个迭代器，start指向容器中的一个元素，finish指向最后一个元素的后一个位置（前闭后开），从微观上讲，start指向map管理的第一个缓冲的第一个元素，finish管理最后一个缓冲的某一个元素（该元素是整个容器的最后一个元素）的后一个位置。  
在STL源码中，这些指针由基类定义，并在子类中直接使用。

template <class _Tp, class _Alloc>
    class _Deque_base {
       //基类
    public:
      typedef _Deque_iterator<_Tp,_Tp&,_Tp*>             iterator;
      typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
      //...
      //...
    protected:
      iterator _M_start;//start指针
      iterator _M_finish;//finish指针
    };
    
    //-----------------------分割线-----------------
    template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    class deque : protected _Deque_base<_Tp, _Alloc> {
       //子类
      typedef _Deque_base<_Tp, _Alloc> _Base;
    public:                         // Iterators
      typedef typename _Base::iterator       iterator;
      typedef typename _Base::const_iterator const_iterator;
    
    protected:
      using _Base::_M_map;//map 管理器
      using _Base::_M_map_size;
      using _Base::_M_start;//start指针
      using _Base::_M_finish;//finish指针

有了上述基础，在deque中定义的很多函数就可以轻松完成（很多操作都在deque\_iterator中做了）

iterator begin() { return _M_start; }//返回第一个元素的地址的左值
      iterator end() { return _M_finish; }//返回最后一个元素地址的后一个位置的左值
      const_iterator begin() const { return _M_start; }//const 版本
      const_iterator end() const { return _M_finish; }//const 版本
      //---------------------分割线-----------------------------------------------
      reference front() { return *_M_start; }//返回第一个元素的左值
      reference back() {
       //返回最后一元素的左值，（这里要把原迭代器向前移动一个位置）
        iterator __tmp = _M_finish;
        --__tmp;
        return *__tmp;
      }
      //注释：在书中提到为何不用*(_M_finish-1)来返回，因为对于deque_iterator来说，并没有重载这种类型的操作符，但事实上：存在
    
      _Self operator-(difference_type __n) const {
        _Self __tmp = *this;
        return __tmp -= __n;//直接使用重载的-=
      }
    
      const_reference front() const { return *_M_start; }//const 版本
      const_reference back() const {
       //const 版本
        const_iterator __tmp = _M_finish;
        --__tmp;
        return *__tmp;
      }
      //===================分割线=====================
      size_type size() const { return _M_finish - _M_start; }
      size_type max_size() const { return size_type(-1); }
      bool empty() const { return _M_finish == _M_start; }

## deque的构造与内存管理 ##

### deque数据结构 ###

书中给出`4deque-test.cpp`示例，提到缓冲区的大小为32bytes，这里在侯老师的代码中实际给出：

deque<int,alloc,8>ideq(20,9);

模板实参8表示缓冲区大小为8个元素，由于这里是int型（4字节）的，所以大小为`8*sizeof(int)=32bytes`。  
而上述另一个模板实参就是空间配置器了。（不过书中这种写法说的是在G++环境下，切换到Ubuntu下也不行，可能是g++版本的原因）  
在源码中定义空间配置器的方式与vector类似，都是通过simple\_alloc进行转发，也是在deque的基类中进行定义，子类中使用。

template <class _Tp, class _Alloc>
    class _Deque_base {
       //基类
    //...
    typedef _Alloc allocator_type;//空间分配器型别
    typedef simple_alloc<_Tp, _Alloc>  _Node_alloc_type;
    typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type;
    _Tp* _M_allocate_node()//申请缓冲空间
        { return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp))); }
    void _M_deallocate_node(_Tp* __p)//释放
        { _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp))); }
    _Tp** _M_allocate_map(size_t __n) //申请管理map的空间
        { return _Map_alloc_type::allocate(__n); }
    void _M_deallocate_map(_Tp** __p, size_t __n) //释放
        { _Map_alloc_type::deallocate(__p, __n); }
    
    protected:
      void _M_initialize_map(size_t);
      void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
      void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
    //...
    };
    
    //=================>分割线<========================
    template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    class deque : protected _Deque_base<_Tp, _Alloc> {
      //...
      typedef _Deque_base<_Tp, _Alloc> _Base;
      typedef typename _Base::allocator_type allocator_type;
      allocator_type get_allocator() const { return _Base::get_allocator(); }
      using _Base::_M_initialize_map;
      using _Base::_M_create_nodes;
      using _Base::_M_destroy_nodes;
    
      using _Base::_M_allocate_node;
      using _Base::_M_deallocate_node;
      using _Base::_M_allocate_map;
      using _Base::_M_deallocate_map;
      //...
    };

### deque构造器详解 ###

万事俱备，现在要将上述定义的指针啊，空间配置器什么的用起来，产生并安排好deque的结构——deque的constructor构造器：  
与之前提到的很多东西一样，也是在基类中实现，构造函数除了初始化指针外，还要为deque“安排空间”，这里就需要用到空间配置器的东西了（上面的代码中早已做好了封装），书中提供`create_map_and_nodes`方法，在SGI STL源码中有这样一个函数：

//该函数的实现细节书中几乎一致，我在其中也做了一些注释
    template <class _Tp, class _Alloc>//该模板函数在构造函数中调用
    void
    _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
    {
      //需要的节点数=(元素个数/每个缓冲区的大小) +1
      //如果刚好整除就多分配一个节点
      size_t __num_nodes = 
        __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
    
        //一个map要管理多少个节点（想象一下就是指针数组的“行”）
        //最少是8个，最多是“所需要的节点加2”（预留）
        //enum { _S_initial_map_size = 8 };就体现了最少
      _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
      _M_map = _M_allocate_map(_M_map_size);//分配空间，具有_M_map_size个节点
    
      //由于map会多2个节点的备用空间，这里两个指针指向map实际使用的首尾位置
      //也就是说，在首部多一个空闲节点，尾部多一个空闲节点
      _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
      _Tp** __nfinish = __nstart + __num_nodes;//这里在侯老师的书中还要减1（小细节，就是区间取闭区间和开区间的区别）
    
        /*
        STL_TRY
        STL_UNWIND
        就是实现try catch的功能
        */
    
    
      __STL_TRY {
          //为现用的（不包含备用的）节点配置缓冲区。
        _M_create_nodes(__nstart, __nfinish);//因为[__nstart,__nfinish)正是现用的区间嘛
      }
      __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size), 
                    _M_map = 0, _M_map_size = 0));//try catch block如果不成功则一个都不留
        //以下配置迭代器（deque_iterator）以及迭代器中访问数据和管理缓冲区的指针
      _M_start._M_set_node(__nstart);//设置_M_start迭代器中的三个指针（管理缓冲区的节点地址，缓冲区的起点，缓冲区的终点）
      _M_finish._M_set_node(__nfinish - 1);//设置_M_finish迭代器中的三个指针
      _M_start._M_cur = _M_start._M_first;//设置指向当前元素值指针
      _M_finish._M_cur = _M_finish._M_first +
                   __num_elements % __deque_buf_size(sizeof(_Tp));//设置指向最后一个元素元素指针
    }
    
    //====================>分割线<=====================
    template <class _Tp, class _Alloc>
    void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
    {
      _Tp** __cur;
      __STL_TRY {
        for (__cur = __nstart; __cur < __nfinish; ++__cur)//侯书中__cur<=__nfinish
          *__cur = _M_allocate_node();//分配缓冲区，大小为 512/sizeof(T);T为型别
          //就是为每个map节点指针分配固定大小的缓冲区
      }
      __STL_UNWIND(_M_destroy_nodes(__nstart, __cur));//如果不成功则一个都不留（其实就是try catch block）
    }

### deque空间管理 ###

其实就是由于Deque双向开口的特性，提供push\_back()和push\_front()两个操作，又由于这里deque实际上是由多个缓冲区和中控map来模拟连续空间，所以在添加构造元素的时要考虑当前缓冲区是否还够用，如果不够用了就得将中控map的节点指针向后（push\_back）或者向前（push\_front）挪动一小格，当然若连中控map也没有足够的节点来扩充了，还需要重新整治一下map。

void push_back(const value_type& __t) {
        if (_M_finish._M_cur != _M_finish._M_last - 1) {
          construct(_M_finish._M_cur, __t);//当前缓冲区还有空间，直接构造
          ++_M_finish._M_cur;
        }
        else
          _M_push_back_aux(__t);//当前缓冲区空间不足，需要map挪一个节点。
      }
    
    // Called only if _M_finish._M_cur == _M_finish._M_last - 1.
    //缓冲被填满
    template <class _Tp, class _Alloc>
    void deque<_Tp,_Alloc>::_M_push_back_aux(const value_type& __t)
    {
      value_type __t_copy = __t;
      _M_reserve_map_at_back();//这个用来判断是否需要扩充map
      *(_M_finish._M_node + 1) = _M_allocate_node();//先为后一个节点分配空间
      __STL_TRY {
        construct(_M_finish._M_cur, __t_copy);//构造，这里当前缓冲还剩最后一个位置
        _M_finish._M_set_node(_M_finish._M_node + 1);//当前缓冲区用完，更换节点
        _M_finish._M_cur = _M_finish._M_first;//更换指针
      }
      __STL_UNWIND(_M_deallocate_node(*(_M_finish._M_node + 1)));//若失败则一个不留
    }
    
    //----------------->分割线<---------------------------------
    void push_front(const value_type& __t) {
        if (_M_start._M_cur != _M_start._M_first) {
       //当前缓冲足够
          construct(_M_start._M_cur - 1, __t);//直接往前构造
          --_M_start._M_cur;//更新指针
        }
        else
          _M_push_front_aux(__t);//需要往前挪动一个指针
      }
    template <class _Tp, class _Alloc>
    void  deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
    {
      value_type __t_copy = __t;
      _M_reserve_map_at_front();
      *(_M_start._M_node - 1) = _M_allocate_node();//先在前一个map节点处构造缓冲区
      __STL_TRY {
        _M_start._M_set_node(_M_start._M_node - 1);//设置新的节点
        _M_start._M_cur = _M_start._M_last - 1;//设置新的指针
        construct(_M_start._M_cur, __t_copy);//构造新节点
      }
      __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
    }

上述有两个关键操作（实际是一个效果），**就是扩充map节点**。`_M_reserve_map_at_front()&_M_reserve_map_at_back()`而里面的实际操作却是由`_M_reallocate_map()`实现

void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
        if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
        //map尾端节点备用空间不够
          _M_reallocate_map(__nodes_to_add, false);//配置更大的，拷贝，释放原来的
      }

当然对应的又`pop_back()`和`pop_front()`与在前端和后端插入类似，这里必须要判断是否需要释放整个缓冲区。

除了在首尾插入删除元素，deque还有一些常见的方法比如clear()、erase()、insert()等

//clear()
    template <class _Tp, class _Alloc> 
    void deque<_Tp,_Alloc>::clear()
    {
      for (_Map_pointer __node = _M_start._M_node + 1;
           __node < _M_finish._M_node;
           ++__node) {
        destroy(*__node, *__node + _S_buffer_size());
        _M_deallocate_node(*__node);
      }//先删除首尾节点之外的缓冲区域
    
      if (_M_start._M_node != _M_finish._M_node) {
       //包含首尾节点还有两个缓冲
        destroy(_M_start._M_cur, _M_start._M_last);//删除头迭代器缓冲所有元素
        destroy(_M_finish._M_first, _M_finish._M_cur);//删除尾迭代器缓冲所有元素
        _M_deallocate_node(_M_finish._M_first);//只释放一个缓冲
      }
      else//只剩下一个缓冲，此时首尾指向同一个节点
        destroy(_M_start._M_cur, _M_finish._M_cur);//将所有元素析构，但是保留缓冲
    
      _M_finish = _M_start;//调整状态
    }

//erase()删除单个元素的版本
    iterator erase(iterator __pos) {
        iterator __next = __pos;
        ++__next;
        difference_type __index = __pos - _M_start;//清除点之前的元素个数
        if (size_type(__index) < (this->size() >> 1)) {如果清除点之前的元素比较少
          copy_backward(_M_start, __pos, __next);//从后往前复制（此时待删除元素已经被覆盖）
          pop_front();//弹出第一个冗余元素
        }
        else {
          copy(__next, _M_finish, __pos);//从前往后复制
          pop_back();//待删除元素已经被覆盖
        }
        return _M_start + __index;//返回删除位置
      }
    
    //============>>分割线<<========================
    
    //earse()迭代器版本
    template <class _Tp, class _Alloc>
    typename deque<_Tp,_Alloc>::iterator 
    deque<_Tp,_Alloc>::erase(iterator __first, iterator __last)
    {
      if (__first == _M_start && __last == _M_finish) {
        clear();//是否是清空全部
        return _M_finish;
      }
      else {
        difference_type __n = __last - __first;//清除区间的长度
        difference_type __elems_before = __first - _M_start;//清除区间前方的元素个数
        if (__elems_before < difference_type((this->size() - __n) / 2)) {
       //前方元素比较少
          copy_backward(_M_start, __first, __last);//把前方元素拷贝到待删除区间的last之前
          iterator __new_start = _M_start + __n;//计算新的起点
          destroy(_M_start, __new_start);//析构冗余元素
          _M_destroy_nodes(__new_start._M_node, _M_start._M_node);//删除冗余缓冲区
          _M_start = __new_start;//设置新的起点
        }
        else {
       //后方元素比较少
          copy(__last, _M_finish, __first);
          iterator __new_finish = _M_finish - __n;
          destroy(__new_finish, _M_finish);
          _M_destroy_nodes(__new_finish._M_node + 1, _M_finish._M_node + 1);
          _M_finish = __new_finish;
        }
        return _M_start + __elems_before;
      }
    }

iterator insert(iterator position, const value_type& __x) {
        if (position._M_cur == _M_start._M_cur) {
       //如果插入点在最前端
          push_front(__x);//直接push_front()
          return _M_start;
        }
        else if (position._M_cur == _M_finish._M_cur) {
       //插入点最后端
          push_back(__x);//直接push_back()
          iterator __tmp = _M_finish;
          --__tmp;
          return __tmp;
        }
        else {
          return _M_insert_aux(position, __x);
        }
      }
    //===========>>分割线<<=====================
    template <class _Tp, class _Alloc>
    typename deque<_Tp, _Alloc>::iterator
    deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
    {
      difference_type __index = __pos - _M_start;//插入点之前的元素个数
      value_type __x_copy = __x;
      if (size_type(__index) < this->size() / 2) {
       //比较少
        push_front(front());//在最前端先插入一个元素
        iterator __front1 = _M_start;//标记
        ++__front1;
        iterator __front2 = __front1;
        ++__front2;
        __pos = _M_start + __index;
        iterator __pos1 = __pos;
        ++__pos1;
        copy(__front2, __pos1, __front1);//元素移动，实际是把冗余的首元素覆盖
      }
      else {
       //比较多
        push_back(back());
        iterator __back1 = _M_finish;
        --__back1;
        iterator __back2 = __back1;
        --__back2;
        __pos = _M_start + __index;
        copy_backward(__pos, __back2, __back1);
      }
      *__pos = __x_copy;//将多出来的位置赋值
      return __pos;
    }