C++ STL源码剖析之序列式容器deque

0.导语

deque是一种双向开口的分段连续线性空间(简单理解为：双端队列)，可以在头尾端进行元素的插入和删除。

deque与vector最大的差异就是：

  • deque允许于常数时间内对头端进行插入或删除元素；

  • deque是分段连续线性空间，随时可以增加一段新的空间；

deque不像vector那样，vector当内存不够时，需重新分配/复制数据/释放原始空间；不过deque的迭代器设置比vector复杂，因为迭代器不能使用普通指针，因此尽量使用vector。

1.deque中控器

用户看起来deque使用的是连续空间，实际上是分段连续线性空间。为了管理分段空间deque容器引入了map，称之为中控器，map是一块连续的空间，其中每个元素是指向缓冲区的指针，缓冲区才是deque存储数据的主体。

deque_r.png

在上图中，buffer称为缓冲区，显示map size的一段连续空间就是中控器。

中控器包含了map size,指向buffer的指针，deque的开始迭代器与结尾迭代器。

  1. _Tp     **_M_map;
  2. size_t      _M_map_size;
  3. iterator    _M_start;
  4. iterator    _M_finish;

由于buffer也是指针，所以_Tp是指针的指针。

deque继承自_Deque_base,而_Deque_base里面有一个_M_impl。

deque_base.png

根据下图与上述描述，可以知道，中控器是由_Deque_impl实现的。

impl.png

而deque是使用基类_Deque_base来完成内存管理与中控器管理。

2.高端的迭代器

对于deque来说，它的迭代器设计的非常棒！

如下图所示：deque_iterator.png

首先来看一下比较重要的成员：

  1. typedef _Tp             **_Map_pointer;
  2. _Tp     *_M_cur;
  3. _Tp     *_M_first;
  4. _Tp     *_M_last;
  5. _Map_pointer    _M_node;

这几个究竟是什么呢，根据名字，很容易知道啥意思，对于deque来说，是分段连续空间，迭代器执行操作，上述的_M_cur指向具体的元素，_M_first指向这段buffer中的第一个元素,_M_last指向最后一个元素(不是有效的元素)，而_M_node则是指向中控器。所以它是一个指针的指针。

例如现在迭代器执行++操作，当前buffer不够用了，那么此时需要一个指针能够回到中控器，取下一段buffer，重置_M_first与_M_last的指针位置，_M_cur指向新段buffer中的指定位置。

我们现在回到一开始的图：

deque_r.png

最上面的的iterator就是上面几个指针的区块配图。

那buffer计算是什么实现的呢?

在源码中计算是根据传递进来的类型，如果传递的类型小于512字节，那么buffersize就是512/sizeof(_Tp)，超过512，就是1。

  1. static size_t _S_buffer_size()
  2. _GLIBCXX_NOEXCEPT
  3. {
  4.     return(__deque_buf_size( sizeof(_Tp) ) );
  5. }

__deque_buf_size实现

  1. #ifndef _GLIBCXX_DEQUE_BUF_SIZE
  2. #define _GLIBCXX_DEQUE_BUF_SIZE 512
  3. #endif
  4. inline size_t
  5. __deque_buf_size( size_t
  6.             __size )
  7. {
  8.     return(__size < _GLIBCXX_DEQUE_BUF_SIZE
  9.             ? size_t( _GLIBCXX_DEQUE_BUF_SIZE / __size ) : size_t( 1 ) );
  10. }

前面几节源码中提到了萃取机技术，针对每个迭代器都需要嵌入下面五种typedef：

  1. typedef std::random_access_iterator_tag iterator_category;
  2. typedef _Tp             value_type;
  3. typedef _Ptr                pointer;
  4. typedef _Ref                reference;
  5. typedef ptrdiff_t           difference_type;

据此，也可以知道deque迭代器的使用的是随机访问迭代器：random_access_iterator_tag。

