Summary

STL deque——part 1

deque概述

deque是一个双端队列

1
2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class T, class Alloc = alloc, size_t BufSiz = 0>   
class deque {  
public:                         // Basic types  
  typedef T value_type;  
  typedef value_type* pointer;  
  ···
protected:                      // Data members  
  iterator start;       // start.cur指向deque的第一个结点  
  iterator finish;  // finish.cur指向迭代器deque的最后一个结点的后一个元素  
  
  map_pointer map;  // 指向中控器。其实是指向中控器的第一个结点。  
                    //  中控器是连续的，map_size定义了中控器的大小。  
                           
  size_type map_size;   // 中控器的大小。
  ...
};

3

deque 迭代器

4

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
140
141
142
143
144
145
146
/* 
此函数用来计算缓冲区的大小 
如果n不等于0，那么返回n，开发者自己决定 
    否则：如果sz小于512，返回512/sz 
    	如果sz大于512，返回1 
*/  
inline size_t __deque_buf_size(size_t n, size_t sz)  
{  
  return n != 0 ? n : (sz < 512 ? size_t(512 / sz) : size_t(1));  
}  
  
  
//deque的迭代器，未继承std::iterator  
template <class T, class Ref, class Ptr, size_t BufSiz>  
struct __deque_iterator {     
  typedef __deque_iterator<T, T&, T*, BufSiz>      iterator;  
  typedef __deque_iterator<T, const T&, const T*, BufSiz> const_iterator;  
  static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }  
  
  //没有继承std::iterator，自己定义5个迭代器相应型别。  
    
  typedef random_access_iterator_tag iterator_category; // (1)  
  typedef T value_type;                 // (2)  
  typedef Ptr pointer;              // (3)  
  typedef Ref reference;                // (4)  
  typedef size_t size_type;  
  typedef ptrdiff_t difference_type;    // (5)  
  typedef T** map_pointer;  //注意，是指针的指针  
  //map_pointer指向中控器，中控器的存储的是指针，指向node-buf结点缓冲区  
  
  typedef __deque_iterator self;  

  
  T* cur;   // 迭代器所指元素  
  T* first; // 迭代器所指元素所在缓冲区的开头  
  T* last;  // 迭代器所指元素所在缓冲区的结尾（结尾包含在缓冲区内）  
  map_pointer node;//指向中控器的结点，这个结点指向迭代器所指元素所在的缓冲区  
    
//迭代器的构造函数  
  
    //x是迭代器所指结点，y为中控器中的结点的值，指向x所指缓冲区  
  __deque_iterator(T* x, map_pointer y)   
    : cur(x), first(*y), last(*y + buffer_size()), node(y) {}  
    //默认构造函数  
  __deque_iterator() : cur(0), first(0), last(0), node(0) {}  
    //用一个迭代器x初始化本迭代器  
  __deque_iterator(const iterator& x)  
    : cur(x.cur), first(x.first), last(x.last), node(x.node) {}  
  
  //迭代器需要重载的运算符  
  reference operator*() const { return *cur; }   
