C++:list模拟实现

hello,各位小伙伴,本篇文章跟大家一起学习《C++:list模拟实现》,感谢大家对我上一篇的支持,如有什么问题,还请多多指教 !
如果本篇文章对你有帮助,还请各位点点赞!!!
在这里插入图片描述
话不多说,开始进入正题

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

在这里插入图片描述

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

// List的节点类
template<class T>
struct ListNode
{
    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:
    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);

在这里插入图片描述

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 < n; ++i)
        push_back(value);
}
  • 带参构造(迭代器)
template <class Iterator>
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<class T, class Ref, class Ptr>
struct ListIterator
{
    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;
    }

    bool operator!=(const Self& l)
    {
        return _pNode != l._pNode;
    }

    bool operator==(const Self& l)
    {
        return !(*this != l);
    }
    PNode _pNode;
};

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

template<class T, class Ref, class Ptr>;

这一行是模板声明,定义了一个模板类 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;

    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<assert.h>
#include<iostream>
using namespace std;

namespace My_List
{
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T())
            :_val(val)
            ,_pPre(nullptr)
            ,_pNext(nullptr)
        {}
        ListNode<T>* _pPre;
        ListNode<T>* _pNext;
        T _val;
    };


    //List的迭代器类
    template<class T, class Ref, class Ptr>
    struct ListIterator
    {
        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;
        }

        bool operator!=(const Self& l)
        {
            return _pNode != l._pNode;
        }

        bool operator==(const Self& l)
        {
            return !(*this != l);
        }
        PNode _pNode;
    };


    //list类
    template<class T>
    class list
    {
        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 <class Iterator>
        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;
        }

        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<T>& l)
        {
            /*list<T> 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模拟实现》的学习就先到这里,如果有什么问题,还请指教指教,希望本篇文章能够对你有所帮助,我们下一篇见!!!

如你喜欢,点点赞就是对我的支持,感谢感谢!!!

请添加图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/674030.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

音视频开发10 FFmpeg 内存模型-AVPacket, AVFrame

从现有的 Packet 拷贝一个新 Packet 的时候&#xff0c;有两种情况&#xff1a; • ①两个 Packet 的 buf 引用的是 同一数据缓存空间 &#xff0c;这时 候要注意数据缓存空间的释放问题&#xff1b; • ②两个 Packet 的 buf 引用不同的数据缓存空间 &#xff0c;每个 Pac…

移动机器人定位与导航实训记录

本次实训主要学习ros-tf的使用、slam使用、机器人自主导航&#xff0c;我先简单发出来&#xff0c;等我整理完再重新编辑一边。

AI图书推荐:结合ChatGPT的Java编程实用指南

《结合ChatGPT的Java编程实用指南》&#xff08;Practical Java Programming with ChatGPT&#xff09;是一本具有变革性意义的书籍&#xff0c;通过展示针对各种问题的多样化调查&#xff0c;挑战了传统软件开发的速度。这本书旨在通过集成OpenAI API、利用生成式人工智能和大…

性能优化随笔(一)

在软件开发过程中&#xff0c;一般要先实现功能方面的需求&#xff0c;功能方面的需求开发完毕之后&#xff0c;往往会考虑性能方面的优化。在业务发展的初期&#xff0c;性能往往能满足使用的需求&#xff0c;这时性能优化不是必不可少的。随着业务的发展&#xff0c;软件复杂…

常见加解密算法04 - 分组密码DES

​各位才华横溢&#xff0c;风度翩翩的读者们&#xff0c;你们好。今天我们讨论一下DES算法以及逆向识别。 DES算法要比RC4复杂的多&#xff0c;但是幸运的是它的逆向识别比RC4要简单很多&#xff0c;当你了解DES大致的实现原理之后就明白为什么了。 DES算法介绍 DES算法&am…

【前端开发--css学习笔记】CSS超详细的学习笔记。前端开发css学习笔记(非常详细,适合小白入门)

二&#xff0c;CSS学习笔记 1&#xff0c;CSS语法 1-1 CSS 实例 CSS声明总是以分号 ; 结束&#xff0c;声明总以大括号 {} 括起来: <!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title>菜鸟教程(runoob.com)</title…

湖南源点调研 为什么中小企业产品上市前一定要做市场调研?

本文由湖南长沙&#xff08;产品前测&#xff09;源点调研咨询编辑发布 可能有很多企业主会表示&#xff0c;市场调研&#xff0c;产品调研&#xff0c;不都是大公司、大品牌、上市公司才会有的流程吗&#xff0c;像我们这种小企业、小品牌、小厂家没有必要去那么做&#xff0…

Update! 基于RockyLinux9.3离线安装Zabbix6.0

链接&#xff1a; Ansible离线部署 之 Zabbixhttp://mp.weixin.qq.com/s?__bizMzk0NTQ3OTk3MQ&mid2247487434&idx1&sn3128800a0219c5ebc5a3f89d2c8ccf50&chksmc3158786f4620e90afe440bb32fe68541191cebbabc2d2ef196f7300e84cde1e1b57383c521a&scene21#we…

2024年6月 AWVS -24.4.27详细安装教程附下载教程含windows和linux多版本

免责声明 请勿利用文章内的相关技术从事非法测试。由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;作者不为此承担任何责任&#xff0c;请务必遵守网络安全法律法规。本文仅用于测试&#xff0c;请完成测试后…

[数据集][目标检测]电力工地场景下的人头检测数据集VOC+YOLO格式7035张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;7035 标注数量(xml文件个数)&#xff1a;7035 标注数量(txt文件个数)&#xff1a;7035 标注…

FastAPI vs Django:选择适合你的Python Web框架

文章目录 FastAPIDjango如何选择&#xff1f;总结 在Python Web开发领域&#xff0c;选择合适的框架对于项目的成功至关重要。FastAPI 和 Django 是两个备受关注的框架&#xff0c;各自拥有独特的优势和适用场景。本文将深入比较它们之间的特点&#xff0c;以帮助你做出明智的选…

操作系统错误答案汇总

第1章 计算机系统概述 1.1 软件vs应用程序&#xff1a;软件程序其他相关文件等。eg&#xff1a;一个游戏软件包括程序(.exe)和其它图片(.bmp等)、音效(.wav等)等附件&#xff0c;那么这个程序(.exe)称作“应用程序”&#xff0c;而它与其他文件&#xff08;图片、音效等&#…

如何从清空的回收站中恢复已删除的Word文档?

“嗨&#xff0c;我将 10 个 Word 文档移动到回收站&#xff0c;然后用清洁软件清理回收站。现在我意识到我犯了一个大错误——我删除了错误的文件。我想知道是否可以从清空的回收站中恢复已删除的Word文档。我没有数据恢复的经验&#xff0c;也不精通计算机技术。有没有简单的…

很酷的个人仪表盘honey

什么是 honey &#xff1f; honey 是一个很酷的个人仪表盘。采用纯 HTML、CSS、 JS编写的&#xff0c;因此不需要动态后端或特殊的 Web 服务器配置。它开箱即用&#xff0c;因为所有操作都是在客户端完成的。 官方提供了在线示例&#xff1a;https://honeyy.vercel.app/ 安装 …

1121 祖传好运

solution 好运数&#xff1a;去除任意位末尾数位 所得到的数都满足能够被当前数位整除 #include<iostream> #include<string> using namespace std; int main(){int k, flag;string s;cin >> k;while(k--){flag 1;cin >> s;for(int i 1; i < s.…

VRTK4.0学习——(一)

此开发基于Unity 6000.0.0f1 1.导入VRTK v4 Tilia Package Importer.unitypackage包 2.在PackManager中查看配置是否正确 3.点击 Window→Tilia→Package Importer 打开面板后点击 Add Scoped Registry 4.首先我们先将CameraRigs导入,CameraRigs中主要是启动VR头盔的功能&…

LeetCode题练习与总结:二叉树展开为链表--114

一、题目描述 给你二叉树的根结点 root &#xff0c;请你将它展开为一个单链表&#xff1a; 展开后的单链表应该同样使用 TreeNode &#xff0c;其中 right 子指针指向链表中下一个结点&#xff0c;而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。 …

MySQL连表查询练习

– 34. 查询所有员工的姓名和部门名称&#xff0c;没有部门的员工不需要展示 SELECTe.NAME 员工姓名,d.NAME 部门名称 FROMt_emp eINNER JOIN t_dept d ON e.dept_id d.id;– 35. 查询所有员工的姓名和部门名称&#xff0c;没有部门的员工展示BOSS SELECTe.NAME 员工姓名,i…

521源码-免费源码下载-在线变量命名工具前端源码-新手开发者工具

更多网站源码学习教程&#xff0c;请点击&#x1f449;-521源码-&#x1f448;获取最新资源 本工具地址&#xff1a;在线变量命名工具前端源码-新手开发者工具 - 521源码

活跃引进OA体系,打造“数字学校”

信息化建造高速开展的今日&#xff0c;越来越多的企事业单位开端自己重视工作办理&#xff0c;活跃引进OA体系来完善企业安排办理&#xff0c;进步企业协同工作功率。关于教育职业&#xff0c;OA工作体系有着绝佳的效果。如“数字学校”的打造。 数字化学校是使用计算机技能、网…