C++模拟实现容器list(含迭代器)

谁借莪１个温暖的怀抱￠ 2022-06-05 00:15 264阅读 0赞

list同之前实现过的容器vector类似，都是STL众多容器中的一个。STL中实现的链表是带头结点的双向循环链表，这种链表相比于之前我们在C语言和C++初级阶段模板实现的链表或者双向链表更加的方便，更加方便的遍历，方便查找，方便各种操作。  
在vector中，我们是用一个原生态的指针来当做迭代器，但是在list中我们只能对指针进行封装来实现迭代器。  
![这里写图片描述][SouthEast]  
list的基本结构就如上图所示，接下来看看具体实现代码

#define _CRT_SECURE_NO_WARNINGS 1
    #pragma once
    #include <stdlib.h>
    #include <iostream>
    using namespace std;
    
    
    template<class T>
    struct ListNode
    {
        ListNode(const T& data = T())
        : _pPre(0)
        , _pNext(0)
        , _data(data)
        {}
    
        ListNode<T>* _pPre;
        ListNode<T>* _pNext;
        T _data;
    };
    //迭代器
    template<class T,class Ref,class Ptr>
    class ListIterator
    {
        typedef ListIterator<T, Ref, Ptr> Self;
    public:
        ListIterator()
            :_pCur(0)
        {}
    
        ListIterator(ListNode<T>* pCur)
            : _pCur(pCur)
        {}
    
        ListIterator(const Self& s)
            : _pCur(s._pCur)
        {}
    
        Ref operator*()
        {
            return _pCur->_data;
        }
    
        Ptr operator->()
        {
            return &(operator*());
            //return &(_pCur->_data); 
        }
    
        Self& operator++()
        {
            _pCur = _pCur->_pNext;
            return*this;
        }
    
        Self operator++(int)
        {
            Self temp(*this);
            _pCur = _pCur->_pNext;
            return temp;
        }
    
        Self& operator--()
        {
            _pCur = _pCur->_pPre;
            return*this;
        }
    
        Self operator--(int)
        {
            Self temp(*this);
            _pCur = _pCur->_pPre;
            return temp;
        }
    
        bool operator!=(const Self& s)
        {
            return _pCur != s._pCur;
        }
    
        bool operator==(const Self& s)
        {
            return _pCur == s._pCur;
        }
    
        ListNode<T>* _pCur;
    };
    
    template <class T>
    class List
    {
    public:
        typedef ListIterator<T, T&, T*> Iterator;
        typedef ListNode<T> Node;
    public:
        List()//无参构造函数
            : _pHead(new Node)
        {
            _pHead->_pNext = _pHead;//带头节点的循环链表
            _pHead->_pPre = _pHead;
        }
    
        List(const T* array, size_t size)//有参构造函数
            :_pHead(new Node)
        {
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
            for (size_t i = 0; i < size; i++)
            {
                PushBack(array[i]);
            }
        }
        List(const List<T>& l)//拷贝构造函数
            :_pHead(new Node)
        {
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
            Node* cur = l._pHead->_pNext;
            for (size_t i = 0; i < l.Size();i++)
            {
                PushBack(cur->_data);
                cur = cur->_pNext;
            }
    
        }
        List<T>& operator=(const List<T>& l)//赋值运算符重载
        {
            if (this != &l)
            {
                Node* pRet = l._pHead->_pNext;
                for (size_t i = 0; i < l.Size(); i++)
                {
                    PushBack(pRet->_data);
                    pRet = pRet->_pNext;
                }
            }
            return *this;
        }
        ~List()//析构函数
        {
            Clear();
            delete _pHead;
            _pHead = NULL;
        }
    
        Iterator Begin()
        {
            return Iterator(_pHead->_pNext);
        }
    
        Iterator End()
        {
            return Iterator(_pHead);
        }
        void PushBack(const T& data)//尾插
        {
            Node* _pNewNode = new Node(data);
            if (Empty())//链表为空
            {
                _pHead->_pNext = _pNewNode;
                _pHead->_pPre = _pNewNode;
                _pNewNode->_pNext = _pHead;
                _pNewNode->_pPre = _pHead;
            }
            else
            {
                Node* pTail = _pHead->_pPre;
                pTail->_pNext = _pNewNode;
                _pNewNode->_pNext = _pHead;
                _pNewNode->_pPre = pTail;
                _pHead->_pPre = _pNewNode;
            }
        }
        void PopBack()//尾删
        {
            if (Empty())//链表为空
            {
                return;
            }
            else
            {
                Node* del = _pHead->_pPre;//要删除的节点
                Node* tail = del->_pPre;//新的尾节点
                delete del;
                tail->_pNext = _pHead;
                _pHead->_pPre = tail;
            }
        }
        void PushFront(const T& data)//头插
        {
            Node* _pNewNode = new Node(data);
            _pHead->_pNext->_pPre = _pNewNode;
            _pNewNode->_pNext = _pHead->_pNext;
            _pNewNode->_pPre = _pHead;
            _pHead->_pNext = _pNewNode;
        }
        void PopFront()//头删
        {
            if (Empty())
            {
                return;
            }
            else
            {
                Node* pDel = _pHead->_pNext;
                _pHead->_pNext = pDel->_pNext;
                pDel->_pNext->_pPre = _pHead;
                delete pDel;
            }
        }
        Iterator Insert(Iterator pos, const T& data)//任意位置插入
        {
            Node* _pNewNode = new Node(data);
            pos._pCur->_pPre->_pNext = _pNewNode;
            _pNewNode->_pNext = pos._pCur;
            _pNewNode->_pPre = pos._pCur->_pPre;
            pos._pCur->_pPre = _pNewNode;
            return Iterator(_pNewNode);
        }
        Iterator Erase(Iterator pos)//任意位置删除
        {
            Node* pCur = pos._pCur->_pNext;
            pos._pCur->_pNext->_pPre = pos._pCur->_pPre;
            pos._pCur->_pPre->_pNext = pos._pCur->_pNext;
            delete pos._pCur;
            return Iterator(pCur);
        }
        Iterator Find(const T& d)//通过迭代器来查找
        {
            Iterator it = Begin();
            while (it != End())
            {
                if ((*it) == d)
                    return it;
                it++;
            }
            return End();
        }
        bool Empty()const//判断链表是否为空
        {
            return _pHead->_pNext == _pHead;
        }
        size_t Size()const//返回链表元素个数
        {
            Node* pCur = _pHead->_pNext;
            size_t count = 0;
            while (pCur != _pHead)
            {
                ++count;
                pCur = pCur->_pNext;
            }
            return count;
        }
        T& Front()//返回第一个节点
        {
            return _pHead->_pNext->_data;
        }
        const T& Front()const
        {
            return _pHead->_pNext->_data;
        }
        T& Back()//返回尾节点
        {
            return _pHead->_pPre->_data;
        }
        const T& Back()const
        {
            return _pHead->_pPre->_data;
        }
        void Clear()//清空链表
        {
            Iterator it = Begin();
            while (it != End())
            {
                it = Erase(it);
            }
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }
    private:
        ListNode<T>* _pHead;
    };
    void PrintList( List<int>& l)//打印链表
    {
        List<int>::Iterator It = l.Begin();
        while (It != l.End())
        {
            cout << *It << " ";
            ++It;
        }
        cout << endl;
    }

