首页 > STL源码剖析 > STL笔记之deque

STL笔记之deque

deque是双端队列,在队列头部和尾部可以快速的进行元素的插入和删除操作,相比vector而言有一定的优势,同时由于内部构造的设计,不存在vector那样扩充时带来的“配置新空间 / 移动旧数据 / 释放旧空间”问题。deque还提供Random Access Iterator,可以随机访问容器内的元素。deque同时还是STL中queue和stack的底层依赖组件。

1. deque结构设计
如果只是平时使用deque的话,可能就想不到其内部实现细节了。下面的图片展示deque的内部结构设计:
deque内部结构
可以看到,deque拥有一个bitmap结构(称之为map),map中每一个元素指向一块连续的内存块,后者才是真正存储deque元素的地方,因为每个块都是固定大小的,但是每个块之间不要求是连续的,所以扩充空间的时候,就没有vector那样的副作用了。

鉴于deque的特殊设计,其迭代器也需要特殊设计,deque的iterator的设计结构如图:
deque迭代器设计
迭代器内部维护了四个指针,分别为cur, first, last, node,具体在后面进行介绍。

2. deque迭代器
deque的迭代器的设计,主要是让其看起来像一个random access iterator,因此源码主要各种operator的重载。内部结构分为四个指针,分别为cur, first, last, node。

在某一个时刻,迭代器肯定指向某个具体元素,而这个元素位于N段连续内存块中的某一块,其中node指向map结构中的一个节点(这个节点指向当前的内存块),first指向当前内存块的起始位置,cur指向当前内存块中的特定元素节点,last指向当前内存块的末尾位置,一图抵千言,还是看图来的明白:
STL deque iterator结构
deque iterator的源码分析如下:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// ============================================================================
// 一个连续内存块容纳的元素数量
// ============================================================================
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)); }
 
  // deque 的 iterator 是 random access iterator
  typedef 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 _Tp** _Map_pointer;
 
  typedef _Deque_iterator _Self;
 
  // ==========================================================================
  // 内部指针定义: cur, first, last, node
  // ==========================================================================
  _Tp* _M_cur;
  _Tp* _M_first;
  _Tp* _M_last;
  _Map_pointer _M_node; // T** 类型
 
  // 各种构造函数
  _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) {}
 
  // ==========================================================================
  // iterator的各种操作
  // ==========================================================================
  // 解引用
  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) {
      // 如果到达末尾了,需要跳转到下一个内存块
      _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()))
      _M_cur += __n;
    else {
      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;
  }
 
  // 下标操作
  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); }
 
  // 更新当前指向的内存块
  void _M_set_node(_Map_pointer __new_node) {
    _M_node = __new_node;
    _M_first = *__new_node;
    _M_last = _M_first + difference_type(_S_buffer_size());
  }
};

3. deque分析
deque的构造函数中会进行map结构的初始化操作,通过调用_M_initialize_map来实现,默认map的大小为8. 或者,当用户指定了每个内存块容纳的元素个数时,根据每个内存块默认的大小,算出需要多少个map指针,再加上2. 随后创建map需要的空间,并让start和finish尽可能落在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
49
// enum { _S_initial_map_size = 8 };
// ============================================================================
// _M_initialize_map 初始化map
//      __num_elements : 每一个内存块存储的元素个数
// ============================================================================
template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
{
  // 计算实际需要map的大小
  size_t __num_nodes = 
    __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
  // 从默认大小和实际大小中取最大值
  _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
  // 创建map
  _M_map = _M_allocate_map(_M_map_size);
 
  // 让start和finish落在map的中间位置,使得头部和尾部都方便扩充
  _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
  _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));
  // 设置start和finish的内容
  _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));
}
 
// 分配实际存储元素的内存块空间
template <class _Tp, class _Alloc>
void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
{
  _Tp** __cur;
  __STL_TRY {
    for (__cur = __nstart; __cur < __nfinish; ++__cur)
      *__cur = _M_allocate_node();
  }
  __STL_UNWIND(_M_destroy_nodes(__nstart, __cur));
}
 
_Tp* _M_allocate_node()
{
  return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
}

