/*

deque是一种双向开口的连续线性空间,可以在头尾两端分别做元素的插入和删除操作

常用接口：back(), front(), push_back(), pop_back(), push_front(), pop_front()

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=>

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 - ) + (cur - first) + (x.last - x.cur);

    }

    //前置

    self& operator++()

    {

        ++cur;

        if (cur == last)

        {

            set_node(node + );

            cur = first;

        }

        return *this;

    }

    //后置

    self operator++(int)

    {

        self tmp = *this;

        ++*this;//调用上面的++

        return tmp;

    }

    self& operator--()

    {

        if (cur == first)

        {

            set_node(node - );

            cur = last;

        }

        --cur;

        return *this;

    }

    self operator--(int)

    {

        self tmp = *this;

        --*this;

        return tmp;

    }

};