Summary

STL deque——part 2

接下来介绍一下deque的插入删除操作及其他操作(push, pop …)
常见的有push_back, push_front, pop_back, pop_front, insert, erase, clear等
包括了内存分配和释放等问题

push pop

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
  //在deque末尾添加元素  
  void push_back(const value_type& t) {  
    if (finish.cur != finish.last - 1) {   
      // 当前缓冲区还有空间  
      construct(finish.cur, t); // 直接在可用空间构建  
      ++finish.cur; // 调整finish迭代器  
    }  
    else  // 当前缓冲区无可用空间（last不能存储元素用）  
      push_back_aux(t);  
  }  
  
  //在deque头添加元素  
  void push_front(const value_type& t) {  
    if (start.cur != start.first) {     // 当前缓冲区还有空间  
      construct(start.cur - 1, t);   
      --start.cur;        
    }  
    else // 当前缓冲区无空间可用了  
      push_front_aux(t);  
  }  
    
    //删掉末尾元素  
  void pop_back() {  
    if (finish.cur != finish.first) {//最后一个缓冲区（finish指的缓冲区）有多于一个元素（含一个）  
      --finish.cur;       
      destroy(finish.cur);    
    }  
    else  
      // 最后一个缓冲区无元素  
      pop_back_aux();       // 这里会进行缓冲区的释放工作  
  }  
  
  //在deque头删除元素  
  void pop_front() {  
    if (start.cur != start.last - 1) {  
      // start.node所指缓冲区有多余一个元素（不含一个）  
      destroy(start.cur);     
      ++start.cur;    
    }  
    else   
      // start.node所指缓冲区只有一个元素  
      pop_front_aux();      // 这里会进行缓冲区释放工作  
  }  

template <class T, class Alloc, size_t BufSize>  
void deque<T, Alloc, BufSize>::push_back_aux(const value_type& t) {  
  value_type t_copy = t;  
  reserve_map_at_back();        //  若符合某重条件则必须重换一个map  
  *(finish.node + 1) = allocate_node(); // 配置一个新结点（缓冲区）  
  __STL_TRY {  
    construct(finish.cur, t_copy);      // 设置值  
    finish.set_node(finish.node + 1);   // 改变finish，令其指向新结点  
    finish.cur = finish.first;          // 设置 finish 的状态  
  }  
  __STL_UNWIND(deallocate_node(*(finish.node + 1)));  
}  
  
// 只有当start.cur == start.first才会调用。  
// 第一个缓冲区没有未用空间时才会调用。和上面实现类似  
template <class T, class Alloc, size_t BufSize>  
void deque<T, Alloc, BufSize>::push_front_aux(const value_type& t) {  
  value_type t_copy = t;  
  reserve_map_at_front();         
  *(start.node - 1) = allocate_node();    
  __STL_TRY {  
    start.set_node(start.node - 1);       
    start.cur = start.last - 1;           
    construct(start.cur, t_copy);         
  }
}  
// 只有当finish.cur == finish.first才会调用  
template <class T, class Alloc, size_t BufSize>  
void deque<T, Alloc, BufSize>::pop_back_aux() {  
  deallocate_node(finish.first);      
  finish.set_node(finish.node - 1);   
  finish.cur = finish.last - 1;       
  destroy(finish.cur);        
}   
// 只有当start.cur == start.last - 1时才会调用  
template <class T, class Alloc, size_t BufSize>  
void deque<T, Alloc, BufSize>::pop_front_aux() {  
  destroy(start.cur);                 
  deallocate_node(start.first);   
  start.set_node(start.node + 1);  
  start.cur = start.first;  
}  



  //在map尾添加缓冲区  
  void reserve_map_at_back (size_type nodes_to_add = 1) {  
    if (nodes_to_add + 1 > map_size - (finish.node - map))  
    //map空间不够用，则开辟新的map空间，把原来map内容拷贝过来。释放原来的  
      reallocate_map(nodes_to_add, false);   
  }  
  
  //在map头添加缓冲区  
  void reserve_map_at_front (size_type nodes_to_add = 1) {  
    if (nodes_to_add > start.node - map)  
      reallocate_map(nodes_to_add, true);     
  }  

//添加map结点，指向新的缓冲区，add_at_front=true添加在map头，否则添加在尾  
template <class T, class Alloc, size_t BufSize>  
void deque<T, Alloc, BufSize>::reallocate_map(size_type nodes_to_add,  
                                              bool add_at_front) {  
  size_type old_num_nodes = finish.node - start.node + 1;  
  size_type new_num_nodes = old_num_nodes + nodes_to_add;  
  
  map_pointer new_nstart;  
  if (map_size > 2 * new_num_nodes) {  
    new_nstart = map + (map_size - new_num_nodes) / 2   
                     + (add_at_front ? nodes_to_add : 0);  
    if (new_nstart < start.node)  
      copy(start.node, finish.node + 1, new_nstart);  
    else  
      copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);  
  }  
  else {  
    size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;  
    // 配置新的结点，准备给map使用  
    map_pointer new_map = map_allocator::allocate(new_map_size);  
    new_nstart = new_map + (new_map_size - new_num_nodes) / 2  
                         + (add_at_front ? nodes_to_add : 0);  
    // 把原map 內容拷贝  
    copy(start.node, finish.node + 1, new_nstart);  
    // 释放放原map  
    map_allocator::deallocate(map, map_size);  
    // 设置新map起始位置和大小  
    map = new_map;  
    map_size = new_map_size;  
  }  
  
  // 重新设置迭代器 start 和 finish  
  start.set_node(new_nstart);  
  finish.set_node(new_nstart + old_num_nodes - 1);  
}

