/*deque是一种双向开口的连续线性空间,可以在头尾两端分别做元素的插入和删除操作deque与vector差异：1.deque允许于常数时间内对头部进行元素的插入和移除操作2.deque没有容量(capacity)概念，由分段连续空间组合而成，随时可以增加一段新的空间并链接起来，而vector当空间不足时，需要重新配置一块更大空间，然后复制元素，再释放旧空间注意：deque的迭代器不是普通指针，操作复杂度比vector迭代器要大，所以应尽可能选择使用vector对deque进行的排序操作，为了最高效率，可将deque复制到vector，将vector排序后，再复制回deque*//*deque采用一小块连续空间，其中每个元素都是指针，指向另一段较大的连续线性空间，称为缓冲区，缓冲区是deque的储存空间主体，SGI STL允许我们指定缓冲区大小，默认值0表示将使用512bytes缓冲区*/template <class T,class Alloc=alloc,size_t BufSiz=0>class deque{public:    typedef T value_type;    typedef value_type* pointer;    typedef _deque_iterator<T, T&, T*, BufSiz> iterator;    //...protected:    typedef pointer* map_pointer;    typedef size_t size_type;    map_pointer map;//指向map，map是块连续空间，其内的每个元素都是一个指针，指向一块缓冲区    size_type map_size;//map内可容纳指针数    iterator start;//指向第一个缓冲区的第一个元素    iterator finish;//指向最后缓冲区的最后一个元素的下一位置    };//迭代器实现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;    //未继承iterator    typedef random_access_iterator_tag iterator_category;    typedef T value_type;    typedef Ptr pointer;    typedef Ref reference;    typedef size_t size_type;    typedef ptrdiff_t difference_type;    typedef T** map_pointer;    typedef _deque_iterator self;        //每个迭代器指向一个缓冲区    T* cur;//该迭代器所指的缓冲区中的当前元素    T* first;//该迭代器所指的缓冲区的头    T* last;//该迭代器所指的缓冲区的尾    map_pointer node;//指向map空间中指向对应缓冲区的结点    //返回缓冲区中元素个数    static size_t buffer_size();    //当迭代器行进时遇到缓冲区边缘，需要调用set_node()跳一个缓冲区    void set_node(map_pointer new_node)    {        //new_node指向新缓冲区        node = new_node;        first = *new_node;        last = first + difference_type(buffer_size());    }    reference operator*()const    {        return *cur;    }    pointer operator->()const    {        return &(operator*());    }    difference_type operator-(const self &x)const    {        return difference_type(buffer_size())*(node - x.node - 1) + (cur - first) + (x.last - x.cur);    }    //前置    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;    }};