测试代码：

void FunTest1()
    {
        //无参构造函数
        List<int> l1;
    
        //有参构造函数
        int arr[5] = { 1, 2, 3, 4, 5 };
        List<int> l2(arr, 5);
        PrintList(l2);
    
        //拷贝构造函数
        List<int> l3(l2);
    
        //赋值运算符重载
        l1 = l2;
    }
    void FunTest2()
    {
        List<int> l1;
        l1.PushBack(1);
        l1.PushBack(2);
        l1.PushBack(3);
        l1.PushBack(4);
        l1.PushBack(5);
        l1.PushBack(6);
        l1.PushFront(7);
        PrintList(l1);
        cout << l1.Size() << endl;
    
        l1.PopBack();
        l1.PopBack();
        l1.PopBack();
        l1.PopFront();
        l1.PopFront();
        PrintList(l1);
        cout << l1.Size() << endl;
    }
    void FunTest3()
    {
        List<int> l1;
        l1.PushBack(1);
        l1.PushBack(2);
        l1.PushBack(3);
        l1.PushBack(4);
        l1.PushBack(5);
        List<int>::Iterator pos = l1.Find(3);
        l1.Insert(pos, 0);
        PrintList(l1);
    
        l1.Erase(pos);
        PrintList(l1);
    
    }

运行结果：  
![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]  
![这里写图片描述][SouthEast 3]

[SouthEast]: /images/20220605/06d701d50b134a8394f4b60c4e6d16e1.png
[SouthEast 1]: /images/20220605/fe35ac93a6ba4a9b9db14cfcf40177e4.png
[SouthEast 2]: /images/20220605/a430cef207f9409a97becac037f76e89.png
[SouthEast 3]: /images/20220605/71222f59808d46c6a14a6fe73c404548.png