/** Class invariants:
 *  For any nonsingular iterator i:
 *    i.node is the address of an element in the map array.  The
 *      contents of i.node is a pointer to the beginning of a node.
 *    i.first == *(i.node)
 *    i.last  == i.first + node_size
 *    i.cur is a pointer in the range [i.first, i.last).  NOTE:
 *      the implication of this is that i.cur is always a dereferenceable
 *      pointer, even if i is a past-the-end iterator.
 *  Start and Finish are always nonsingular iterators.  NOTE: this means
 *    that an empty deque must have one node, and that a deque
 *    with N elements, where N is the buffer size, must have two nodes.
 *  For every node other than start.node and finish.node, every element
 *    in the node is an initialized object.  If start.node == finish.node,
 *    then [start.cur, finish.cur) are initialized objects, and
 *    the elements outside that range are uninitialized storage.  Otherwise,
 *    [start.cur, start.last) and [finish.first, finish.cur) are initialized
 *    objects, and [start.first, start.cur) and [finish.cur, finish.last)
 *    are uninitialized storage.
 *  [map, map + map_size) is a valid, non-empty range.
 *  [start.node, finish.node] is a valid range contained within
 *    [map, map + map_size).
 *  A pointer in the range [map, map + map_size) points to an allocated node
 *    if and only if the pointer is in the range [start.node, finish.node].
 */

/// Note: this function is simply a kludge to work around several compilers'
///  bugs in handling constant expressions.
inline size_t __deque_buf_size(size_t __size)
{
    return __size < 512 ? size_t(512 / __size) : size_t(1);   ///计算deque每个区段大小
}

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

    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;

    ///指向迭代器所在区段头指针在区段中控器(一个按序存储区段头指针
    ///的数组,也可以理解为区段位置的索引表)中的存储位置,存储顺序决定了
    ///各个区段的顺序,据此来控制迭代器跨区段移动
    _Map_pointer _M_node;
    _Tp* _M_cur;   ///指向迭代器实指位置

    _Tp* _M_first;    ///指向迭代器所在区段的头指针,由*_M_node可得
    ///指向超出迭代器所在区段的第一个指针,由_M_first与区段大小求和可得
    _Tp* _M_last;

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

    reference operator*() const
    {
        return *_M_cur;
    }
    pointer operator->() const
    {
        return _M_cur;
    }

    difference_type operator-(const _Self& __x) const
    {
        ///_M_node - __x._M_node-1计算x和本迭代器之间相隔的完整区段数
        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;
    }

    ///为使迭代器