STL之Deque

Posted on | Edited on

deque是双向开口的，可以在头部插入/删除，也可以在尾部插入/删除，而且都是常数时间的复杂度

而这得益于deque的其结构，deque是由多段线型空间组合而成，可以随时增加一段新的空间并连接起来

因此可以把deque看作是一个链表，而每一个链表节点则是一个数组

虽然deque也提供Random Access Iterator，但是这并不是普通的指针，可以的话尽量使用vector

deque的中控器

deque由于结构并不是真正的线形空间，为了维护其整体连续的假象，并提供随机存取的接口，因此需要使用一块map作为中控器

其中map的每一个元素指向一个节点(一块连续的空间)，我们称这块空间为缓冲区

1
2
3
4
5
6
7
8
9
10
11
template <class _Tp, class _Alloc>
class _Deque_base {
protected:
  _Tp** _M_map; //中控器
  size_t _M_map_size;  //中控器的容量
  iterator _M_start; //缓冲区的头
  iterator _M_finish;//缓冲区的尾
  
  iterator begin() { return _M_start; }
  iterator end() { return _M_finish; }
}

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
template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator {
  _Tp* _M_cur; //指向当前元素
  _Tp* _M_first;//当前缓冲区的头
  _Tp* _M_last;//当前缓冲区的尾
  _Map_pointer _M_node;

  _Self& operator++() {
    ++_M_cur;
    if (_M_cur == _M_last) {
      _M_set_node(_M_node + 1);
      _M_cur = _M_first;
    }
    return *this; 
  }
  
  _Self& operator--() {
    if (_M_cur == _M_first) {
      _M_set_node(_M_node - 1);
      _M_cur = _M_last;
    }
    --_M_cur;
    return *this;
  }
  
};

迭代器所进行++和—的操作，需要进行边界判断，判断是否能到达下一个/上一个缓冲区

这个行为依赖于_M_set_node

1
2
3
4
5
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());
  }

deque的内存管理

deque的结构，使其需要管理map以及缓冲区

当新建缓冲区的时候，不仅需要构建一块缓冲区，还要往map中构造一个指针，而这些操作由以下函数完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14

_Tp* _M_allocate_node() {
    return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
  }
  
void _M_deallocate_node(_Tp* __p) {
    _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
  }
 
_Tp** _M_allocate_map(size_t __n) 
    { return _M_map_allocator.allocate(__n); }
  
void _M_deallocate_map(_Tp** __p, size_t __n) 
    { _M_map_allocator.deallocate(__p, __n); }

安排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
template <class _Tp, class _Alloc>
void
_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
{
  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);
  _M_map = _M_allocate_map(_M_map_size);

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

按照初始化的顺序，首先是通过_M_allocate_map()来初始化map，随后在通过_M_create_nodes()来初始化缓冲区，最后再设置start,finish等变量的值

初始化map

1
2
3
4
5
  _Tp** _M_allocate_map(size_t __n) 
    { return _Map_alloc_type::allocate(__n); }

static _Tp* allocate(size_t __n)
      { return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }

从源码可以看出，只是单纯地分配一大块内存而已,其大小为

1
2
3
4
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管理的是缓冲区，然后每个缓冲区都可以存放一定的nodes，因此大小为node总数/每个缓冲区的大小+1

初始化缓冲区

1
2
3
4
5
6
_Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
  _Tp** __nfinish = __nstart + __num_nodes;
    
  __STL_TRY {
    _M_create_nodes(__nstart, __nfinish);
  }

让nstart和nfinish指向map的中间部分，因为deque是双向开口的，因此要保证向前和向后扩充的容量是一样的，每个节点对应一个缓冲区

元素操作

push_front

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
void push_front(const value_type& __t) {
    if (_M_start._M_cur != _M_start._M_first) {
      construct(_M_start._M_cur - 1, __t);
      --_M_start._M_cur;
    }
    else  //当前缓冲区已无空间
      _M_push_front_aux(__t); 
  }

template <class _Tp, class _Alloc>
void  deque<_Tp,_Alloc>::_M_push_front_aux(const value_type& __t)
{
  value_type __t_copy = __t;
  _M_reserve_map_at_front(); //测试是否需要更换一个map
   //新建缓冲区
  *(_M_start._M_node - 1) = _M_allocate_node();
  __STL_TRY {
    _M_start._M_set_node(_M_start._M_node - 1);
    _M_start._M_cur = _M_start._M_last - 1;
    construct(_M_start._M_cur, __t_copy);
  }
  __STL_UNWIND((++_M_start, _M_deallocate_node(*(_M_start._M_node - 1))));
} 

 void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
    if (__nodes_to_add > size_type(_M_start._M_node - _M_map)) //重新分配map的条件
      _M_reallocate_map(__nodes_to_add, true);
  }

pop_front

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  void pop_front() {
    if (_M_start._M_cur != _M_start._M_last - 1) {
      destroy(_M_start._M_cur);
      ++_M_start._M_cur;
    }
    else //最后缓冲区没有任何元素 
      _M_pop_front_aux();
  }

void deque<_Tp,_Alloc>::_M_pop_front_aux()
{
    //释放缓冲区
  destroy(_M_start._M_cur);
  _M_deallocate_node(_M_start._M_first);
   //调整start，指向下一个缓冲区的第一个元素
  _M_start._M_set_node(_M_start._M_node + 1);
  _M_start._M_cur = _M_start._M_first;
}

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
iterator insert(iterator position, const value_type& __x) {
    //根据插入位置的不同进行不同的操作
    if (position._M_cur == _M_start._M_cur) { //在缓冲区头部插入
      push_front(__x);
      return _M_start;
    }
    else if (position._M_cur == _M_finish._M_cur) { //在缓冲区尾部插入
      push_back(__x);
      iterator __tmp = _M_finish;
      --__tmp;
      return __tmp;
    }
    else {
      return _M_insert_aux(position, __x);
    }
  }

deque<_Tp,_Alloc>::_M_insert_aux(iterator __pos, const value_type& __x)
{
  difference_type __index = __pos - _M_start;
  value_type __x_copy = __x;
  if (size_type(__index) < this->size() / 2) {
    push_front(front());
    iterator __front1 = _M_start;
    ++__front1;
    iterator __front2 = __front1;
    ++__front2;
    __pos = _M_start + __index;
    iterator __pos1 = __pos;
    ++__pos1;
    copy(__front2, __pos1, __front1);
  }
  else {
    push_back(back());
    iterator __back1 = _M_finish;
    --__back1;
    iterator __back2 = __back1;
    --__back2;
    __pos = _M_start + __index;
    copy_backward(__pos, __back2, __back1);
  }
  *__pos = __x_copy;
  return __pos;
}