迭代器模拟实现STL中的list

以你之姓@ 2022-06-17 09:13 242阅读 0赞

list中的迭代器类似与智能指针的作用，它是将指向链表指向结点的指针管理起来。  
在STL中的list是带头结点的双向循环链表，这样的设计很巧妙，可以让我们的插入和删除元素的时候减少一些需要考虑的边界问题。

要模拟实现STL中的list我们首先得模拟实现迭代器，设计成用来管理指向list中结点的指针。因此要先给出迭代器这个类。所以在使用标准库中的迭代器的时候实际上是定义了一个迭代器对象，在这个对象的成员变量是指向结点的指针。

**1、下面先来模拟实现list中的迭代器**  
首先需要了解迭代器它是可以遍历容器中的元素的，也就是如果我们有一个链表，迭代器是可以访问这个链表中所有的节点的。

因此我们可以直接通过对迭代器的++或者–操作来遍历整个链表。如果对迭代器解引用我们可以直接访问到指向结点的指针的成员变量data。也就是结点这个结构体中的成员变量data.如果迭代器使用！=操作是代表可以判断当前指向结点的指针是否等于另一个指向结点的指针。

因此在模拟实现list的迭代器的时候我们需要将这些操作符进行重载。另外我们在设计的时候由于有const类型和非const类型的，而标准库中设计这个迭代器类的时候是非常巧妙地给出模板参数列表，因此我们可以仿照这种方式以此来提高代码的高效和复用率。

template<class T,class Ref,class Ptr>
    class _ListIterator
    {
    public:
        typedef _ListNode<T>  Node;
        typedef _ListIterator<T,  Ref,  Ptr> Self;
        _ListIterator(Node *node)
          :_node(node)
        {
    
        }
        Self& operator++()//前置++
        {
            _node = _node->pNext;
            return Self(_node);
        }
        Self operator++(int)//后置++效率低
        {  
            Node* Temp = _node;
            _node = _node->pNext;
            return Self(_node);
        }
        T& operator*()
        {
            return _node->_data;
        }//直接通过对迭代器解引用操作就可以直接访问结点中data的数据成员
        Ptr operator->()
        {
            return &(*(*this));
        }//直接可以通过对it->就可以访问结点中的成员
        Self& operator--()//前置--
        {
            _node = _node->pPre;
            return Self(_node);
        }
        Self operator--(int)
        {
            Node* Temp = _node;
            _node = _node->pPre;
            return Self(Temp);
        }
        bool operator!=(const _ListIterator&l)
        {
            return _node != l._node;
        }
        Node*_node;
    };//由于要去管理指向结点的指针，因此它的成员变量必然是指向结点的指针

给出了迭代器就可以通过迭代器来模拟实现STL中的list了