而vector使用的迭代器也是这个，根据侯捷老师所讲，连续的buffer是vector，这与迭代器的tag类型不谋而合。

下面来看一下这个强大的迭代器的一些操作符重载：

具体的讲解在代码里面说。

取值操作符

  1. reference
  2. operator*() const
  3. _GLIBCXX_NOEXCEPT
  4. {
  5.     return(*_M_cur);
  6. }
  9. pointer
  10. operator->() const
  11. _GLIBCXX_NOEXCEPT
  12. {
  13.     return(_M_cur);
  14. }

当然上述的->也可以直接调用*操作符来实现，例如：

  1. pointer
  2. operator->() const
  3. _GLIBCXX_NOEXCEPT
  4. {
  5.     return &(operator*());
  6. }

++与—操作符

  1. // 前置++操作符
  2. _Self &
  3. operator++()
  4. _GLIBCXX_NOEXCEPT
  5. {
  6.     // 先++，判断是否到了buffer的末尾，如果到了末尾，就要跳到下一个buffer。
  7.     ++_M_cur;
  8.     if ( _M_cur == _M_last ) // _M_last指向的不是有效元素，保留节点  
  9.     {
  10.         _M_set_node( _M_node + 1 );
  11.         _M_cur = _M_first;
  12.     }
  13.     return(*this);
  14. }
  16. // 后置++操作符
  17. _Self
  18. operator++( int )
  19. _GLIBCXX_NOEXCEPT
  20. {
  21.     _Self __tmp = *this;
  22.     ++*this;
  23.     return(__tmp);
  24. }
  26. // 前置--操作符
  27. _Self &
  28. operator--()
  29. _GLIBCXX_NOEXCEPT
  30. {
  31.     // 先判断是否到了起始位置，如果到了，由于需要进行--操作，那么就应该进入前一个buffer
  32.     if ( _M_cur == _M_first )
  33.     {
  34.         _M_set_node( _M_node - 1 );
  35.         _M_cur = _M_last;
  36.     }
  37.     --_M_cur;
  38.     return(*this);
  39. } //先在容器头部插入与第一个元素相同的元素
  41. // 后置--操作符
  42. _Self
  43. operator--( int )
  44. _GLIBCXX_NOEXCEPT
  45. {
  46.     _Self __tmp = *this;    /* 定义一个副本 */
  47.     --*this;                /* 迭代器自减操作 */
  48.     return(__tmp);
  49. }

跳跃n个距离操作符

  1. /*
  2. * 实现随机取,迭代器可以直接跳跃n个距离
  3. * 将迭代器前移n个距离,当n负值时就为下面的operator-=操作
  4. */
  5. _Self &
  6. operator+=( difference_type __n )
  8. _GLIBCXX_NOEXCEPT
  9. {
  10.     const difference_type __offset = __n + (_M_cur - _M_first);
  11.     /*
  12.         * 若前移n个距离后，目标依然在同一个缓冲区
  13.         * 则直接前移n个距离
  14.         */
  15.     if ( __offset >= 0 && __offset < difference_type( _S_buffer_size() ) )
  16.         _M_cur += __n;
  17.     else {
  18.         /*
  19.             * 若前移n个距离后,目标超出了缓冲区范围
  20.             * __offset>0   __offset / difference_type(_S_buffer_size())计算向后移动多少个缓冲区
  21.             * __offset<=0  -difference_type((-__offset - 1) / _S_buffer_size()) - 1计算向前移动多少个缓冲区
  22.             */
  23.         const difference_type __node_offset =
  24.             __offset > 0 ? __offset / difference_type( _S_buffer_size() )
  25.             : -difference_type( (-__offset - 1)
  26.                         / _S_buffer_size() ) - 1;
  27.         /* 调整到正确的缓冲区,此时_M_first已经修改了 */
  28.         _M_set_node( _M_node + __node_offset );
  29.         /* 修改为正确的指针位置 */
  30.         _M_cur = _M_first + (__offset - __node_offset
  31.                         * difference_type( _S_buffer_size() ) );
  32.     }
  33.     return(*this);
  34. }

