模拟實作STL中的List容器

List.h

#include <iostream>
#include <assert.h>
using namespace std;

//結點結構
template<class T>
struct ListNode
{

    ListNode(const T&data = T())
        :_prev()
        ,_next()
        ,_data(data)
    {}

    ListNode<T>*_prev;
    ListNode<T>*_next;
    T _data;
};

//構造疊代器
template<class T,class Ref,class Ptr>
class _Listlterator_
{
    typedef _Listlterator_<T,T&,T*> lterator;
    typedef _Listlterator_<T,const T&,const T*> Constlterator;
    typedef ListNode<T>* _LinkType;
    typedef _Listlterator_<T,Ref,Ptr> Self;
    typedef Ref Reference;
    typedef Ptr Pointer;

public:
    _Listlterator_(_LinkType x = )
        :_node(x)
    {}
    _Listlterator_(const lterator& x)
        :_node(x->_node)
    {}
    bool operator==(const lterator&x)
    {
        return _node==(x._node);
    }
    bool operator!=(const lterator&x)
    {
        return _node!=(x._node);
    }
    Reference operator*()
    {
        return _node->_data;
    }
    Pointer operator->()
    {
        return &_node->_data;
    }
    Self& operator++()
    {
        _node = _node->_next;
        return *this;
    }
    Self operator++(int)
    {
        Self tem(*this);
        _node = _node->_next;
        return tem;
    }
    Self&operator--()
    {
        _node = _node->_prev;
        return *this;
    }
    Self operator--(int)
    {
        Self tem(*this);
        _node = _node->_prev;
        return tem;
    }

public:
    _LinkType _node;
};



//實作List的功能
template<class T>
class List
{
public:
    typedef ListNode<T> Node;
    typedef T ValueType;
    typedef ValueType& Reference;
    typedef const ValueType& ConstReference;
    typedef ValueType* Pointer;
    typedef const ValueType*  ConstPointer;
    typedef Node* LinkType;
    typedef size_t SizeType;
    typedef _Listlterator_<T,T&,T*> lterator;
    typedef _Listlterator_<T,const T&,const T*>Constlterator;

public:
    List()
    {
        _phead =  new Node ;
        _phead->_data = T();
        _phead->_next = _phead;
        _phead->_prev = _phead;
    }
    List(SizeType n,const T&data)
        :_phead( new Node)
    {
        _phead ->_data = T();
        _phead->_next =_phead ;
        _phead->_prev = _phead;
        LinkType _temp = _phead;
        while (n)
        {
            LinkType tem =  new Node;
            tem->_data = data;
            if (tem!=NULL)
            {
                _temp ->_next= tem;
                tem ->_prev = _temp;
                tem ->_next = _phead;
                _phead->_prev = tem;
                _temp = tem;
                --n;
            }
        }
    }

    List(const List<T>&l)//拷貝構造函數 ：要注意淺拷貝的問題
    {
        _phead = new Node();
        _phead->_data = T();
        _phead->_prev = _phead;
        _phead->_next = _phead;
        LinkType tem = l._phead->_next;
        LinkType pre = _phead;
        while (tem != l._phead)
        {
            LinkType temp = new Node ;
            temp->_data = tem->_data;
            pre->_next = temp;
            temp ->_prev = pre;
            temp ->_next = _phead;
            _phead->_prev = temp;
            pre = temp;
            tem = tem->_next;
        }
    }
    ~List()
    {
        Destroy();
        delete _phead;
        _phead = NULL;
    }
    void Destroy()
    {
        LinkType ptem = _phead->_next;
        while (ptem!=_phead)
        {
            LinkType tem = ptem->_next;
            delete ptem;
            ptem = tem;
        }
        _phead->_next = _phead;
        _phead->_prev = _phead;
    }

    List<T>& operator=(constList<T>&l)//重載指派運算符
    {
        _phead = new Node();
        _phead->_data = T();
        _phead->_prev = _phead;
        _phead->_next = _phead;
        LinkType tem = l._phead->_next;
        LinkType pre = _phead;
        while (tem)
        {
            LinkType temp = new Node ;
            temp ->_data = tem->_data;
            pre->_next = temp;
            temp ->_prev = pre;
            temp ->_next = _phead;
            _phead->_prev = temp;
            pre = temp;
            tem = tem->_next;
        }
        return *this;
    }