deque支持push_back / pop_back / push_front / pop_font,实现机制都是类似的,这里以push_back为例进行分析。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// ============================================================================
// deuqe class
// ============================================================================
template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class deque : protected _Deque_base<_Tp, _Alloc> {
public:
  // ==========================================================================
  // push_back() 操作
  // ==========================================================================
  void push_back(const value_type& __t) {
    // 如果还有多余1个节点的空间,则直接构造,否则借助_M_push_back_aux实现
    if (_M_finish._M_cur != _M_finish._M_last - 1) {
      construct(_M_finish._M_cur, __t);
      ++_M_finish._M_cur;
    }
    else
      _M_push_back_aux(__t);
  }
 
protected:
  // ==========================================================================
  // push_back() 依赖的内部操作
  // ==========================================================================
  void _M_push_back_aux(const value_type& __t)
  {
    value_type __t_copy = __t;
    // 确保map还有剩余空间
    _M_reserve_map_at_back();
    // 构造一块新的内存块,并填充map对应的节点
    *(_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)
  {
    // 如果剩余空间不够,则需要扩充map了
    if (__nodes_to_add + 1 > _M_map_size - (_M_finish._M_node - _M_map))
      _M_reallocate_map(__nodes_to_add, false);
  }
 
  // 默认在尾部扩充
  void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
  {
    // map中已经被填充的节点的个数
    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;
 
    _Map_pointer __new_nstart;
    // 如果map的大小比需要被填充的节点个数的两倍还大
    // 则将map中start, finish区间往前移动即可
    if (_M_map_size > 2 * __new_num_nodes) {
      __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 {
      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;
    }
 
    _M_start._M_set_node(__new_nstart);
    _M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
  }
  // ...
}

deque还有很多内部/外部函数,也都是围绕deque自身独特的设计进行操作,这里不再分析。

4. Adapter设计模式
STL出现最多的两个模式是迭代器模式和适配器模式(配接器模式、Adapter Pattern),这两个模式都是GoF提出的经典设计模式。

适配器模式(英语:adapter pattern)有时候也称包装样式或者包装。将一个类的接口转接成用户所期待的。一个适配使得因接口不兼容而不能在一起工作的类工作在一起,做法是将类别自己的接口包裹在一个已存在的类中。

举个例子:我的笔记本电脑的工作电压是20V,而家庭用电是220V,如何让20V的笔记本电脑能够在220V的电压下工作?答案是引入一个电源适配器(AC Adapter),俗称充电器或变压器。

STL中queue和stack就是应用于deque的适配器模式的例子,他们的代码都很简单,都是基于deque实现的,是对deque进行的包装。这对用户而言是透明的,就好比使用priority_queue的时候不需要知道内部是heap实现的一样。

适配器模式的结构如图所示:
Adapter设计模式
在这里,程序猿就是Client,stack/queue就是Target(或者说Adapter,因为没有继承结构,所以不需要面向接口编程了),而deque就是Adaptee了,在使用stack/queue的时候,程序猿不需要知道底层是由deque实现的。

5. stack和queue
stack的源码如下(删除了比较操作符相关代码):

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
// stack默认基于deque实现
template <class _Tp, 
          class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) >
class stack;
 
template <class _Tp, class _Sequence>
class stack {
public:
  typedef typename _Sequence::value_type      value_type;
  typedef typename _Sequence::size_type       size_type;
  typedef          _Sequence                  container_type;
 
  typedef typename _Sequence::reference       reference;
  typedef typename _Sequence::const_reference const_reference;
protected:
  // 内部容器
  _Sequence c;
public:
  // 构造函数
  stack() : c() {}
  explicit stack(const _Sequence& __s) : c(__s) {}
 
  // 基于容器c实现的操作
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  reference top() { return c.back(); }
  const_reference top() const { return c.back(); }
  void push(const value_type& __x) { c.push_back(__x); }
  void pop() { c.pop_back(); }
};

queue的源码如下(删除了比较操作符相关代码):

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
// queue默认基于deque实现
template <class _Tp, 
          class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) >
class queue;
 
template <class _Tp, class _Sequence>
class queue {
public:
  typedef typename _Sequence::value_type      value_type;
  typedef typename _Sequence::size_type       size_type;
  typedef          _Sequence                  container_type;
 
  typedef typename _Sequence::reference       reference;
  typedef typename _Sequence::const_reference const_reference;
 
protected:
  // 内部容器c
  _Sequence c;
public:
  queue() : c() {}
  explicit queue(const _Sequence& __c) : c(__c) {}
 
  // 基于c实现的函数
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  reference front() { return c.front(); }
  const_reference front() const { return c.front(); }
  reference back() { return c.back(); }
  const_reference back() const { return c.back(); }
  void push(const value_type& __x) { c.push_back(__x); }
  void pop() { c.pop_front(); }
};

STL源码剖析笔记系列
1. STL笔记之空间配置器
2. STL笔记之迭代器
3. STL笔记之vector
4. STL笔记之list
5. STL笔记之优先队列
6. STL笔记之deque

参考
http://zh.wikipedia.org/wiki/适配器模式
http://blog.csdn.net/lovelion/article/details/8624325
《设计模式 可复用面向对象软件的基础》


觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> STL笔记之deque
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



  1. 本文目前尚无任何评论.