下面这几个操作符都是调用上面的+=操作符实现：

  1. /*
  2.     * 操作符+重载
  3.     * 返回操作之后的副本
  4.     */
  5. _Self
  6. operator+( difference_type __n ) const
  7. _GLIBCXX_NOEXCEPT
  8. {
  9.     _Self __tmp = *this;
  10.     /* 调用operator+=操作 */
  11.     return(__tmp += __n);
  12. }
  15. /* 利用operator+=操作实现 */
  16. _Self &
  17. operator-=( difference_type __n )
  18. _GLIBCXX_NOEXCEPT
  19. {
  20.     return(*this += -__n);
  21. }
  24. /*
  25.     * 操作符-重载
  26.     * 返回操作之后的副本
  27.     */
  28. _Self
  29. operator-( difference_type __n ) const
  30. _GLIBCXX_NOEXCEPT
  31. {
  32.     _Self __tmp = *this;    /*  保存副本 */
  33.     return(__tmp -= __n);   /* 调用operator-=操作符 */
  34. }
  37. /* 返回指定位置的元素，即实现随机存取 */
  38. reference
  39. operator[]( difference_type __n ) const
  40. _GLIBCXX_NOEXCEPT
  41. {
  42.     return(*(*this + __n) );    /* 该函数调用operator+,operator* */
  43. }

buffer跳跃

前面的++与—等操作符，会调用到_M_set_node函数，该函数的作用是能够进行buffer之间的跳跃，修改_M_node、_M_first、_M_last的指向。

  1. /**
  2.     *  Prepares to traverse new_node.  Sets everything except
  3.     *  _M_cur, which should therefore be set by the caller
  4.     *  immediately afterwards, based on _M_first and _M_last.
  5.     */
  6. void
  7. _M_set_node( _Map_pointer __new_node )
  8. _GLIBCXX_NOEXCEPT
  9. {
  10.     _M_node     = __new_node;                                           /* 指向新的节点 */
  11.     _M_first    = *__new_node;                                          /* 指向新节点的头部 */
  12.     _M_last     = _M_first + difference_type( _S_buffer_size() );       /* 指向新节点的尾部 */
  13. }

据此，我们就把deque的迭代器实现细节讲解完毕了。

3.deque

begin()函数

返回_M_start。

  1. iterator
  2. begin()
  3. _GLIBCXX_NOEXCEPT
  4. {
  5.     return(this->_M_impl._M_start);
  6. }

end()函数

返回_M_finish。

  1. iterator
  2. end()
  3. _GLIBCXX_NOEXCEPT
  4. {
  5.     return(this->_M_impl._M_finish);
  6. }

size()函数

  1. size_type
  2. size() const
  4. _GLIBCXX_NOEXCEPT
  5. {
  6.     return(this->_M_impl._M_finish - this->_M_impl._M_start);
  7. }

resize()函数

根据传递进来的大小，如果超过了总size，就重新分配扩充new_size-size()空间，否则删除从size()-new_size数据，例如现在有20个空间，resize(12)，就会把后面8个空间数据删除及空间释放。

  1. void
  2. resize( size_type __new_size )
  3. {
  4.     const size_type __len = size();
  5.     if ( __new_size > __len )
  6.         _M_default_append( __new_size - __len );
  7.     else if ( __new_size < __len )
  8.         _M_erase_at_end( this->_M_impl._M_start
  9.                     + difference_type( __new_size ) );
  10. }

empty()函数

判断两个指针位置即可。

  1. bool
  2. empty() const
  4. _GLIBCXX_NOEXCEPT
  5. {
  6.     return(this->_M_impl._M_finish == this->_M_impl._M_start);
  7. }

back函数

  1. reference
  2. back()
  3. _GLIBCXX_NOEXCEPT       // 指向finish的前一个位置
  4. {
  5.     iterator __tmp = end();
  6.     --__tmp;
  7.     return(*__tmp);
  8. }

