C++ STL 容器设计实现 -- deque

5、deque

deque 是双端队列(double-ended queue),其实现比较特殊,有多段地址连续的存储空间组成,整理布局如下:

  • 每段地址连续内存成为一个 node
  • map 是指针构成的数据,每个元素指向一个 node
  • start 和 finish 是一个迭代器变量,分别指向第一个和最后一个 node

迭代器以 node 为单位

  • cur 指向当前元素
  • first 指向 node 第一个元素
  • last 指向 node 最后一个元素的下一个地址
  • node 指向 map 中相应位置,可以很方便找到前一个或者后一个 node

  • node 计算如下
    • 元素占用内存小于 512 字节,最大占用 512 字节
    • 否则,默认分配一个元素大小的内存
    /// stl_deque.h
      _GLIBCXX_CONSTEXPR inline size_t
      __deque_buf_size(size_t __size)
      { return (__size < _GLIBCXX_DEQUE_BUF_SIZE // 512
            ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }
    
    

    5.1、_Deque_iterator

    deque 的迭代器是 random access 类型的迭代器,四个成员如上图所示。

    /// stl_deque.h
      template<typename _Tp, typename _Ref, typename _Ptr>
        struct _Deque_iterator
        {
    #if __cplusplus < 201103L
          typedef _Deque_iterator<_Tp, _Tp&, _Tp*>		   iterator;
          typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
          typedef _Tp*					   _Elt_pointer;
          typedef _Tp**					   _Map_pointer;
    #else
        private:
          template<typename _CvTp>
        using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_rebind<_Ptr, _CvTp>>;
        public:
          typedef __iter<_Tp>				   iterator;
          typedef __iter<const _Tp>				   const_iterator;
          typedef __ptr_rebind<_Ptr, _Tp>			   _Elt_pointer;
          typedef __ptr_rebind<_Ptr, _Elt_pointer>		   _Map_pointer;
    #endif
    
          static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
          { return __deque_buf_size(sizeof(_Tp)); }
    
          typedef std::random_access_iterator_tag	iterator_category;
          typedef _Tp				value_type;
          typedef _Ptr				pointer;
          typedef _Ref				reference;
          typedef size_t				size_type;
          typedef ptrdiff_t				difference_type;
          typedef _Deque_iterator			_Self;
    
          _Elt_pointer _M_cur;
          _Elt_pointer _M_first;
          _Elt_pointer _M_last;
          _Map_pointer _M_node;
    
          /* ... */
          void
          _M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT
          {
        _M_node = __new_node;
        _M_first = *__new_node;
        _M_last = _M_first + difference_type(_S_buffer_size());
          }
          /* ... */
        };
    
    

    _Deque_iterator 进行 ++ 或者 -- 操作时,当 cur 移动到 last 或回退到 first 时,自动跳转到下一个 node 或者上一个 node

    /// stl_deque.h
          _Self&
          operator++() _GLIBCXX_NOEXCEPT
          {
        ++_M_cur;
        if (_M_cur == _M_last) // 进入下一个 node
          {
            _M_set_node(_M_node + 1);
            _M_cur = _M_first;
          }
        return *this;
          }
    
          _Self&
          operator--() _GLIBCXX_NOEXCEPT
          {
        if (_M_cur == _M_first) // 进入上一个 node
          {
            _M_set_node(_M_node - 1);
            _M_cur = _M_last;
          }
        --_M_cur;
        return *this;
          }
    
    

    运算符 += 或者 -= 也是同样的道理。

    /// stl_deque.h
          _Self&
          operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
          {
        const difference_type __offset = __n + (_M_cur - _M_first);
        if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
          _M_cur += __n;
        else
          {
            const 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;
          }
    
          _GLIBCXX_NODISCARD
          reference
          operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
          { return *(*this + __n); }
    
    

    5.2、_Deque_base::_Deque_impl_data

    _Deque_impl_data 封装了 deque 的数据结构 map。

    /// stl_deque.h
          struct _Deque_impl_data
          {
        _Map_pointer _M_map;
        size_t _M_map_size;
        iterator _M_start;
        iterator _M_finish;
    
        _Deque_impl_data() _GLIBCXX_NOEXCEPT
        : _M_map(), _M_map_size(), _M_start(), _M_finish()
        { }
    
    /* ... */
          };
    
    

    5.3、_Deque_base::_Deque_impl

    _Deque_impl 继承 _Deque_impl_data 和 内存分配器 _Tp_alloc_type。采用继承的方法,是避免空类(内存分配器通常没有数据成员)引入内存消耗。

    /// stl_deque.h
          // This struct encapsulates the implementation of the std::deque
          // standard container and at the same time makes use of the EBO
          // for empty allocators.
          struct _Deque_impl
          : public _Tp_alloc_type, public _Deque_impl_data
          {
    /* ... */
          };
    
    

    5.4、_Deque_base

    _Deque_base 只有一个 _Deque_impl 成员变量,_Deque_base 另外负责 node 和 map 的内存分配与释放。

    /// stl_deque.h
      template<typename _Tp, typename _Alloc>
        class _Deque_base
        {
        protected:
          typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
        rebind<_Tp>::other _Tp_alloc_type;
          typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type>	 _Alloc_traits;
    
          typedef typename _Alloc_traits::pointer		_Ptr;
          typedef typename _Alloc_traits::const_pointer	_Ptr_const;
    
          typedef typename _Alloc_traits::template rebind<_Ptr>::other
        _Map_alloc_type;
          typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits;
    
          typedef _Alloc		  allocator_type;
    
          allocator_type
          get_allocator() const _GLIBCXX_NOEXCEPT
          { return allocator_type(_M_get_Tp_allocator()); }
    
          typedef _Deque_iterator<_Tp, _Tp&, _Ptr>	  iterator;
          typedef _Deque_iterator<_Tp, const _Tp&, _Ptr_const>   const_iterator;
    /* ... */
    
          typedef typename iterator::_Map_pointer _Map_pointer;
    /* ... */
          enum { _S_initial_map_size = 8 };
    
          _Deque_impl _M_impl;
        };
    
    

    成员函数 _M_allocate_node() 和 _M_deallocate_node() 用于分配和释放一个 node 内存。

    /// stl_deque.h
          _Ptr
          _M_allocate_node()
          {
        typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
        return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp)));
          }
    
          void
          _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
          {
        typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
        _Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp)));
          }
    
    

    _M_create_nodes() 和 _M_destroy_nodes() 分别调用 _M_allocate_node() 和 _M_deallocate_node() 函数,用于申请或者释放多个 node 的内存。

    /// stl_deque.h
      template<typename _Tp, typename _Alloc>
        void
        _Deque_base<_Tp, _Alloc>::
        _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish)
        {
          _Map_pointer __cur;
          __try
        {
          for (__cur = __nstart; __cur < __nfinish; ++__cur)
            *__cur = this->_M_allocate_node();
        }
          __catch(...)
        {
          _M_destroy_nodes(__nstart, __cur);
          __throw_exception_again;
        }
        }
    
      template<typename _Tp, typename _Alloc>
        void
        _Deque_base<_Tp, _Alloc>::
        _M_destroy_nodes(_Map_pointer __nstart,
                 _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
        {
          for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
        _M_deallocate_node(*__n);
        }
    
    

    成员函数 _M_allocate_map() 和 _M_deallocate_map() 用于分配和释放 map 的内存。

    /// stl_deque.h
          _Map_pointer
          _M_allocate_map(size_t __n)
          {
        _Map_alloc_type __map_alloc = _M_get_map_allocator();
        return _Map_alloc_traits::allocate(__map_alloc, __n);
          }
    
          void
          _M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT
          {
        _Map_alloc_type __map_alloc = _M_get_map_allocator();
        _Map_alloc_traits::deallocate(__map_alloc, __p, __n);
          }
    
    

    _M_initialize_map() 函数用于初始化 map,包括申请 node 内存。

    • 1)计算 node 个数
    • 2)申请 map 内存(至少额外申请 2 个空间,用于应对未来的元素插入)
    • 3)申请 node
    • 4)初始化 _Deque_impl_data 成员变量
    /// deque.tcc
      template<typename _Tp, typename _Alloc>
        void
        _Deque_base<_Tp, _Alloc>::
        _M_initialize_map(size_t __num_elements)
        {
          const size_t __num_nodes = (__num_elements / __deque_buf_size(sizeof(_Tp))
                      + 1);
    
          this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
                           size_t(__num_nodes + 2)); // 2 个额外空间
          this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
    
          // For "small" maps (needing less than _M_map_size nodes), allocation
          // starts in the middle elements and grows outwards.  So nstart may be
          // the beginning of _M_map, but for small maps it may be as far in as
          // _M_map+3.
    
          _Map_pointer __nstart = (this->_M_impl._M_map
                       + (this->_M_impl._M_map_size - __num_nodes) / 2);
          _Map_pointer __nfinish = __nstart + __num_nodes;
    
          __try
        { _M_create_nodes(__nstart, __nfinish); }
          __catch(...)
        {
          _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
          this->_M_impl._M_map = _Map_pointer();
          this->_M_impl._M_map_size = 0;
          __throw_exception_again;
        }
    
          this->_M_impl._M_start._M_set_node(__nstart);
          this->_M_impl._M_finish._M_set_node(__nfinish - 1);
          this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
          this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
                        + __num_elements
                        % __deque_buf_size(sizeof(_Tp))); // 最后一个元素下一个位置
        }
    
    

    5.5、std::deque

      template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
        class deque : protected _Deque_base<_Tp, _Alloc>
        {
          typedef _Deque_base<_Tp, _Alloc>			_Base;
          typedef typename _Base::_Tp_alloc_type		_Tp_alloc_type;
          typedef typename _Base::_Alloc_traits		_Alloc_traits;
          typedef typename _Base::_Map_pointer		_Map_pointer;
    
        public:
          typedef _Tp					value_type;
          typedef typename _Alloc_traits::pointer		pointer;
          typedef typename _Alloc_traits::const_pointer	const_pointer;
          typedef typename _Alloc_traits::reference		reference;
          typedef typename _Alloc_traits::const_reference	const_reference;
          typedef typename _Base::iterator			iterator;
          typedef typename _Base::const_iterator		const_iterator;
          typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;
          typedef std::reverse_iterator<iterator>		reverse_iterator;
          typedef size_t					size_type;
          typedef ptrdiff_t					difference_type;
          typedef _Alloc					allocator_type;
    /* ... */
        };
    
    

    deque 重点分析插入元素的几个成员函数,push_back/front,pop_back/front,insert。

    5.5.1、push_back/front

    如果预留有空间,直接插入,否则需要申请 node 或者重新扩展 map。push_back() 和 push_front() 分别调用 _M_push_back_aux() 和 _M_push_front_aux() 用于处理预留空间消耗完的情况。

    /// stl_deque.h
          void
          push_back(const value_type& __x)
          {
        if (this->_M_impl._M_finish._M_cur
            != this->_M_impl._M_finish._M_last - 1)
          { // 直接插入
            _Alloc_traits::construct(this->_M_impl,
                         this->_M_impl._M_finish._M_cur, __x);
            ++this->_M_impl._M_finish._M_cur;
          }
        else
          _M_push_back_aux(__x);
          }
    
          void
          push_front(const value_type& __x)
          {
        if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
          { // 直接插入
            _Alloc_traits::construct(this->_M_impl,
                         this->_M_impl._M_start._M_cur - 1,
                         __x);
            --this->_M_impl._M_start._M_cur;
          }
        else
          _M_push_front_aux(__x);
          }
    
    

    _M_push_back_aux() 和 _M_push_front_aux() 两个函数原理相同,首先判断是否需要拓展 map,必要时先拓展 map,然后申请一个 node,最后插入新增元素。

    /// deque.tcc
      template<typename _Tp, typename _Alloc>
    #if __cplusplus >= 201103L
        template<typename... _Args>
          void
          deque<_Tp, _Alloc>::
          _M_push_back_aux(_Args&&... __args)
    #else
    /* ... */
    #endif
          {
        if (size() == max_size())
          __throw_length_error(
              __N("cannot create std::deque larger than max_size()"));
    
        _M_reserve_map_at_back(); // 必要时拓展 map
        *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); // 申请 node
        __try
          {
    #if __cplusplus >= 201103L
            _Alloc_traits::construct(this->_M_impl,
                         this->_M_impl._M_finish._M_cur,
                         std::forward<_Args>(__args)...); // 插入元素
    #else
    /* ... */
    #endif
            this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
                            + 1);
            this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
          }
        __catch(...)
          {
            _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
            __throw_exception_again;
          }
          }
    
      // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
      template<typename _Tp, typename _Alloc>
    #if __cplusplus >= 201103L
        template<typename... _Args>
          void
          deque<_Tp, _Alloc>::
          _M_push_front_aux(_Args&&... __args)
    #else
    /* ... */
    #endif
          {
        if (size() == max_size())
          __throw_length_error(
              __N("cannot create std::deque larger than max_size()"));
    
        _M_reserve_map_at_front(); // 必要时拓展 map
        *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
        __try
          {
            this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
                               - 1);
            this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
    #if __cplusplus >= 201103L
            _Alloc_traits::construct(this->_M_impl,
                         this->_M_impl._M_start._M_cur,
                         std::forward<_Args>(__args)...); // 插入元素
    #else
    /* ... */
    #endif
          }
        __catch(...)
          {
            ++this->_M_impl._M_start;
            _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
            __throw_exception_again;
          }
          }
    
    

    _M_reserve_map_at_back() 和 _M_reserve_map_at_front() 都调用 _M_reallocate_map() 函数拓展 map。

    /// deque.tcc
          void
          _M_reserve_map_at_back(size_type __nodes_to_add = 1)
          {
        if (__nodes_to_add + 1 > this->_M_impl._M_map_size
            - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
          _M_reallocate_map(__nodes_to_add, false);
          }
    
          void
          _M_reserve_map_at_front(size_type __nodes_to_add = 1)
          {
        if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
                           - this->_M_impl._M_map))
          _M_reallocate_map(__nodes_to_add, true);
          }
    
    

    _M_reallocate_map() 函数定义如下,如果 map 预留的空间足够大(2 倍),不需要拓展 map,只需要移动 nodes 就可以了,否则旧重新申请一个 map,新 map 的大小至少是原来的两倍 + 2。

    /// deque.tcc
      template <typename _Tp, typename _Alloc>
        void
        deque<_Tp, _Alloc>::
        _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
        {
          const size_type __old_num_nodes
        = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
          const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
    
          _Map_pointer __new_nstart;
          if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
        { // 不需要拓展 map,只需要移动 nodes
          __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
                         - __new_num_nodes) / 2
                 + (__add_at_front ? __nodes_to_add : 0);
          if (__new_nstart < this->_M_impl._M_start._M_node)
            std::copy(this->_M_impl._M_start._M_node,
                  this->_M_impl._M_finish._M_node + 1,
                  __new_nstart);
          else
            std::copy_backward(this->_M_impl._M_start._M_node,
                       this->_M_impl._M_finish._M_node + 1,
                       __new_nstart + __old_num_nodes);
        }
          else
        { // 拓展 map
          size_type __new_map_size = this->_M_impl._M_map_size
                         + std::max(this->_M_impl._M_map_size,
                            __nodes_to_add) + 2; // 新 map 的大小
        // 申请新 map
          _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
          __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
                 + (__add_at_front ? __nodes_to_add : 0);
          std::copy(this->_M_impl._M_start._M_node,
                this->_M_impl._M_finish._M_node + 1,
                __new_nstart); // 释放原来 map
          _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
    
          this->_M_impl._M_map = __new_map;
          this->_M_impl._M_map_size = __new_map_size;
        }
    
          this->_M_impl._M_start._M_set_node(__new_nstart);
          this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
        }
    
    

    5.5.2、pop_back/front

    相对于 push_back/front,pop_back/front 就比较简单,只需要考虑 node 的释放,不需要对 map 进行收缩。

    /// stl_deque.h
          void
          pop_back() _GLIBCXX_NOEXCEPT
          {
        __glibcxx_requires_nonempty();
        if (this->_M_impl._M_finish._M_cur
            != this->_M_impl._M_finish._M_first)
          { // 在 [_M_first, _M_cur) 中
            --this->_M_impl._M_finish._M_cur;
            _Alloc_traits::destroy(_M_get_Tp_allocator(),
                       this->_M_impl._M_finish._M_cur);
          }
        else
          _M_pop_back_aux();
          }
    
          void
          pop_front() _GLIBCXX_NOEXCEPT
          {
        __glibcxx_requires_nonempty();
        if (this->_M_impl._M_start._M_cur
            != this->_M_impl._M_start._M_last - 1)
          { // 在 [_M_cur, _M_last) 中
            _Alloc_traits::destroy(_M_get_Tp_allocator(),
                       this->_M_impl._M_start._M_cur);
            ++this->_M_impl._M_start._M_cur;
          }
        else
          _M_pop_front_aux();
          }
    
    

    _M_pop_back_aux() 和 _M_pop_front_aux() 也比较简单

    /// deque.tcc
      template <typename _Tp, typename _Alloc>
        void deque<_Tp, _Alloc>::
        _M_pop_back_aux()
        {
          _M_deallocate_node(this->_M_impl._M_finish._M_first); // 释放 node
          this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
          this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
          _Alloc_traits::destroy(_M_get_Tp_allocator(),
                     this->_M_impl._M_finish._M_cur); // 析构元素
        }
    
      template <typename _Tp, typename _Alloc>
        void deque<_Tp, _Alloc>::
        _M_pop_front_aux()
        {
          _Alloc_traits::destroy(_M_get_Tp_allocator(),
                     this->_M_impl._M_start._M_cur); // 析构元素
          _M_deallocate_node(this->_M_impl._M_start._M_first);
          this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); // 释放 node
          this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
        }
    
    

    5.5.3、insert

    deque 支持在任意位置插入元素,insert() 的实现比较复杂。

    首先是插入单个元素,比如 insert(pos, val)

    • 插入位置在 begin(),调用 push_front() 函数插入
    • 插入位置在 end(),调用 push_end() 函数插入
    • 调用 _M_insert_aux() 函数处理
    /// deque.tcc
      template <typename _Tp, typename _Alloc>
        typename deque<_Tp, _Alloc>::iterator
        deque<_Tp, _Alloc>::
    #if __cplusplus >= 201103L
        insert(const_iterator __position, const value_type& __x)
    #else
    /* ... */
    #endif
        {
          if (__position._M_cur == this->_M_impl._M_start._M_cur)
        { // 插入位置在 begin()
          push_front(__x);
          return this->_M_impl._M_start;
        }
          else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
        { // 插入位置在 end()
          push_back(__x);
          iterator __tmp = this->_M_impl._M_finish;
          --__tmp;
          return __tmp;
        }
          else
        return _M_insert_aux(__position._M_const_cast(), __x);
       }
    
    

    _M_insert_aux() 先移动元素,腾出插入位置,然后插入元素。

    /// deque.tcc
      template<typename _Tp, typename _Alloc>
    #if __cplusplus >= 201103L
        template<typename... _Args>
          typename deque<_Tp, _Alloc>::iterator
          deque<_Tp, _Alloc>::
          _M_insert_aux(iterator __pos, _Args&&... __args)
          {
        value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
    #else
    /* ... */
    #endif
        difference_type __index = __pos - this->_M_impl._M_start;
        if (static_cast<size_type>(__index) < size() / 2)
          { // 移动前半部
            push_front(_GLIBCXX_MOVE(front())); // 赋值第一个元素
            iterator __front1 = this->_M_impl._M_start;
            ++__front1;
            iterator __front2 = __front1;
            ++__front2;
            __pos = this->_M_impl._M_start + __index;
            iterator __pos1 = __pos;
            ++__pos1; // 将 [front2, pos1) 元素移动到 [front1, )
            _GLIBCXX_MOVE3(__front2, __pos1, __front1);
          }
        else
          { // 移动后半部
            push_back(_GLIBCXX_MOVE(back()));
            iterator __back1 = this->_M_impl._M_finish;
            --__back1;
            iterator __back2 = __back1;
            --__back2;
            __pos = this->_M_impl._M_start + __index;
            _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
          }
        *__pos = _GLIBCXX_MOVE(__x_copy);
        return __pos;
          }
    
    

    然后插入多个相同的值,比如 insert(pos, n, val)

    /// stl_deque.h
          iterator
          insert(const_iterator __position, size_type __n, const value_type& __x)
          {
        difference_type __offset = __position - cbegin();
        _M_fill_insert(__position._M_const_cast(), __n, __x);
        return begin() + __offset;
          }
    
    

    _M_fill_insert() 处理逻辑是

    • 插入位置在 begin(),在 begin() 插入 n 个元素
    • 插入位置在 end(),在 end() 后面插入 n 个元素
    • 调用 _M_insert_aux() 处理,先整体移动出 n 个位置的空间,再插入
    /// deque.tcc
      template <typename _Tp, typename _Alloc>
        void
        deque<_Tp, _Alloc>::
        _M_fill_insert(iterator __pos, size_type __n, const value_type& __x)
        {
          if (__pos._M_cur == this->_M_impl._M_start._M_cur)
        { // 插入位置在 begin(),先申请空间,在赋值
          iterator __new_start = _M_reserve_elements_at_front(__n);
          __try
            {
              std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start,
                          __x, _M_get_Tp_allocator());
              this->_M_impl._M_start = __new_start;
            }
          __catch(...)
            {
              _M_destroy_nodes(__new_start._M_node,
                       this->_M_impl._M_start._M_node);
              __throw_exception_again;
            }
        }
          else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
        { // 插入位置在 end()
          iterator __new_finish = _M_reserve_elements_at_back(__n);
          __try
            {
              std::__uninitialized_fill_a(this->_M_impl._M_finish,
                          __new_finish, __x,
                          _M_get_Tp_allocator());
              this->_M_impl._M_finish = __new_finish;
            }
          __catch(...)
            {
              _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
                       __new_finish._M_node + 1);
              __throw_exception_again;
            }
        }
          else
        _M_insert_aux(__pos, __n, __x);
        }
    
    

    _M_insert_aux() 定义如下,根据插入位置,决定移动较少部分元素,腾出 n 个元素的空间。

    /// deque.tcc
      template <typename _Tp, typename _Alloc>
        void
        deque<_Tp, _Alloc>::
        _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
        {
          const difference_type __elems_before = __pos - this->_M_impl._M_start;
          const size_type __length = this->size();
          value_type __x_copy = __x;
          if (__elems_before < difference_type(__length / 2))
        { // 移动前半部
          iterator __new_start = _M_reserve_elements_at_front(__n);
          iterator __old_start = this->_M_impl._M_start;
          __pos = this->_M_impl._M_start + __elems_before;
          __try
            {
              if (__elems_before >= difference_type(__n))
            {
              iterator __start_n = (this->_M_impl._M_start
                        + difference_type(__n));
              std::__uninitialized_move_a(this->_M_impl._M_start,
                              __start_n, __new_start,
                              _M_get_Tp_allocator());
              this->_M_impl._M_start = __new_start;
              _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
              std::fill(__pos - difference_type(__n), __pos, __x_copy);
            }
              else
            {
              std::__uninitialized_move_fill(this->_M_impl._M_start,
                             __pos, __new_start,
                             this->_M_impl._M_start,
                             __x_copy,
                             _M_get_Tp_allocator());
              this->_M_impl._M_start = __new_start;
              std::fill(__old_start, __pos, __x_copy);
            }
            }
          __catch(...)
            {
              _M_destroy_nodes(__new_start._M_node,
                       this->_M_impl._M_start._M_node);
              __throw_exception_again;
            }
        }
          else
        { // 移动后半部
          iterator __new_finish = _M_reserve_elements_at_back(__n);
          iterator __old_finish = this->_M_impl._M_finish;
          const difference_type __elems_after =
            difference_type(__length) - __elems_before;
          __pos = this->_M_impl._M_finish - __elems_after;
          __try
            {
              if (__elems_after > difference_type(__n))
            {
              iterator __finish_n = (this->_M_impl._M_finish
                         - difference_type(__n));
              std::__uninitialized_move_a(__finish_n,
                              this->_M_impl._M_finish,
                              this->_M_impl._M_finish,
                              _M_get_Tp_allocator());
              this->_M_impl._M_finish = __new_finish;
              _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
              std::fill(__pos, __pos + difference_type(__n), __x_copy);
            }
              else
            {
              std::__uninitialized_fill_move(this->_M_impl._M_finish,
                             __pos + difference_type(__n),
                             __x_copy, __pos,
                             this->_M_impl._M_finish,
                             _M_get_Tp_allocator());
              this->_M_impl._M_finish = __new_finish;
              std::fill(__pos, __old_finish, __x_copy);
            }
            }
          __catch(...)
            {
              _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
                       __new_finish._M_node + 1);
              __throw_exception_again;
            }
        }
        }
    
    

    最后一种是插入迭代器指向的区间元素,比如 insert(pos, begin, end)

    /// stl_deque.h
          template<typename _InputIterator,
               typename = std::_RequireInputIter<_InputIterator>>
        iterator
        insert(const_iterator __position, _InputIterator __first,
               _InputIterator __last)
        {
          difference_type __offset = __position - cbegin();
          _M_range_insert_aux(__position._M_const_cast(), __first, __last,
                      std::__iterator_category(__first));
          return begin() + __offset;
        }
    
    

    _M_range_insert_aux() 需要区分迭代器类型,如果是 input_iterator_tag,调用 std::copy() 单个元素进行插入。否则处理方式和 _M_fill_insert() 函数类似。

    /// deque.tcc
      template <typename _Tp, typename _Alloc>
        template <typename _InputIterator>
          void
          deque<_Tp, _Alloc>::
          _M_range_insert_aux(iterator __pos,
                  _InputIterator __first, _InputIterator __last,
                  std::input_iterator_tag)
          { std::copy(__first, __last, std::inserter(*this, __pos)); }
    
      template <typename _Tp, typename _Alloc>
        template <typename _ForwardIterator>
          void
          deque<_Tp, _Alloc>::
          _M_range_insert_aux(iterator __pos,
                  _ForwardIterator __first, _ForwardIterator __last,
                  std::forward_iterator_tag)
          {
        const size_type __n = std::distance(__first, __last);
        if (__pos._M_cur == this->_M_impl._M_start._M_cur)
          {
            iterator __new_start = _M_reserve_elements_at_front(__n);
            __try
              {
            std::__uninitialized_copy_a(__first, __last, __new_start,
                            _M_get_Tp_allocator());
            this->_M_impl._M_start = __new_start;
              }
            __catch(...)
              {
            _M_destroy_nodes(__new_start._M_node,
                     this->_M_impl._M_start._M_node);
            __throw_exception_again;
              }
          }
        else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
          {
            iterator __new_finish = _M_reserve_elements_at_back(__n);
            __try
              {
            std::__uninitialized_copy_a(__first, __last,
                            this->_M_impl._M_finish,
                            _M_get_Tp_allocator());
            this->_M_impl._M_finish = __new_finish;
              }
            __catch(...)
              {
            _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
                     __new_finish._M_node + 1);
            __throw_exception_again;
              }
          }
        else
          _M_insert_aux(__pos, __first, __last, __n);
          }
    
    

    _M_insert_aux() 函数处理方法类似,根据插入位置,决定移动较少部分元素,腾出 n 个元素的空间,然后将 [first, last) 拷贝 n 个元素到 deque。

欢迎关注公众号“源知源为”,阅读更多技术干货
#STL#
C/C++基础 文章被收录于专栏

C/C++ 语言基础

全部评论

相关推荐

3 5 评论
分享
牛客网
牛客企业服务