STL源码笔记（11）—序列式容器之deque（一）

柔光的暖阳◎ 2022-07-30 19:30 37阅读 0赞

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

deque是一种双向开口的连续线性空间，他可以在常量时间内对**头部和尾部**进行插入和移除操作。事实上Deque在宏观逻辑上看是一个连续的空间（类似vector），其实是动态地以分段连续的空间组合而成，这样要维护这个宏观逻辑上的连续性，其代价就是复杂的迭代器架构。由于deque的分段连续性，对deque的排序操作，为了提高效率可以先将deque复制到一个vector，让vector排序后在复制回deque。

## Deque数据结构 ##

看起来有点像链表数组，即一个map作为主控（存放指针的数组），map的每个元素都指向固定大小的连续线性空间叫做缓冲区，默认是512 bytes大小，事实上，如果用户传入小于512Bytes，会做相关的处理：

//>=512则返回1,<512则返回n，其中n*__size=512
    inline size_t __deque_buf_size(size_t __size) {
      return __size < 512 ? size_t(512 / __size) : size_t(1);
    }

我们声明一个链表数组时，通常是这样一个形式：

int *p=new int[4];
    int *a[4];
    a[0]=p;

相较于固定大小的数组形式，在为了方便当map的使用率满载，需要reallocate的时候，这里使用二维指针来表示：

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    class deque : protected _Deque_base<_Tp, _Alloc> {
    public:
      typedef _Tp value_type;
      typedef value_type* pointer;
    protected:                      // Internal typedefs
      typedef pointer* _Map_pointer;//二维指针类型
    };

这里只是一个数据类型的定义，在侯老师的书中为了简便起见，直接使用下述语句定义寻址连续空间的二维指针：

Map_pointer map;

在SGI STL源码中，是通过基类中的一些设计来实现的：

template <class _Tp, class _Alloc>
    class _Deque_base {
       //基类
    //...
    protected:
      _Tp** _M_map;//二维指针
      size_t _M_map_size;  
    //...
    };
    
    template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
    class deque : protected _Deque_base<_Tp, _Alloc> {
    typedef _Deque_base<_Tp, _Alloc> _Base;在子类中定义
    //...
    //在子类中使用
    using _Base::_M_map;
    using _Base::_M_map_size;
    }

## deque的迭代器 ##

deque是分段连续空间，通过迭代器的设计可以让他看起来像是连续空间，这就要设计一个特定的迭代器了。例如deque的迭代器示意图，书中设定的buffer是8，实际上buffer是通过待存储的元素的大小决定的，比如说如果存储int型，则大小就是512/4 = 128  
书中的一个图示，源码中的函数都可以通过该图示简单的计算：

![这里写图片描述][20160419232343281]

而关键又在于operator++和operator–这两个操作符的重载了，仔细研究SGI STL的源码发现其设计确实精妙，并且也不是那么晦涩难懂。

