STL源码解析(2)-deque类

deque是类似于vector的动态数组，与之不同的是支持在头部的插入、删除操作，同时其时间复杂度控制在O(1)级别；在STL标准库中deque实现并不复杂，复杂的是一些如同内存配置器、trans、仿函数之类的特性，这里简单走读一些deque的实现；说明一下，这个源码是比较老的版本，只是为了了解原理

deque实现原理

2021031501.gif

• deque使用的是map+array的模型，多块不连续的缓冲区array用来存储数据，一个map数组用来控制这些缓冲区
• 支持类似数组的随机访问，其本质是运算符重载，相比于真正的数组而言内部额外多了一些计算操作

deque基础结构

核心数据结构

  _Tp** _M_map;               //一个deque包含多个小块连续空间, 这里存储这些连续空间的地址
  size_t _M_map_size;         //该map的大小

这个数据结构即表明了deque的底层数据模型

迭代器

template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator {
......
_Tp* _M_cur;                                // 迭代器指向缓冲区的当前元素
_Tp* _M_first;                              // 迭代器指向缓冲区的头部
_Tp* _M_last;                               // 迭代器指向缓冲区的尾部
_Map_pointer _M_node;                       // 迭代器指向 map 的 node

  deque的迭代器相比于vector就复杂的多，需要查找缓冲区；不过对外提供了运算符重载，使用起来感知不大

// 迭代器 前置式operator++
_Self& operator++() {
    ++_M_cur;                       //元素往后移
    if (_M_cur == _M_last) {        // 以达到缓冲区尾部, 那么需要移动到下一个缓冲区
      _M_set_node(_M_node + 1);     // 切换下一级缓冲区, map其实是一个指针数组所以这里直接+1就是下一个缓冲区的节点
      _M_cur = _M_first;            // 那么移动到下一级缓冲区的开头
    }
    return *this; 
}

  这就是deque迭代器运算符的实现，只是额外考虑了缓冲区的切换

---

deque接口实现

初始化

template <class _Tp, class _Alloc>
void
_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
{
  size_t __num_nodes = 
    __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;     //一个缓冲区约512字节, 计算需要多少个缓冲区

  _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2); //map管理的缓冲区个数, 最少8个
  _M_map = _M_allocate_map(_M_map_size);                            //分配空间, 仅分配了map的空间

  _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;        

   //默认情况传入的参数是0, 那么两者都指向中间
  
  _Tp** __nfinish = __nstart + __num_nodes;
    
  __STL_TRY {
    _M_create_nodes(__nstart, __nfinish);
  }
  __STL_UNWIND((_M_deallocate_map(_M_map, _M_map_size), 
                _M_map = 0, _M_map_size = 0));

  _M_start._M_set_node(__nstart);
  _M_finish._M_set_node(__nfinish - 1);                             //初始化开头和结尾的迭代器
  _M_start._M_cur = _M_start._M_first;
  _M_finish._M_cur = _M_finish._M_first +
               __num_elements % __deque_buf_size(sizeof(_Tp));      //cur节点指向正确位置
}

• deque的缓冲区大小和存储的数据类型有关，取该数据结构的整数倍为缓冲区大小，最大为512字节或者该数据结构的大小
• deque构造时可以指定元素个数，缓冲区的个数需要在保证可存储所有元素的基础上+2，同时限制最小个数为8
• 两个迭代器_M_start和_M_finish分别指向开头和结尾，用来管理缓冲区
• _M_start和_M_finish初始情况是指向map中间的缓冲区，数据也尽量放在中间

在末尾删除元素

  void pop_back() {
    if (_M_finish._M_cur != _M_finish._M_first) {               
    //不需要考虑缓冲区移动, 和vector销毁数据一致
      --_M_finish._M_cur;
      destroy(_M_finish._M_cur);
    }
    else
      _M_pop_back_aux();
  }
  
template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_pop_back_aux()
{
  _M_deallocate_node(_M_finish._M_first);
  _M_finish._M_set_node(_M_finish._M_node - 1);
  _M_finish._M_cur = _M_finish._M_last - 1;
  destroy(_M_finish._M_cur);
}

• 如果末尾元素不是缓冲区的最后一个元素，则移动_M_finish._M_cur更新指针即可
• 如果末尾元素刚好是缓冲区的最后一个元素，那么相关指针需要切换到前一个缓冲区，同时会直接释放一个缓冲区空间
• 和vector相比就是多了缓冲区的考虑

在末尾添加一个元素

void push_back(const value_type& __t) {
    if (_M_finish._M_cur != _M_finish._M_last - 1) {            //finish所在缓冲器还有空间, 直接使用即可
        construct(_M_finish._M_cur, __t);
        ++_M_finish._M_cur;                                     //cur指针后移
    }
    else
        _M_push_back_aux(__t);
}


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();
    *(_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 _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))
        _M_reallocate_map(__nodes_to_add, false);
}

  如果在末尾还有空间，则直接添加元素即可；如果末尾没有空间，则重新调整空间大小

template <class _Tp, class _Alloc>
void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
                                          bool __add_at_front)
{
  size_type __old_num_nodes = _M_finish._M_node - _M_start._M_node + 1;         //缓冲区数量
  size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;                 //x新的缓冲区数量

  _Map_pointer __new_nstart;
  if (_M_map_size > 2 * __new_num_nodes) {  

  /* 已有空间大于需要缓冲区数量的两倍, 那么不需要扩大缓冲区大小, 改为调整map的指针指向 */

    __new_nstart = _M_map + (_M_map_size - __new_num_nodes) / 2 
                     + (__add_at_front ? __nodes_to_add : 0);                   //新的起始缓冲区位置
    if (__new_nstart < _M_start._M_node)
      copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);              //往前移
    else
      copy_backward(_M_start._M_node, _M_finish._M_node + 1,                    //往后移
                    __new_nstart + __old_num_nodes);

    /* 调整完毕, 尽可能的保证缓冲区在map的中间 */
  }
  else {                //上面其实并不扩大map数组的容量, 仅仅是为了使得deque中的数据尽可能在中间
    size_type __new_map_size = 
      _M_map_size + max(_M_map_size, __nodes_to_add) + 2;           //基本每次以两倍的长度扩容

    _Map_pointer __new_map = _M_allocate_map(__new_map_size);
    __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
                         + (__add_at_front ? __nodes_to_add : 0);
    copy(_M_start._M_node, _M_finish._M_node + 1, __new_nstart);
    _M_deallocate_map(_M_map, _M_map_size);

    _M_map = __new_map;
    _M_map_size = __new_map_size;
  }

  因为数据往往存在中间，所以末尾空间不够不代表缓冲区真正不够；缓冲区以差不多两倍扩张，如果原有缓冲区已大于需要空间的两倍则不进行扩容，而是调整位置；同时会重新调整数据位置使得其尽量存储在缓冲区中间位置

开头插入元素

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

  deque数据存储在中间，在开头和末尾添加、删除元素的操作基本一致

总结

• 使用数组来管理多个缓冲区, 在不涉及到缓冲区迁移和扩容时基本和vector一致

• 在map创建以及重新扩容时, 每次都尽可能的将缓冲区放在map的中间

看到了这里基本已经理解deque的结构了, 其他的接口函数也不过超出这些了