deque的一种简单实现

STL库中的deque是一种非常有用的数据结构。嗯。。。好吧，我也不经常用这个数据结构！！！

deque的实现需要考虑的两个问题：

• 如何实现随机存取
• 如何实现在两端实现push和pop

如果想实现随机存取，我们必须有计算公式，能够直接根据指定的值算出element所在的位置。
想实现两端push和pop我们必须能够有一种类似链表的结构支持这样的做法。

为了达到上面的目的，我使用的结构是：

map<int, vector<T*>> dq;

map是一种映射表，如果我采用连续的整数做关键字，那么就可以实现两端push和pop，如果我固定vector的大小，那么我就可以使用固定公式计算element的位置。当然，你也可以使用其他的数据结构，这只是我的一种简单实现罢了！！！

在写代码的过程中，我发现我大部分的时间都是在构造计算公式，对于vector的实现而言，deque的计算公式要稍微复杂一点（其实也没有了，就是初中的加减乘除，不过对于我来说，实现的时候还是费脑子的）

代码如下：

template<typename T>
class MyDeque
{
public:
    MyDeque()
    {
        base = 0;
        curbase = 0;
        tail = 0;
        curtail = 0;
    }
    ~MyDeque()
    {
        for (auto itr = dq.begin(); itr != dq.end(); ++itr)
        {
            for (auto itr2 = itr->second.begin(); itr2 != itr->second.end(); ++itr2)
            {
                delete *itr2;
                *itr2 = nullptr;
            }
        }

        dq.clear();
    }

    void push_back(const T & ele)
    {
        while (true)
        {
            if (dq.find(tail) == dq.end())
            {
                dq[tail] = vector<T*>(l, nullptr);
                curtail = 0;
            }

            if (curtail >= l)
            {
                tail += 1;
                curtail = 0;
                continue;
            }

            dq[tail][curtail] = new T(ele);
            curtail += 1;

            break;
        }
    }

    void pop_back()
    {
        if (base == tail && curbase == curtail)
        {
            return;
        }

        delete dq[tail][curtail - 1];
        dq[tail][curtail - 1] = nullptr;
        curtail -= 1;

        if (curtail <= 0)
        {
            tail -= 1;
            curtail = l;
        }
    }

    void push_front(const T & ele)
    {
        while (true)
        {
            if (dq.find(base) == dq.end())
            {
                dq[base] = vector<T*>(l, nullptr);
                curbase = l;
            }


            if (curbase <= 0)
            {
                base -= 1;
                curbase = l;
                continue;
            }

            dq[base][curbase - 1] = new T(ele);
            curbase -= 1;

            break;
        }
    }

    void pop_front()
    {
        if (base == tail && curbase == curtail)
        {
            return;
        }

        delete dq[base][curbase];
        dq[base][curbase] = nullptr;
        curbase += 1;

        if (curbase == l)
        {
            base += 1;
            curbase = 0;
        }
    }

    T & operator[](int pos)
    {   
        assert(pos >= 0 && pos < size());

        return pos < (l - curbase) ? *(dq[base][curbase + pos]) :
            *(dq[base + (pos - (l - curbase)) / l + 1][(pos - (l - curbase)) % l]);
    }

    int size()
    {
        return (l - curbase) + curtail + (tail - base + 1 - 2) * l;
    }

private:
    int base;
    int curbase;
    int tail;
    int curtail;
    static const int l = 50000;

    map<int, vector<T*>> dq;
};