自定义 C++ deque

deque

双向队列，提供可以头部和尾部进行添加和删除元素的功能。最好的实现方案，就是指针数组，这样可以使用 下标进行元素访问以及添加删除元素。也可以理解list和vector的结合体。

#ifndef TDEQUE_H
#define TDEQUE_H
#include <stdlib.h>
#include <string.h>
#include <ASSERT.H>

using namespace std;

template <class T>

class TDeque
{
public:
    class iterator
    {
    public:
        T** i;

        inline iterator(): i(nullptr) {}
        inline iterator(T** n)
        {
            i = n;
        }
        inline iterator(const iterator &o): i(o.i){}

        inline T &operator*() const { return **i; }
        inline T *operator->() const { return *i; }
        inline bool operator==(const iterator &o) const  { return (int)i == (int)o.i; }
        inline bool operator!=(const iterator &o) const  { return (int)i != (int)o.i; }
        inline iterator operator+(int j) const { return i+j; }
        inline iterator operator-(int j) const { return i-j; }
        inline int operator-(iterator j) const { return i - j.i; }
        //++i
        inline iterator &operator++() { ++i; return *this; }
        //i++
        inline iterator operator++(int) {
            //node *n = i; ++i; return n;
                                          iterator tmp = *this;++(*this);return tmp;}
        //--i
        inline iterator &operator--() { --i; return *this;  }
        //i--
        inline iterator operator--(int) { iterator tmp = *this;--(*this);return tmp; }
    };
    TDeque()
    {
        nCapacity = 16;
        pData = new T*[nCapacity+1];
        nSize = 0;
    }
    T at(int index)
    {
        assert(index < nSize);
        return *pData[index];
    }
    T back()
    {
        return *pData[nSize-1];
    }
    iterator begin()
    {
        return iterator(&pData[0]);
    }
    iterator end()
    {
        return iterator(&pData[nSize]);

    }

    void clear()
    {
        for(int i = 0;i < nSize;i++)
        {
            T* temp = pData[i];
            delete temp;
            temp = NULL;
        }
        delete []pData;
        nCapacity = 16;

        pData = new T*[nCapacity+1];
        nSize = 0;

    }
    bool empty()
    {
        return nSize == 0;
    }

    T& front()
    {
        return *pData[0];
    }
    unsigned int max_size()
    {
        return nCapacity;
    }
    void pop_back()
    {
        T* temp = NULL;
        temp = pData[nSize - 1];
        if(temp)
        {
            delete temp;
        }
        pData[nSize - 1] = NULL;
        nSize--;
    }
    void pop_front()
    {
        T* temp = NULL;
        temp = pData[0];
        if(temp)
        {
            delete temp;
            memmove(pData,pData+1,(nSize - 1)*4);
            nSize--;

        }

    }
    void push_back(const T& value)
    {
        realloc();
        T* temp = new T(value);
        pData[nSize] = temp;
        nSize++;

    }
    void push_front(const T& value)
    {
        realloc();
        T* temp = new T(value);
        memmove(pData+1,pData,nSize*4);
        pData[0] = temp;
        nSize++;
    }
    unsigned int size()
    {
        return nSize;
    }
    void realloc()
    {
        if(nSize == nCapacity)
        {
            nCapacity = nCapacity * 2;
            T** pNewData = new T*[nCapacity+1];
            for(int i = 0; i < (nCapacity+1);i++)
            {
               pNewData[i] = pData[i];

            }
            delete []pData;
            pData = pNewData;
        }
    }

private:
    T** pData;
    unsigned int nCapacity;
    unsigned int nSize;


};

#endif // DEQUE_H

最后

以上就是美丽乌冬面为你收集整理的自定义 C++ deque的全部内容，希望文章能够帮你解决自定义 C++ deque所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。