C++：list模拟实现

hello，各位小伙伴，本篇文章跟大家一起学习《C++：list模拟实现》，感谢大家对我上一篇的支持，如有什么问题，还请多多指教 ！
如果本篇文章对你有帮助，还请各位点点赞！！！

话不多说，开始进入正题

🍁list的逻辑结构以及节点代码

是一个双指针带头链表，所以我选择用一个结构体

ListNode

来维护节点，如下：

// List的节点类template<classT>structListNode{ListNode(const T& val =T()):_val(val),_pPre(nullptr),_pNext(nullptr){}
    ListNode<T>* _pPre;// 指向前一个结点
    ListNode<T>* _pNext;// 指向后一个节点
    T _val;// 该结点的值};

我对

ListNode<T>

改一个名字：

Node

：

typedef ListNode<T> Node;typedef Node* PNode;

🍁list类

🍃私有成员变量

_pHead

和私有成员函数

CreateHead()

private:voidCreateHead()// 创建头节点并且初始化{
        _pHead =newNode();
        _pHead->_pNext = _pHead;
        _pHead->_pPre = _pHead;}

    PNode _pHead;

🍃尾插函数和插入函数

尾插只是插入的其中一种方式，所以实现了插入函数，就能够实现尾插函数。
插入思路图解：在pos位置前插入值为val的节点

创建新节点值为value后；
使prev节点的_pNext指针指向newnode，newnode的节点的_pPre指向prev；
使cur节点的_pPre指针指向newnode，newnode的节点的_pNext指向cur；
最后返回iterator(newnode);

itearator

为迭代器，后面会实现

• 插入

// 在pos位置前插入值为val的节点
iterator insert(iterator pos,const T& val){
    Node* cur = pos._pNode;
    Node* newnode =newNode(val);
    Node* prev = cur->_pPre;// prev  newnode  cur
    prev->_pNext = newnode;
    newnode->_pPre = prev;
    newnode->_pNext = cur;
    cur->_pPre = newnode;returniterator(newnode);}

• 尾插

voidpush_back(const T& val){insert(end(), val);}

🍃构造函数

• 无参构造

list(const PNode& pHead =nullptr){CreateHead();/*_pHead = new Node();
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;*/}

• 带参构造（数值）

list(int n,const T& value =T()){CreateHead();for(int i =0; i < n;++i)push_back(value);}

• 带参构造（迭代器）

template<classIterator>list(Iterator first, Iterator last){CreateHead();while(first != last){push_back(*first);++first;}}

• 拷贝构造

list(const list<T>& l){CreateHead();// 复用带参构造（迭代器）
    list<T>temp(l.cbegin(), l.cend());// 与*this的头节点pHead交换指向swap(temp);}

🍃析构函数

clear()

为其中的成员函数，功能：清理

list

中的数据

~list(){clear();delete _pHead;
    _pHead =nullptr;/*Node* cur = _pHead->_pNext;
    Node* tmp = cur->_pNext;
    while (cur != _pHead)
    {
        delete cur;
        cur = tmp;
        tmp = tmp->_pNext;
    }
    tmp = cur = nullptr;
    _pHead->_pNext = _pHead;
    _pHead->_pPre = _pHead;*/}

🍃迭代器模拟

逻辑上并不难，也许难理解于模板

//List的迭代器结构体template<classT,classRef,classPtr>structListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;ListIterator(PNode pNode =nullptr):_pNode(pNode){}ListIterator(const Self& l){
        _pNode = l._pNode;}

    T&operator*(){assert(_pNode != _pNode->_pNext);return _pNode->_val;}

    T*operator->(){return&(*this);}

    Self&operator++(){
        _pNode = _pNode->_pNext;return*this;}

    Self operator++(int){
        PNode* tmp = _pNode;
        _pNode = _pNode->_pNext;return tmp;}

    Self&operator--(){
        _pNode = _pNode->_pPre;return*this;}

    Self&operator--(int){
        PNode* tmp = _pNode;
        _pNode = _pNode->_pPre;return tmp;}booloperator!=(const Self& l){return _pNode != l._pNode;}booloperator==(const Self& l){return!(*this!= l);}
    PNode _pNode;};

这段代码定义了一个模板结构

ListIterator

，用于表示

List

类的迭代器。让我们来解释模板声明部分：

template<classT,classRef,classPtr>;

这一行是模板声明，定义了一个模板类

ListIterator

，它有三个模板参数：

T、Ref 和 Ptr

。让我们逐个解释这些参数的作用：