#include<iostream>
    #include<stdlib.h>
    #include<assert.h>
    using namespace std;
    template<class T>
    struct _ListNode
    {
        _ListNode(const T&data)
        :pPre(NULL)
        , pNext(NULL)
        , _data(data)
        {
    
        }
        _ListNode* pNext;
        _ListNode* pPre;
        T _data;
    };//首先给出结点的结构体
    template<class T,class Ref,class Ptr>
    class _ListIterator
    {
    public:
        typedef _ListNode<T>  Node;
        typedef _ListIterator<T,  Ref,  Ptr> Self;
        _ListIterator(Node *node)
          :_node(node)
        {
    
        }
        Self& operator++()//前置++
        {
            _node = _node->pNext;
            return Self(_node);
        }
        Self operator++(int)//后置++效率低
        {  
            Node* Temp = _node;
            _node = _node->pNext;
            return Self(_node);
        }
        T& operator*()
        {
            return _node->_data;
        }//直接通过对迭代器解引用操作就可以直接访问结点中data的数据成员
        Ptr operator->()
        {
            return  &(*(*this));
        }//直接可以通过对it->就可以访问结点中的成员
        Self& operator--()//前置--
        {
            _node = _node->pPre;
            return Self(_node);
        }
        Self operator--(int)
        {
            Node* Temp = _node;
            _node = _node->pPre;
            return Self(Temp);
        }
        bool operator!=(const _ListIterator&l)
        {
            return _node != l._node;
        }
        bool operator==(const _ListIterator&l)
        {
            return _node == l._node;
        }
        Node*_node;
    };//由于要去管理指向结点的指针，因此它的成员变量必然是指向结点的指针
    template<class T>
    class List
    {
    public:
        typedef _ListNode<T> Node;
        typedef _ListIterator<T, T&, T*> Iterator;
        typedef _ListIterator<T, const T&, const T*> Const_Iterator;
        Node *GetNode(const T&data)
        {
            return new Node(data);
        }
        List()//由于带头结点的循环双向链表需要构造出一个头结点并且头和尾都指向它自己
        {
            _pHead = GetNode(T());
            _pHead->pNext = _pHead;
            _pHead->pPre = _pHead;
        }
        ~List()
        {
            Clear();
            delete _pHead;
        }
        Iterator Begin()
        {
            return _pHead->pNext;
        }
        Const_Iterator Begin()const
        {
            return _pHead->pNext;
        }
        Iterator End()
        {
            return _pHead;
        }
        Const_Iterator End()const
        {
            return _pHead;
        }
        void PushBack(const T&data)
        {
            Insert(End(),data);
        }
        void PopBack()
        {
            Erase(--End());
        }
        void PushFront(const T&data)
        {
            Insert(Begin(),data);
        }
        void PopFront()
        {
            Erase(Begin());
        }
        Iterator Insert(Iterator Pos,const T&data)
        {
            Node* Temp = Pos._node;
            Node* pre = Temp->pPre;
            Node* Cur = GetNode(data);
            Cur->pNext = Temp;
            Temp->pPre = Cur;
            pre->pNext = Cur;
            Cur->pPre = pre;
            return Cur;
        }
        Iterator Erase(Iterator Pos)
        {
            assert(Pos!=End()&&Pos._node!=End()._node);
            Node* Temp = Pos._node;
            Node* pre = Temp->pPre;
            Node *next = Temp->pNext;
            pre->pNext = next;
            next->pPre = pre;
            delete Temp;
            return pre;
        }//只需要分两种情况删除的是头结点还是非头结点，高效
    
        void Clear()
        {
            Iterator it = Begin();
            while (it != End())
            {
                it=Erase(it);//如果不接受返回值迭代器就会失效，因为it1里面的结点指针仍旧是指向被删除的结点
                ++it;//对已经不存在的位置++，相当于对已经delete掉的再次使用，程序必然会崩溃
            }
        }//删除除了头结点之外的所有元素
        Node *_pHead;
    };
    void MyPrint(List<int> &l)
    {
        List<int>::Iterator it= l.Begin();
        while (it != l.End())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }
    void FunTest()//测试代码
    {
        struct AA
        {
            int a;
        };
        List<AA>l2;
        l2.PushBack(AA());
        List<AA>::Iterator it2 = l2.Begin();
        it2->a;
        List<int>l1;
        l1.PushBack(1);
        l1.PushBack(2);
        l1.PushBack(3);
        l1.PushFront(4);
        l1.PopFront();
        l1.PopBack();
        l1.Clear();
        List<int>::Iterator it1 = l1.Begin();
        while (it1 != l1.End())
        {
            cout<<*it1<<" ";
            ++it1;
        }
    }
    int main()
    {
        FunTest();
        system("pause");
        return 0;
    }

**小结：**  
首先这个迭代器的设计很巧妙代码复用率很高：它给出的模板参数列表是

template<class T,class Ref,class Ptr>

于是我们用const 类型的迭代器的时候自然会去调用const 类型的一系列的操作符重载的成员函数。使用非const类型的迭代器自然会去调用非const 类型的一系列的操作符重载的成员函数

而且在设计成带头结点的循环双向链表之后，我们就可以将删除尾结点和删除中间结点使用同一种方式来处理，更加方便。

在简单的模拟实现了STL中的list之后可以深刻的体会到STL中的list的设计的巧妙之处。这种框架还是很值得自己去学习的。