insert

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
  // 在position 处插入一個元素，其值为 x  
  iterator insert(iterator position, const value_type& x) {  
    if (position.cur == start.cur) {      // position是deque的最前端，则调用push_front()
      push_front(x);      
      return start;  
    }  
    else if (position.cur == finish.cur) {   // position是deque的最末端，则调用push_back()
      push_back(x);  
      iterator tmp = finish;  
      --tmp;  
      return tmp;  
    }  
    else {  
      return insert_aux(position, x);       // 都不是就交给insert_aux 去做  
    }  
  }  
//在pos处插入一个元素，值为x。要判断插入点距头更近还是尾更近
template <class T, class Alloc, size_t BufSize>  
typename deque<T, Alloc, BufSize>::iterator  
deque<T, Alloc, BufSize>::insert_aux(iterator pos, const value_type& x) {  
  difference_type index = pos - start;    
  value_type x_copy = x;  
  if (index < size() / 2) {    //插入点之前的元素少
    push_front(front());          
    iterator front1 = start;  
    ++front1;  
    iterator front2 = front1;  
    ++front2;  
    pos = start + index;  
    iterator pos1 = pos;  
    ++pos1;  
    copy(front2, pos1, front1);  
  }  
  else {                      //插入点之后的元素少
    push_back(back());        
    iterator back1 = finish;  
    --back1;  
    iterator back2 = back1;  
    --back2;  
    pos = start + index;  
    copy_backward(pos, back2, back1);     
  }  
  *pos = x_copy;      
  return pos;  
}

resize

1
2
3
4
5
6
7
8
9
10
//调整deque的大小。
  void resize(size_type new_size, const value_type& x) {  
    const size_type len = size();  
    if (new_size < len)   //如果deque变小，直接擦除掉多余的元素
      erase(start + new_size, finish);  
    else  
      insert(finish, new_size - len, x);  //如果deque变大，则在deque后面插入元素补充
  }  
  
  void resize(size_type new_size) { resize(new_size, value_type()); }

erase

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
  // 清除 pos 所指的元素。  
  //判断pos距离头近还是距离尾近，距离那个位置近就移动那个位置的元素，保证移动元素个数最少  
  iterator erase(iterator pos) {  
    iterator next = pos;  
    ++next;  
    difference_type index = pos - start;    // pos和deque开头元素的个数  
    if (index < (size() >> 1)) {           // size() >> 1为size()/2  
    //如果pos距离deque头比较近的话，deque的开头到pos元素向后移  
      copy_backward(start, pos, next);    
      pop_front();              // 移动后，删除第一个元素  
    }  
    else {                  // 否则pos+1到结尾元素向前移，  
      copy(next, finish, pos);    
      pop_back();                 
    }  
    return start + index;  
  }  

//擦除两个迭代器之间的元素  
template <class T, class Alloc, size_t BufSize>  
deque<T, Alloc, BufSize>::iterator   
deque<T, Alloc, BufSize>::erase(iterator first, iterator last) {  
  if (first == start && last == finish) { // 如果是清除整个 deque  
    clear();                            // 直接调用 clear() 即可  
    return finish;  
  }  
  else {  
    difference_type n = last - first;           // 擦除区间长度  
    difference_type elems_before = first - start;   // 擦除区间前方元素的个数  
    if (elems_before < (size() - n) / 2) {       // 如果前方的元素少，  
      copy_backward(start, first, last);        // 前方元素向后移（覆盖擦除区间）  
      iterator new_start = start + n;           // deque 的新起点  
      destroy(start, new_start);                // 多于元素析构  
      // 释放多于元素所占内存  
      for (map_pointer cur = start.node; cur < new_start.node; ++cur)  
        data_allocator::deallocate(*cur, buffer_size());  
      start = new_start;      
    }  
    else {  // 后方元素更少  
      copy(last, finish, first);    //后方元素向前移动（覆盖擦除区间）     
      iterator new_finish = finish - n;   
      destroy(new_finish, finish);        
      // 释放多于元素所占内存
      for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur)  
        data_allocator::deallocate(*cur, buffer_size());  
      finish = new_finish;    
    }  
    return start + elems_before;  
  }  
}

clear

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//清空deque。最后保留了一个缓冲区，这是deque的策略，也是其初始状态  
template <class T, class Alloc, size_t BufSize>  
void deque<T, Alloc, BufSize>::clear() {  
  //头尾以外的缓冲区，它们肯定是满的。  
  for (map_pointer node = start.node + 1; node < finish.node; ++node) {  

    destroy(*node, *node + buffer_size());  
    data_allocator::deallocate(*node, buffer_size());  
  }  
  
  if (start.node != finish.node) {  // 至少有2个以上（含）缓冲区  
    destroy(start.cur, start.last); // 头缓冲区元素析构  
    destroy(finish.first, finish.cur); // 尾缓冲区元素析构  
    // 释放尾缓冲区，保留了头缓冲区  
    data_allocator::deallocate(finish.first, buffer_size());  
  }  
  else  // 只有一个缓冲区  
    destroy(start.cur, finish.cur); // 析构，但是不释放  
  
  finish = start;   // 调整迭代器，deque为空  
}