1. T
   

   : 这是一个模板参数，表示迭代器指向的元素类型。在使用 ListIterator 时，你需要提供实际的类型作为 T 的值。

2. Ref
   

   : 这也是一个模板参数，表示迭代器的引用类型。通常情况下，当你通过迭代器解引用（使用 * 运算符）时，你希望得到的是元素的引用类型。所以 Ref 通常被设定为 T&，表示引用类型为 T 的元素。

3. Ptr
   

   : 这是迭代器的指针类型。与 Ref 类似，当你通过迭代器解引用（使用 -> 运算符）时，你希望得到的是元素的指针类型。因此，通常情况下 Ptr 被设定为 T*，表示指针类型为 T 的元素。

通过将这些参数设定为模板参数，

ListIterator

类可以适用于不同类型的元素，同时也可以提供不同的引用和指针类型。这样做使得

ListIterator

类更加灵活，能够适用于不同的使用场景。

• 封装的意义 将迭代器的实现从 List 类中分离出来，有几个重要的意义和优势：

1. 模块化设计：通过将迭代器封装为单独的类，可以实现更模块化的设计。这意味着 List 类的实现与迭代器的实现可以分开，每个类都专注于自己的职责。这样的设计使得代码更易于理解、维护和测试。
2. 可重用性：通过将迭代器设计为独立的类，可以在不同的容器类中重复使用相同的迭代器实现。例如，如果你有另一个类似于 List 的容器类，也需要迭代器来遍历其中的元素，你可以直接重用相同的迭代器实现，而无需重新编写。
3. 灵活性：将迭代器设计为独立的类使得它们的实现更加灵活。你可以在迭代器类中添加额外的功能或改变迭代器的行为，而不会影响到容器类的实现。这样的设计使得容器和迭代器的职责分离，每个类可以独立地演化和改进。
4. 通用性：独立的迭代器类可以设计成通用的，适用于多种容器类型。这意味着你可以为不同的容器类实现相同的迭代器接口，使得用户在使用不同的容器时无需学习不同的迭代器接口，提高了代码的一致性和可用性。

总的来说，将迭代器封装为独立的类使得代码更加模块化、可重用、灵活和通用，提高了代码的可维护性、可扩展性和可读性。

🍃

list

类中迭代器的使用

public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T,const T&,const T&> const_iterator;

• begin()和end()

// List Iterator
iterator begin(){return _pHead->_pNext;}

iterator end(){return _pHead;}

const_iterator begin()const{return _pHead->_pNext;}

const_iterator end()const{return _pHead;}

• erase****删除pos位置的节点，返回该节点的下一个位置

iterator erase(iterator pos){assert(pos._pNode != _pHead);
    Node* Prev = pos._pNode->_pPre;
    Node* Next = pos._pNode->_pNext;delete pos._pNode;
    Prev->_pNext = Next;
    Next->_pPre = Prev;returniterator(Next);}

🍃List Modify

voidpush_back(const T& val){insert(end(), val);}voidpop_back(){erase(--end());}voidpush_front(const T& val){assert(!empty());insert(begin(), val);}voidpop_front(){erase(begin());}

🍁全部代码