push_front函数

  1. void
  2. push_front( const value_type &__x )
  3. {
  4.     //若当前缓冲区存在可用空间
  5.     if ( this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first )
  6.     {
  7.         this->_M_impl.construct( this->_M_impl._M_start._M_cur - 1, __x );// 直接构造对象
  8.         --this->_M_impl._M_start._M_cur;    // 调整指针所指位置
  9.     } else
  10.         _M_push_front_aux( __x );   // 需分配一段新的连续空间
  11. }

push_back函数

  1. void
  2. push_back( const value_type &__x )
  3. {
  4.     //若当前缓冲区存在可用空间
  5.     if ( this->_M_impl._M_finish._M_cur
  6.             != this->_M_impl._M_finish._M_last - 1 )
  7.     {
  8.         this->_M_impl.construct( this->_M_impl._M_finish._M_cur, __x ); // 直接构造对象
  9.         ++this->_M_impl._M_finish._M_cur;       //调整指针所指位置
  10.     } else     // 若当前缓冲区不存在可用空间
  11.     // 需分配一段新的连续空间
  12.         _M_push_back_aux( __x );
  13. }

上述对应的pop动作与之相反。

insert()函数

insert函数比较有意思，根据传递进来的迭代器位置，看是不在开头与结尾，如果是在开头直接调用push_front函数，结尾直接调push_back函数，否则在容器中直接插入元素。

  1. template <typename _Tp, typename _Alloc>
  2. typename deque<_Tp, _Alloc>::iterator
  3. deque<_Tp, _Alloc>::
  4. insert(iterator __position, const value_type& __x)
  5. {
  6.         if (__position._M_cur == this->_M_impl._M_start._M_cur)   
  7.     {
  8.         push_front(__x);
  9.         return this->_M_impl._M_start;
  10.     }
  11.         else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
  12.     {
  13.         push_back(__x);
  14.         iterator __tmp = this->_M_impl._M_finish;
  15.         --__tmp;
  16.         return __tmp;
  17.     }
  18.         else  //否则在容器直接插入数据
  19.         return _M_insert_aux(__position._M_const_cast(), __x);
  20. }

而上述在容器中直接插入元素函数，会计算插入点，如果比较靠前面，就在前面插入，靠近后面就在后面插入：

  1. template<typename _Tp, typename _Alloc>
  2. typename deque<_Tp, _Alloc>::iterator
  3. deque<_Tp, _Alloc>::
  4. _M_insert_aux(iterator __pos, const value_type& __x)
  5. {
  6.     value_type __x_copy = __x; // XXX copy
  7.     difference_type __index = __pos - this->_M_impl._M_start;  //计算插入点之前元素个数
  8.     if (static_cast<size_type>(__index) < size() / 2)   //若插入点之前的元素较少
  9.         {
  10.         push_front(_GLIBCXX_MOVE(front())); //先在容器头部插入与第一个元素相同的元素
  11.         iterator __front1 = this->_M_impl._M_start;
  12.         ++__front1;
  13.         iterator __front2 = __front1;
  14.         ++__front2;
  15.         __pos = this->_M_impl._M_start + __index;
  16.         iterator __pos1 = __pos;
  17.         ++__pos1;
  18.         _GLIBCXX_MOVE3(__front2, __pos1, __front1); // 元素搬移
  19.         }
  20.     else
  21.     {
  22.         push_back(_GLIBCXX_MOVE(back()));
  23.         iterator __back1 = this->_M_impl._M_finish;
  24.         --__back1;
  25.         iterator __back2 = __back1;
  26.         --__back2;
  27.         __pos = this->_M_impl._M_start + __index;
  28.         _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
  29.     }
  30.     *__pos = _GLIBCXX_MOVE(__x_copy);       // 在安插点上设定新值
  31.     return __pos;
  32. }