2017-12-05 12:46:54 / herohlc

---

deque深度探索

1. deque数据结构

Image Copied on 2017-12-10 at 16.48.33 下午.png

体会外部的设计思路。deque对外特性连续，内部分段连续。

2. deque缓冲区

deque如何实现前后扩充？
缓冲区帮助deque实现前后扩充

deque缓冲区设计

1. 分段缓冲区存储

deque实际存入的元素放在缓冲区中，deque中会创建多个缓冲区供插入数据。

2. 缓冲区管理

多个缓冲区元素在一个map形式数据中（vector实现）中管理，缓冲区元素分布在map的中间位置，向两侧扩充。当map充满后自动扩充（vector扩充）。

3. deque迭代器设计

deque如何实现连续访问？
deque iterator帮助deque实现连续访问

iterator的四个变量

Image Copied on 2017-12-10 at 16.50.30 下午.png

1. cur: 迭代器在一个deque中当前指向的元素
2. first: 迭代器当前指向的缓冲区中，缓冲区范围中的第一个元素的位置
3. last: 迭代器当前指向的缓冲区中，缓冲区范围中的最后一个元素的下一个元素位置
4. node: 指向map区
   注意： iterator四个变量的变化规律
5. iterator在一个缓冲区中移动时，cur在变化，其他不变
6. iterator切换缓冲区移动时，所有变量都在变。

iterator移动行为

1. iterator在缓冲区存储元素的范围内移动。
2. iterator如果移动到缓冲区的边界（first/last），则通过node返回map，找到下一个缓冲区。

4. deque 对象存储的两个迭代器 begin/end

所有的容器都会存储两个迭代器，begin/end

template <class T, class Alloc = alloc, size_t Buffsiz = 0>
class deque {
    ...
protected:
    iterator start;
    iterator finish;
    ...
}

5. 源码

deque

// g++ 2.95.1 stl_deque.h
template <class _Tp, class _Alloc, size_t __bufsiz>
class _Deque_base {
public:
#ifndef __STL_NON_TYPE_TMPL_PARAM_BUG
  typedef _Deque_iterator<_Tp,_Tp&,_Tp*,__bufsiz>              iterator;
  typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*, __bufsiz> const_iterator;
#else /* __STL_NON_TYPE_TMPL_PARAM_BUG */
  typedef _Deque_iterator<_Tp,_Tp&,_Tp*>                      iterator;
  typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*>          const_iterator;
#endif /* __STL_NON_TYPE_TMPL_PARAM_BUG */

  typedef _Alloc allocator_type;
  allocator_type get_allocator() const { return allocator_type(); }

  _Deque_base(const allocator_type&, size_t __num_elements)
    : _M_map(0), _M_map_size(0),  _M_start(), _M_finish() {
    _M_initialize_map(__num_elements);
  }
  _Deque_base(const allocator_type&)
    : _M_map(0), _M_map_size(0),  _M_start(), _M_finish() {}
  ~_Deque_base();    

protected:
  void _M_initialize_map(size_t);
  void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
  void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
  enum { _S_initial_map_size = 8 };

protected:
  _Tp** _M_map;
  size_t _M_map_size;  
  iterator _M_start;
  iterator _M_finish;

  typedef simple_alloc<_Tp, _Alloc>  _Node_alloc_type;
  typedef simple_alloc<_Tp*, _Alloc> _Map_alloc_type;

  _Tp* _M_allocate_node()
    { return _Node_alloc_type::allocate(__deque_buf_size(__bufsiz, 
                                                         sizeof(_Tp))); }
  void _M_deallocate_node(_Tp* __p)
    { _Node_alloc_type::deallocate(__p, __deque_buf_size(__bufsiz, 
                                                         sizeof(_Tp))); }
  _Tp** _M_allocate_map(size_t __n) 
    { return _Map_alloc_type::allocate(__n); }
  void _M_deallocate_map(_Tp** __p, size_t __n) 
    { _Map_alloc_type::deallocate(__p, __n); }
};

iterator

// g++ 2.95.1 stl_deque.h
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(0, sizeof(_Tp)); }

  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;

  _Tp* _M_cur;
  _Tp* _M_first;
  _Tp* _M_last;
  _Map_pointer _M_node;
...
  }

注意其中的 associate types

6. buffer size

指定缓冲区大小.
注意：
这里的大小是指缓冲区数组的个数，而不是缓冲区实际内存大小。

template<class T, class Alloc = alloc, size_t Buffsiz=0>
class deque{
...
}

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));
}  // sz 为sizeof(value_type)

其中 template中size_t 的用法是新的知识点

template <class T, class Alloc = alloc, size_t Buffersiz = 0>
class deque{
    ...
}

1. 新版本不再支持用户指定缓冲区大小

7. deque<T>::insert()

iterator insert(iterator position, const value_type x) {
    if(position.cur == start.cur) {
        push_front(x);
        return start;
    } else if(position.cur == finish.cur) {
        push_back(x);
        iterator tmp = finish;
        --tmp;
        return tmp;
    } else {
        return insert_aux(position, x);
    }
}

// g++ 2.95.1 stl_deque.h
template <class _Tp, class _Alloc, size_t __bufsize>
typename deque<_Tp, _Alloc, __bufsize>::iterator
deque<_Tp,_Alloc,__bufsize>::_M_insert_aux(iterator __pos,
                                           const value_type& __x)
{
  difference_type __index = __pos - _M_start;
  value_type __x_copy = __x;
  if (__index < 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;
}

注意：

1. Insert 插入元素到已有元素位置时，已有元素需要向一侧推动。
2. Insert在推动元素时，需要考虑向头一侧推动还是向尾一侧推动，谁的效率更高。
3. 推动元素会造成已有元素的析构和新元素的构造。

理解：

1. 对于deque，insert操作会造成元素的推动，推动的过程会有元素的copy/构造等操作，造成效率问题，但在头尾的push不会有元素的推动，相对来说效率会高。

---

queue&stack深度探索

未完待续

---

RB-tree深度探索

未完待续

---

set/multiset深度探索

未完待续

---

map/multimap深度探索

未完待续

---

hash table深度探索

未完待续

---

hash_set/has_multiset, hash_map/hash_multimap概念

未完待续

---

unordered容器概念

未完待续

---