#pragmaonce#include<assert.h>#include<iostream>usingnamespace std;namespace My_List
{// List的节点类template<classT>structListNode{ListNode(const T& val =T()):_val(val),_pPre(nullptr),_pNext(nullptr){}
        ListNode<T>* _pPre;
        ListNode<T>* _pNext;
        T _val;};//List的迭代器类template<classT,classRef,classPtr>structListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;ListIterator(PNode pNode =nullptr):_pNode(pNode){}ListIterator(const Self& l){
            _pNode = l._pNode;}

        T&operator*(){assert(_pNode != _pNode->_pNext);return _pNode->_val;}

        T*operator->(){return&(*this);}

        Self&operator++(){
            _pNode = _pNode->_pNext;return*this;}

        Self operator++(int){
            PNode* tmp = _pNode;
            _pNode = _pNode->_pNext;return tmp;}

        Self&operator--(){
            _pNode = _pNode->_pPre;return*this;}

        Self&operator--(int){
            PNode* tmp = _pNode;
            _pNode = _pNode->_pPre;return tmp;}booloperator!=(const Self& l){return _pNode != l._pNode;}booloperator==(const Self& l){return!(*this!= l);}
        PNode _pNode;};//list类template<classT>classlist{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T,const T&,const T&> const_iterator;public:///// List的构造list(const PNode& pHead =nullptr){CreateHead();/*_pHead = new Node();
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;*/}list(int n,const T& value =T()){CreateHead();for(int i =0; i < n;++i)push_back(value);/*int cnt = 0;
            while (cnt < n)
            {
                PNode _first = new Node(value);
                PNode tmp = _pHead->_pPre;
                tmp->_pNext = _first;
                _first->_pPre = tmp;
                _first->_pNext = _pHead;
                _pHead->_pPre = _first;
                ++cnt;
            }*/}template<classIterator>list(Iterator first, Iterator last){CreateHead();while(first != last){push_back(*first);++first;}/*while (first != last)
            {
                PNode _first = new Node(*first);
                PNode tmp = _pHead->_pPre;
                tmp->_pNext = _first;
                _first->_pPre = tmp;
                _first->_pNext = _pHead;
                _pHead->_pPre = _first;
                ++first;
            }*/}list(const list<T>& l){CreateHead();
            list<T>temp(l.cbegin(), l.cend());swap(temp);/*iterator first = l._pHead->_pNext;
            iterator last = l._pHead;
            while (first != last)
            {
                PNode _first = new Node(*first);
                PNode tmp = _pHead->_pPre;
                tmp->_pNext = _first;
                _first->_pPre = tmp;
                _first->_pNext = _pHead;
                _pHead->_pPre = _first;
                ++first;
            }*/}

        list<T>&operator=(const list<T> l){CreateHead();swap(l);return*this;/*iterator first = l._pHead->_pNext;
            iterator last = l._pHead;
            while (first != last)
            {
                PNode _first = new Node(*first);
                PNode tmp = _pHead->_pPre;
                tmp->_pNext = _first;
                _first->_pPre = tmp;
                _first->_pNext = _pHead;
                _pHead->_pPre = _first;
                ++first;
            }
            return *this;*/}~list(){clear();delete _pHead;
            _pHead =nullptr;/*Node* cur = _pHead->_pNext;
            Node* tmp = cur->_pNext;
            while (cur != _pHead)
            {
                delete cur;
                cur = tmp;
                tmp = tmp->_pNext;
            }
            tmp = cur = nullptr;
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;*/}///// List Iterator
        iterator begin(){return _pHead->_pNext;}

        iterator end(){return _pHead;}

        const_iterator begin()const{return _pHead->_pNext;}

        const_iterator end()const{return _pHead;}///// List Capacity
        size_t size()const{
            Node* cur = _pHead->_pNext;
            size_t cnt =0;while(cur != _pHead){++cnt;
                cur = cur->_pNext;}return cnt;}boolempty()const{returnsize()==0;}// List Access
        T&front(){return _pHead->_pNext->_val;}const T&front()const{return _pHead->_pNext->_val;}

        T&back(){return _pHead->_pPre->_val;}const T&back()const{return _pHead->_pPre->_val;}// List Modifyvoidpush_back(const T& val){insert(end(), val);}voidpop_back(){erase(--end());}voidpush_front(const T& val){assert(!empty());insert(begin(), val);}voidpop_front(){erase(begin());}// 在pos位置前插入值为val的节点
        iterator insert(iterator pos,const T& val){
            Node* cur = pos._pNode;
            Node* newnode =newNode(val);
            Node* prev = cur->_pPre;// prev  newnode  cur
            prev->_pNext = newnode;
            newnode->_pPre = prev;
            newnode->_pNext = cur;
            cur->_pPre = newnode;returniterator(newnode);}// 删除pos位置的节点，返回该节点的下一个位置
        iterator erase(iterator pos){assert(pos._pNode != _pHead);
            Node* Prev = pos._pNode->_pPre;
            Node* Next = pos._pNode->_pNext;delete pos._pNode;
            Prev->_pNext = Next;
            Next->_pPre = Prev;returniterator(Next);}voidclear(){
            iterator cur =begin();while(cur !=end()){
                cur =erase(cur);}
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;}voidswap(list<T>& l){/*list<T> tmp = l;
            l = *this;
            *this = tmp;*/

            PNode tmp = _pHead;
            _pHead = l._pHead;
            l._pHead = tmp;}private:voidCreateHead(){
            _pHead =newNode();
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;}

        PNode _pHead;};};

你学会了吗？
好啦，本章对于《C++：list模拟实现》的学习就先到这里，如果有什么问题，还请指教指教，希望本篇文章能够对你有所帮助，我们下一篇见！！！

如你喜欢，点点赞就是对我的支持，感谢感谢！！！