//stl_deque.h
    //计算buffer的大小
    inline size_t __deque_buf_size(size_t __size) {
      return __size < 512 ? size_t(512 / __size) : size_t(1);
    }
    template <class _Tp, class _Ref, class _Ptr>
    struct _Deque_iterator {
      typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;//迭代器本身型别
      typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
      static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }//计算buffer的长度
    
      //迭代器必须要求的几个要素
      typedef random_access_iterator_tag iterator_category;//迭代器型别（1）
      typedef _Tp value_type;//元素型别（2）
      typedef _Ptr pointer;//指针（3）
      typedef _Ref reference;//引用（4）
      typedef size_t size_type;
      typedef ptrdiff_t difference_type;//表示迭代器之间距离的型别（5）
      typedef _Tp** _Map_pointer;//管理主控map的指针型别
    
      typedef _Deque_iterator _Self;
    
      _Tp* _M_cur;//该指针指向迭代器所指向的缓冲区当前元素
      _Tp* _M_first;//该指针指向迭代器所指向的元素所在的缓冲区的头
      _Tp* _M_last;//该指针指向迭代器所指向的元素所在的缓冲区的尾
      _Map_pointer _M_node;//管理主控的map
    
    /*构造函数，主要是进行几个指针的初始化*/
      _Deque_iterator(_Tp* __x, _Map_pointer __y) 
        : _M_cur(__x), _M_first(*__y),
          _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
      _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
      _Deque_iterator(const iterator& __x)
        : _M_cur(__x._M_cur), _M_first(__x._M_first), 
          _M_last(__x._M_last), _M_node(__x._M_node) {}
    
      reference operator*() const { return *_M_cur; }//返回元素的左值
      pointer operator->() const { return _M_cur; }//范围元素的地址的左值
    
    
      difference_type operator-(const _Self& __x) const {
       //计算俩迭代器的距离
        return difference_type(_S_buffer_size()) * (_M_node - __x._M_node - 1) +
          (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
      }//
    
      _Self& operator++() {
       //前置自增
        ++_M_cur;//先到下一个元素
        if (_M_cur == _M_last) {
       //已经到了当前buff的尾部（仍然是前闭后开的原则）
          _M_set_node(_M_node + 1);
          _M_cur = _M_first;
        }
        return *this; 
      }
      _Self operator++(int)  {
       //后置自增，直接调用前置自增（这种后置自增符重载调用前置自增的都是一致的）
        _Self __tmp = *this;
        ++*this;
        return __tmp;
      }
    
      //以下自减符类似
      _Self& operator--() {
        if (_M_cur == _M_first) {
       //先判断，也是因为前闭后开
          _M_set_node(_M_node - 1);
          _M_cur = _M_last;
        }
        --_M_cur;
        return *this;
      }
      _Self operator--(int) {
        _Self __tmp = *this;
        --*this;
        return __tmp;
      }
    
      _Self& operator+=(difference_type __n)
      {
        difference_type __offset = __n + (_M_cur - _M_first);
        if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))//还没有超过buffer的范围
          _M_cur += __n;
        else {
       //超过之后需要跳到下__node_offset个节点，也可能是上__node_offset个节点
          difference_type __node_offset =
            __offset > 0 ? __offset / difference_type(_S_buffer_size())
                       : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
          _M_set_node(_M_node + __node_offset);//新的节点
          _M_cur = _M_first + 
            (__offset - __node_offset * difference_type(_S_buffer_size()));//计算当前位置
        }
        return *this;
      }
    
      _Self operator+(difference_type __n) const
      {
        _Self __tmp = *this;
        return __tmp += __n;//调用+=的操作符重载
      }
    
      _Self& operator-=(difference_type __n) { return *this += -__n; }
    
      _Self operator-(difference_type __n) const {
        _Self __tmp = *this;
        return __tmp -= __n;
      }
    
    //以前不知道迭代器也有元素索引访问的重载，试了一下确实可以。
    //*this获取当前对象
    //*this+__n则调用了重载的+号进而调用重载的+=符号
    //最后*(*this + __n)使用了重载的*号
      reference operator[](difference_type __n) const { return *(*this + __n); }
    
    //指针位置的判断
      bool operator==(const _Self& __x) const { return _M_cur == __x._M_cur; }
      bool operator!=(const _Self& __x) const { return !(*this == __x); }
      bool operator<(const _Self& __x) const {
        return (_M_node == __x._M_node) ? 
          (_M_cur < __x._M_cur) : (_M_node < __x._M_node);
      }
      bool operator>(const _Self& __x) const  { return __x < *this; }
      bool operator<=(const _Self& __x) const { return !(__x < *this); }
      bool operator>=(const _Self& __x) const { return !(*this < __x); }
    
    //跟进主控map的节点。
      void _M_set_node(_Map_pointer __new_node) {
        _M_node = __new_node;//将map中下一个元素（即链表节点）赋给当前节点值
        _M_first = *__new_node;//更新_M_first
        _M_last = _M_first + difference_type(_S_buffer_size());//更新_M_last
      }
    };

--------------------

[20160419232343281]: /images/20220724/2e4a8c2dc755494e912e785f37da837a.png