deque

双向开口的连续线性空间，因为要在头部也要插入，所以不是简单的像vector一样分配。

deque没有容量的概念，实际上底层是以分段连续空间组合而成。

Constructor

指定初值。such as:deque l = {2,3,1};

1
2
3
4
5
6
7
    deque(initializer_list<value_type> __l,
    const allocator_type& __a = allocator_type())
    : _Base(__a)
    {
_M_range_initialize(__l.begin(), __l.end(),
            random_access_iterator_tag());
    }

这样的调用的是_M_range_initialize

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
template <typename _Tp, typename _Alloc>
  template <typename _ForwardIterator>
    void
    deque<_Tp, _Alloc>::
    _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
                        std::forward_iterator_tag)
    {
      const size_type __n = std::distance(__first, __last);
      this->_M_initialize_map(__n);

      _Map_pointer __cur_node;
      __try
        {
            //尝试遍历map中的节点并调用__uniintialized_copy_a将初值拷贝进去，最后将剩下的一点拷贝进最后一个缓冲区
          for (__cur_node = this->_M_impl._M_start._M_node;
               __cur_node < this->_M_impl._M_finish._M_node;
               ++__cur_node)
     {
_ForwardIterator __mid = __first;
std::advance(__mid, _S_buffer_size());
std::__uninitialized_copy_a(__first, __mid, *__cur_node,
			    _M_get_Tp_allocator());
__first = __mid;
     }
          std::__uninitialized_copy_a(__first, __last,
			this->_M_impl._M_finish._M_first,
			_M_get_Tp_allocator());
        }
      __catch(...)
        {
          std::_Destroy(this->_M_impl._M_start,
	  iterator(*__cur_node, __cur_node),
	  _M_get_Tp_allocator());
          __throw_exception_again;
        }
    }

首先得到长度，再初始化map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 template<typename _Tp, typename _Alloc>
   void
   _Deque_base<_Tp, _Alloc>::
   _M_initialize_map(size_t __num_elements)
   {
       //单个连续缓冲区大小为512字节
       <!-- #ifndef _GLIBCXX_DEQUE_BUF_SIZE
       #define _GLIBCXX_DEQUE_BUF_SIZE 512
       #endif

       inline size_t
       __deque_buf_size(size_t __size)
       { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
    ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); } -->


     const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
			  + 1);

       //_M_map_size最小为8
     this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
				   size_t(__num_nodes + 2));
     this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);


       //这里注意到，map中的节点地址，并不是从头开始存放的，而是尽量往中间存放。
       //因为需要应对两头存放时可能需要分配新的缓冲区，若直接在头部存放，则push_front容易变得低效，因为可能得经常变动map。
     _Tp** __nstart = (this->_M_impl._M_map
		+ (this->_M_impl._M_map_size - __num_nodes) / 2);
     _Tp** __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 = 0;
  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)));           //最后一个元素后的位置
   }

这里可以看到该结构体主要有四个部分，

  1. _M_map，指向map地址，map中存储各个缓冲区的地址。
  2. _M_map_size，指定map大小。
  3. _M_start，指向map中第一个节点的缓冲区。
    struct _Deque_iterator
    {
    _TP _M_cur; 使用中的缓冲区指针
    _Tp     _M_first; 第一个缓冲区的头指针
    _Tp* _M_last; 第一个缓冲区的尾指针
    _Tp** _M_node; 在map中的node的位置
    }
  4. _M_finish，指向map中最后一个节点的缓冲区，结构与_M_start相同。

初始化就是进行空间的分配及对这些值进行相应的设置。

同时注意到后两个就是deque的迭代器，其重构了许多符号来应对空间的不连续操作，因为比较简单就不分析了。

push_back && pop_back && push_front && pop_front

  1. push_back
1
2
3
void
push_back(value_type&& __x)
{ emplace_back(std::move(__x)); }

跟进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<typename _Tp, typename _Alloc>
template<typename... _Args>
    void
    deque<_Tp, _Alloc>::
    emplace_back(_Args&&... __args)
    {
if (this->_M_impl._M_finish._M_cur
    != this->_M_impl._M_finish._M_last - 1)  //最后一个缓冲区还有位置
    {
    this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
                std::forward<_Args>(__args)...);
    ++this->_M_impl._M_finish._M_cur;
    }
else
    _M_push_back_aux(std::forward<_Args>(__args)...);
    }

分析下没有位置的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template<typename _Tp, typename _Alloc>
template<typename... _Args>
    void
    deque<_Tp, _Alloc>::
    _M_push_back_aux(_Args&&... __args)
    {
        //若map中节点位置已满，则需要一块更大的缓冲区存放map，这里调用的是_M_reallocate_map
_M_reserve_map_at_back();
          <!-- 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);  
            } -->
*(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); 分配新节点
__try
    {
    this->_M_impl.construct(this->_M_impl._M_finish._M_cur,
                std::forward<_Args>(__args)...);
    this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node  //_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;
    }
    }

对map的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 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;

     //如果原先map足够大，则根据需要移动下map中的指针即可
     if (this->_M_impl._M_map_size > 2 * __new_num_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);
}
       //若map大小不够，则需要重新分配map，并把原先的map拷贝到新map中特定的位置
     else
{
  size_type __new_map_size = this->_M_impl._M_map_size
                             + std::max(this->_M_impl._M_map_size,
					__nodes_to_add) + 2;

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

  1. pop_back
1
2
3
4
5
6
7
8
9
10
11
12
13
    void
    pop_back() _GLIBCXX_NOEXCEPT  
    {
        //若最后一个缓冲区不为空，则直接弹出
if (this->_M_impl._M_finish._M_cur
    != this->_M_impl._M_finish._M_first)
    {
    --this->_M_impl._M_finish._M_cur;
    this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
    }
else
    _M_pop_back_aux();
    }

否则回收最后一个节点，调整_M_finish结构为前一个node节点的缓冲区并将最后一个元素弹出

1
2
3
4
5
6
7
8
9
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::
_M_pop_back_aux()
{
    _M_deallocate_node(this->_M_impl._M_finish._M_first);
    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;
    this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
}

这里发现即使deque中为空也不会报错

  1. push_front && pop_front

流程与push_back，pop_back基本一致，不再做过多分析。