    //
    lterator Begin()
    {
        return _phead->_next;
    }
    Constlterator Begin()const
    {
        return _phead->_next;
    }
    lterator End()
    {
        return _phead;
    }
    bool Empty()const
    {
        return _phead->_next==_phead;
    }
    SizeType Size()const
    {
        SizeType n = ;
        LinkType temp = _phead;
        while (temp->_next!=_phead)
        {
            ++n;
            temp = temp->_next;
        }
        return n;
    }
    SizeType MaxSize()const
    {}
    Reference Front()
    {
        return _phead->_next->_data;
    }
    Reference Back()
    {
        return _phead->_prev->_data;
    }
    ConstReference Back()const
    {
        return *_phead->_prev;
    }
    lterator Insert(lterator pos,const T& x=T())
    {
        if(pos==NULL)
        {
            return NULL;
        }
        LinkType temp = new Node ;
        temp->_data = x;
        LinkType prve = pos._node->_prev;
        prve->_next = temp;
        temp->_prev = prve;
        temp->_next = pos._node;
        pos._node->_prev = temp;
        return _phead;
    }
    void PushFront(const T&x)
    {
        Insert(Begin(),x);
    }
    void PushBack(const T&x)
    {
        Insert(End(),x);
    }
    lterator Erase(lterator pos)
    {
        if (pos==NULL)
        {
            return NULL;
        }
        if (pos == _phead)
        {
            pos = _phead->_prev;
        }
        LinkType prve = pos._node->_prev;
        prve->_next = pos._node->_next;
        prve->_next->_prev = prve;
        delete pos._node;//要釋放不用的指針
        return _phead;
    }
    void PopFront()
    {
        Erase(Begin());
    }
    void PopBack()
    {
        Erase(End());
    }
    void Resize(SizeType sz,T c = T())//置數函數
    {                                 
        if (sz<=Size())
        {
            return;
        }
        else
        {
            SizeType n = sz -Size();
            for (SizeType i = ;i<n;i++)
            {
                PushBack(c);
            }
        }
    }
    void Assign(SizeType n,const T&data)
    {
        Destroy();
        while (n--)
        {
            PushBack(data);
        }

}

void Clear()
    {
        Destroy();
    }
private:
    void EmptyInit()
    {}
protected:
    LinkType _phead;
};
void PrintfList(List<int> l)//利用疊代器列印list的内容
{
    List<int>::lterator it1 = l.Begin();
    while (it1 != l.End())
    {
        cout<<it1._node->_data<<" ";
        ++it1;
    }
    cout<<endl;
}
           

test.c

///////////////////////////////////////////////////////////////////////
#include "ListAqueue.h"

int main()
{
    List<int>l1;
    List<int>l2(,);
    cout<<"l2:";
    PrintfList(l2);
    List<int>l3(l2);
    cout<<"l3:";
    PrintfList(l3);
    List<int>l4 = l2;
    cout<<"l4:";
    PrintfList(l4);
    l2.Insert(l2.Begin(),);
    cout<<"l2:";
    PrintfList(l2);
    l3.Insert(l3.End(),);
    cout<<"l3:";
    PrintfList(l3);
    l2.Erase(l2.Begin());
    cout<<"l2:";
    PrintfList(l2);
    l3.Erase(l3.End());
    cout<<"l3:";
    PrintfList(l3);
    l1.PushBack();
    l1.PushFront();
    l1.PopBack();
    l1.Resize(,);
    cout<<"l1:";
    PrintfList(l1);
    l1.Resize(,);
    cout<<"l1:";
    PrintfList(l1);
    l2.Assign(,);
    cout<<"l2:";
    PrintfList(l2);
    l1.Clear();
    cout<<"l1:";
    PrintfList(l1);
    return ;
}
           

運作結果