/* 
两个迭代器之间的距离。这两个迭代器可能不在同一个buffer上。 
*/  
  difference_type operator-(const self& x) const {  
    return difference_type(buffer_size()) * (node - x.node - 1) +  
      (cur - first) + (x.last - x.cur);  
  }  
    
  /* 
    迭代器前进一步。 
    先++cur，再判断cur==last。说明cur不会指向last的。last所指空间不存内容 
  */  
  self& operator++() {  
    ++cur;              // 前进一步  
    if (cur == last) {      // 到了所在缓冲区的尾端了  
      set_node(node + 1);   // 切换到下一个缓冲区  
      cur = first;          //   的第一个元素  
    }  
    return *this;   
  }  
  self operator++(int)  {  
    self tmp = *this;  
    ++*this;  
    return tmp;  
  }  
  //迭代器往回走一步。  
  self& operator--() {  
    if (cur == first) { // 如果在所在缓冲区的头部  
      set_node(node - 1);   // 切换到前一个缓冲区  
      cur = last;           //   的最后一个元素  
    }  
    --cur;              // 直接往回走一步  
    return *this;  
  }  
  self operator--(int) {  
    self tmp = *this;  
    --*this;  
    return tmp;  
  }  
  
  /* 
    迭代器向前进或后退n步（取决于n的正负）。这是支持random access iterator 所必须的操作。 
    如果这个操作不会是迭代器走出当前所在缓冲区，直接更改cur即可。 
    如果这个操作使迭代器走出当前所在缓冲区，要计算出操作后在哪个缓冲区的哪个位置。 
  */  
  self& operator+=(difference_type n) {  
    difference_type offset = n + (cur - first);  
    if (offset >= 0 && offset < difference_type(buffer_size()))  
      // 不会走出当前所在缓冲区  
      cur += n;  
    else {  
      // 走出了当前所在缓冲区  
      difference_type node_offset =  
        offset > 0 ? offset / difference_type(buffer_size())  
                   : -difference_type((-offset - 1) / buffer_size()) - 1;  
      // 切换缓冲区  
      set_node(node + node_offset);  
      // 找到切换缓冲区后，迭代器所指向的元素  
      cur = first + (offset - node_offset * difference_type(buffer_size()));  
    }  
    return *this;  
  }  
  
  
  self operator+(difference_type n) const {  
    self tmp = *this;  
    return tmp += n; // 调用operator+=  
  }  
    //调用operator+=  
  self& operator-=(difference_type n) { return *this += -n; }  
    
  
  
  self operator-(difference_type n) const {  
    self tmp = *this;  
    return tmp -= n; // 调用operator-=  
  }  
  
  reference operator[](difference_type n) const { return *(*this + n); }  
  // 以上调用了operator*, operator+  
  
  /*迭代器关于比较的运算符的重载*/  
  bool operator==(const self& x) const { return cur == x.cur; }  
  bool operator!=(const self& x) const { return !(*this == x); }  
  bool operator<(const self& x) const {  
    return (node == x.node) ? (cur < x.cur) : (node < x.node);  
  }  
  
  //切换缓冲区，更改了first和last，但是未更改cur  
  void set_node(map_pointer new_node) {  
    node = new_node;  
    first = *new_node;  
    last = first + difference_type(buffer_size());  
  }  
};

5

deque的定义

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
template <class T, class Alloc = alloc, size_t BufSiz = 0>   
class deque {  
public:                         // Basic types  
  typedef T value_type;  
  typedef value_type* pointer;  
  typedef const value_type* const_pointer;  
  typedef value_type& reference;  
  typedef const value_type& const_reference;  
  typedef size_t size_type;  
  typedef ptrdiff_t difference_type;  
  
public:                         // 迭代器  
  typedef __deque_iterator<T, T&, T*, BufSiz>              iterator;  
  typedef __deque_iterator<T, const T&, const T&, BufSiz>  const_iterator;  

  typedef reverse_iterator<const_iterator> const_reverse_iterator;  
  typedef reverse_iterator<iterator> reverse_iterator;  

  
protected:                      // Internal typedefs  
  // 指向中控器，是指针的指针（pointer of pointer of T）  
  typedef pointer* map_pointer;   
  // 空间配置器，用来配置缓冲区  
  typedef simple_alloc<value_type, Alloc> data_allocator;  
  // 空间配置器，用来配置中控器  
  typedef simple_alloc<pointer, Alloc> map_allocator;  
  
  static size_type buffer_size() {  
    return __deque_buf_size(BufSiz, sizeof(value_type));  
  }  
  //默认中控器大小为8  
  static size_type initial_map_size() { return 8; }  
  
protected:                      // Data members  
  iterator start;       // start.cur指向deque的第一个结点  
  iterator finish;  // finish.cur指向迭代器deque的最后一个结点的后一个元素  
  
