C++：list模拟实现

2024-06-04 9098阅读

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

如果本篇文章对你有帮助，还请各位点点赞！！！

C++：list模拟实现 第1张

话不多说，开始进入正题

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

C++：list模拟实现 第2张

是一个双指针带头链表，所以我选择用一个结构体ListNode来维护节点，如下：

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

我对ListNode改一个名字：Node：

typedef ListNode Node;
typedef Node* PNode;

🍁list类

🍃私有成员变量_pHead和私有成员函数CreateHead()

private:
    void CreateHead()// 创建头节点并且初始化
    {
        _pHead = new Node();
        _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);

C++：list模拟实现 第3张

itearator为迭代器，后面会实现

  • 插入 
    // 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T& val)
{
    Node* cur = pos._pNode;
    Node* newnode = new Node(val);
    Node* prev = cur->_pPre;
    // prev  newnode  cur
    prev->_pNext = newnode;
    newnode->_pPre = prev;
    newnode->_pNext = cur;
    cur->_pPre = newnode;
    
    return iterator(newnode);
}
    • 尾插 
      void push_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
          • 带参构造（迭代器） 
            template 
list(Iterator first, Iterator last)
{
    CreateHead();
    while (first != last)
    {
        push_back(*first);
        ++first;
    }
}
            • 拷贝构造 
              list(const list& l)
{
    CreateHead();
    
    // 复用带参构造（迭代器）
    list 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
struct ListIterator
{
    typedef ListNode* PNode;
    typedef ListIterator 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;
    }
    bool operator!=(const Self& l)
    {
        return _pNode != l._pNode;
    }
    bool operator==(const Self& l)
    {
        return !(*this != l);
    }
    PNode _pNode;
};

              这段代码定义了一个模板结构 ListIterator，用于表示List类的迭代器。让我们来解释模板声明部分：

              template;

              这一行是模板声明，定义了一个模板类 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 iterator;
    typedef ListIterator 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;
    return iterator(Next);
}

                    🍃List Modify

                    void push_back(const T& val) { insert(end(), val); }
void pop_back() { erase(--end()); }
void push_front(const T& val) 
{ 
    assert(!empty());
    insert(begin(), val); 
}
void pop_front() { erase(begin()); }

                    🍁全部代码

                    #pragma once
#include
#include
using namespace std;
namespace My_List
{
    // List的节点类
    template
    struct ListNode
    {
        ListNode(const T& val = T())
            :_val(val)
            ,_pPre(nullptr)
            ,_pNext(nullptr)
        {}
        ListNode* _pPre;
        ListNode* _pNext;
        T _val;
    };
    //List的迭代器类
    template
    struct ListIterator
    {
        typedef ListNode* PNode;
        typedef ListIterator 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;
        }
        bool operator!=(const Self& l)
        {
            return _pNode != l._pNode;
        }
        bool operator==(const Self& l)
        {
            return !(*this != l);
        }
        PNode _pNode;
    };
    //list类
    template
    class list
    {
        typedef ListNode Node;
        typedef Node* PNode;
    public:
        typedef ListIterator iterator;
        typedef ListIterator 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 _pPre;
                tmp->_pNext = _first;
                _first->_pPre = tmp;
                _first->_pNext = _pHead;
                _pHead->_pPre = _first;
                ++cnt;
            }*/
        }
        template 
        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& l)
        {
            CreateHead();
            list 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& operator=(const list 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;
        }
        bool empty()const
        {
            return size() == 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 Modify
        void push_back(const T& val) { insert(end(), val); }
        void pop_back() { erase(--end()); }
        void push_front(const T& val) 
        { 
            assert(!empty());
            insert(begin(), val); 
        }
        void pop_front() { erase(begin()); }
        // 在pos位置前插入值为val的节点
        iterator insert(iterator pos, const T& val)
        {
            Node* cur = pos._pNode;
            Node* newnode = new Node(val);
            Node* prev = cur->_pPre;
            // prev  newnode  cur
            prev->_pNext = newnode;
            newnode->_pPre = prev;
            newnode->_pNext = cur;
            cur->_pPre = newnode;
            
            return iterator(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;
            return iterator(Next);
        }
        void clear()
        {
            iterator cur = begin();
            while (cur != end())
            {
                cur = erase(cur);
            }
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }
        void swap(list& l)
        {
            /*list tmp = l;
            l = *this;
            *this = tmp;*/
            PNode tmp = _pHead;
            _pHead = l._pHead;
            l._pHead = tmp;
        }
    private:
        void CreateHead()
        {
            _pHead = new Node();
            _pHead->_pNext = _pHead;
            _pHead->_pPre = _pHead;
        }
        PNode _pHead;
    };
};

                    你学会了吗？

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

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

                    C++：list模拟实现 第4张


相关阅读：

1、亚马逊测评买家号安全攻略，VPS使用指南，保障账号无忧测评！

2、VPS代理安卓App使用指南与优势深度解析

3、阿里云VPS个人使用指南，高效、安全、便捷，个人云托管的最佳选择！

4、VPS面板使用指南，带你探索未知神秘世界！

5、掌握虚拟专用服务，手机VPS软件使用指南

    高速稳定云服务器25元起
    免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

    相关阅读

    目录[+]