  map_pointer map;  // 指向中控器。其实是指向中控器的第一个结点。  
                    //  中控器是连续的，map_size定义了中控器的大小。  
                           
  size_type map_size;   // 中控器的大小。  
  
public:                         // 对外的接口  
  iterator begin() { return start; }  
  iterator end() { return finish; }  
  const_iterator begin() const { return start; }  
  const_iterator end() const { return finish; }  
  
  reverse_iterator rbegin() { return reverse_iterator(finish); }  
  reverse_iterator rend() { return reverse_iterator(start); }  
  const_reverse_iterator rbegin() const {  
    return const_reverse_iterator(finish);  
  }  
  const_reverse_iterator rend() const {  
    return const_reverse_iterator(start);  
  }  
  
  reference operator[](size_type n) {  
    return start[difference_type(n)]; // 调用 __deque_iterator<>::operator[]  
  }  
  const_reference operator[](size_type n) const {  
    return start[difference_type(n)];  
  }  
  
  reference front() { return *start; } // 调用 __deque_iterator<>::operator*  
    
  //取出最后一个元素  
  reference back() {  
    iterator tmp = finish;    
    --tmp;  // 调用 __deque_iterator<>::operator--  
    return *tmp;    // 调用 __deque_iterator<>::operator*  
  }  
    
  //返回第一个元素，并不删除  
  const_reference front() const { return *start; }  
  const_reference back() const {  
    const_iterator tmp = finish;  
    --tmp;  
    return *tmp;  
  }  
  
  //两分号但是合法
  size_type size() const { return finish - start;; }   
    //deque最大容量。  
  size_type max_size() const { return size_type(-1); }  
  //下面调用了operator::iterator==  
  bool empty() const { return finish == start; }  
  
public:       
    
   //默认构造函数  
  deque(): start(), finish(), map(0), map_size(0)  
  {  
    create_map_and_nodes(0);  
  }  
//用一个deque构建新的deque  
  deque(const deque& x)  
    : start(), finish(), map(0), map_size(0)  
  {  
    create_map_and_nodes(x.size());  
    __STL_TRY {  
      uninitialized_copy(x.begin(), x.end(), start);  
    }  
    //commit or rollback  
    __STL_UNWIND(destroy_map_and_nodes());  
  }  
//构建大小为n，元素值为value的deque  
  deque(size_type n, const value_type& value)  
    : start(), finish(), map(0), map_size(0)  
  {  
    fill_initialize(n, value);  
  }  
  
  deque(int n, const value_type& value)  
    : start(), finish(), map(0), map_size(0)  
  {  
    fill_initialize(n, value);  
  }  
   
  deque(long n, const value_type& value)  
    : start(), finish(), map(0), map_size(0)  
  {  
    fill_initialize(n, value);  
  }  
//构建大小为n的deque，默认值为T(),说明deque容器的元素要有默认构造函数  
  explicit deque(size_type n)  
    : start(), finish(), map(0), map_size(0)  
  {  
    fill_initialize(n, value_type());  
  }  
   
  template <class InputIterator>  
  deque(InputIterator first, InputIterator last)  
    : start(), finish(), map(0), map_size(0)  
  {  
    range_initialize(first, last, iterator_category(first));  
  }  
 
  ~deque() {  
    destroy(start, finish);  
    destroy_map_and_nodes();  
  }  
  
  deque& operator= (const deque& x) {  
    const size_type len = size();  
    if (&x != this) {  
      if (len >= x.size())  
        erase(copy(x.begin(), x.end(), start), finish);  
      else {  
        const_iterator mid = x.begin() + difference_type(len);  
        copy(x.begin(), mid, start);  
        insert(finish, mid, x.end());  
      }  
    }  
    return *this;  
  }          
  
  void swap(deque& x) {  
    __STD::swap(start, x.start);  
    __STD::swap(finish, x.finish);  
    __STD::swap(map, x.map);  
    __STD::swap(map_size, x.map_size);  
  }