【C++】模拟实现list

举报
修修修也 发表于 2024/10/25 15:27:42 2024/10/25
【摘要】 🦄个人主页:修修修也 🎏所属专栏:实战项 目集 ⚙️操作环境:Visual Studio 2022​编辑目录一.了解 项 目及其功能 📌 了解list官方 标 准 📌 了解模 拟实现 list 📌 了解更底 层 的 list 实现 二.list迭代器和vector迭代器的异同 📌 迭代器的分 类 🎏 单 向迭代器( Forward Iterator) 🎏 双向迭代器(Bidi...

🦄个人主:修修修也

🎏所属专栏:实战项 目集

⚙️操作:Visual Studio 2022

​编辑


一.了解 目及其功能

📌 了解list官方

📌 了解模 拟实现 list

📌 了解更底 list 实现

二.list迭代器和vector迭代器的异同

📌 迭代器的分

🎏 向迭代器( Forward Iterator)

🎏 双向迭代器(Bidirectional Iterator)

🎏 随机迭代器(Random Access Iterator)

📌 list和vector的底 层实现 差异 迭代器的影响

三.逐步 实现项 目功能模 及其 逻辑详

📌 分析list的

📌 实现 list 模板

🎏 构造list 员变

🎏 实现 list 构造函数

📌 实现 list迭代器 模板

🎏 构造list迭代器 员变

🎏 实现 list迭代器 构造函数

🎏 实现 operator*重 函数

🎏 实现 前置 operator++重 函数

🎏 实现 后置 operator++重 函数

🎏 实现 前置 operator--重 函数

🎏 实现 后置 operator--重 函数

🎏 实现 operator!=重 函数

🎏 实现 operator==重 函数

🎏 实现 operator->重 函数

🎏 实现 const修 list迭代器 模板

📌 实现 list 模板

🎏 构造list 员变

🎏 实现 list empty_init()函数

🎏 实现 list 无参构造函数

🎏 实现 list 构造函数

🎏 实现 list swap()函数

🎏 实现 list operator=()函数

🎏 实现 list clear()函数

🎏 实现 list 析构函数

🎏 实现 list begin()函数

🌳 实现 普通 list begin()函数

🌳 实现 const修 list begin()函数

🎏 实现 list end()函数

🌳 实现 普通 list end()函数

🌳 实现 const修 list end()函数

🎏 实现 list insert()函数

🎏 实现 list erase()函数

🎏 实现 list push_front()函数

🎏 实现 list pop_front()函数

🎏 实现 list push_back()函数

🎏 实现 list pop_back()函数

🎏 实现 list size()函数

四. 目完整代

📌 test.cpp文件

📌 list.h 文件

结语


一.了解目及其功能

📌了解list官方

        在本次项目中我们的目标是拟实现一个list,先一起看一下C++标准文档中list的定义:cplusplus : C++ list 准文档 https://legacy.cplusplus.com/reference/list/list/?kw=list

​编辑

        总结一下:

1. list是可以在O(1)范在任意位置行插入和除的序列式容器,并且该容器可以前后双向迭代

2. list的带头双向循环链,带头双向循环链表中每个数据元素存在互不相关的独立点中,在节点中指向其前一个元素和后一个元素​编辑

3. list与forward_list(单链表)非常相似:最主要的不同在于forward_list是单链只能朝前迭代,让其更简单高效。

4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置行插入、移除元素的行效率更好

5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:访问list的第6个元素,必从已知的位置(比如部或者尾部)迭代到位置,在这段位置上迭代需要线性的时间开销;list需要一些外的空,以保存每个点的相关信息(对于存储类型较小元素的list来说这可能是一个重要的因素)

 声明:

        拟实现仅适用于STL初学小白了解list的简单实现,会合一些STL源参照,但是源中涉及的配置器部分我们暂不做涉及!

        在本篇博文中,将使用new/delete等方式来完成C++的动态内存的申.方式相比于空配置器效率有所降低,但是初学者较为友好的一种初步了解STL的一种方式.


📌了解模拟实现list

        该list模板使用动态内存分配空,可以用来任意数量的同型数据.

带头双向循环链(Node)需要包含三个成:前指prev,数据域val,后指next.

结点(Node)逻辑结构如下:

​编辑

  list提供的功能有:

1. list的默函数

2. list的swap()函数

3. list的clear()函数

4. list的begin()函数

5. list的end()函数

6. list的insert()函数

7. list的erase()函数

8. list的push_front()函数

9. list的pop_front()函数

10. list的push_back()函数

11. list的pop_back()函数

12. list的size()函数

13. list的operator=运算符重函数

        注意,因为我们要实现的list类并不只足于只能存一种固定型的元素,我们在一个项目中,可能会建几个存不同型元素的list,如:

list<int> lage; //存放学生年龄

list<string> lname; //存放学生姓名

list<double> lhigh; //存放学生身高

list<Student> lstu; //存放自定义学生类

        因此,我们需要将list实现为一个模板,这样才可以满足上面的需求,有关C++泛型程模板相关知识还不是很了解的朋友可以先移步:

【C++】初 模板 https://blog.csdn.net/weixin_72357342/article/details/137910913?spm=1001.2014.3001.5502


📌了解更底list实现

        由于在之前C言模拟实现双向带头环链的时候我们已经对链表的构和操作行的详细的解析,所以本篇博客的重点将会是C++的法特性,而不会很细致的深入探究链表在操作上的结构特性,如果有对链表操作的底原理和逻辑的朋友可以先移步更偏底层逻辑实现C实现双向循环链的文章:

【数据 构】 C 实现带头 双向循 环链 表万字 (附完整运行代 ) https://blog.csdn.net/weixin_72357342/article/details/134513792?spm=1001.2014.3001.5502

​ 该图为文章部分节选 编辑


二.list迭代器和vector迭代器的异同

📌迭代器的分

        迭代器是一种许顺访问其元素而无需暴露底表示。根据其访问方式和特性,迭代器可以被分为不同类型。这里我们介绍三种主要的迭代器:向迭代器、双向迭代器随机迭代器

🎏向迭代器(Forward Iterator)

        向迭代器只允许顺访问元素且只能从到尾行迭代。它不能返回到先前的元素。C++的forward_list、unordered_map、unordered_set等数据结构的迭代器都可以被视作单向迭代器。

特点:

只能向前移,即只能++操作。

没有回退功能。


🎏双向迭代器(Bidirectional Iterator)

        双向迭代器允在迭代向前和向后移,可以在遍历过程中回退。这种迭代器常用于需要访问前一个元素的场景。C++的list、map、set等数据结构的迭代器都可以被视作双向迭代器。

特点:

支持向前和向后移,即支持 ++ / -- 操作.

在迭代程中返回到先前的元素。


🎏随机迭代器(Random Access Iterator)

        随机迭代器允在任意序中访问元素,可以直接通索引访问这种迭代器在数组等数据结构中常见,因为它们支持快速随机访问。C++的vector、string、deque等数据结构的迭代器都可以被视作随机迭代器。

特点:

可以跳到任何元素,即可以 ++ / -- / + / - 操作。

每个元素的访问时间度通常是 O(1)。


📌list和vector的底层实现差异迭代器的影响

        我们知道,vector的底层实现是传统序表的形式,这种形式下象的指然的就是迭代器,并且是随机迭代器,它可以通物理的++ / -- / + / - 来精确定位要找到的元素位置.

        vector底层示意图:​编辑

        但是由于list在底层实现带头双向循环链的形式,这种形式下象的指无法承担起迭代器的功能,因为它在物理内存中 ++ / -- 的结果是未知的内存块,我们想要的是对迭代器 ++ / -- 后它就能自动的指向链表的下一个/前一个结点,因此想要达到迭代器的效果,就只能自己将点指封装成一个,然后重载结点指 ++ / -- / != /的逻辑,使其可以正常完成迭代器的功能,后面我们会着重分析并搭建迭代器的结构.

        list底层示意图:

​编辑


三.逐步实现项目功能模及其逻辑详

        通过第一部分对项目功能的介绍,我们已经对list的功能有了大致的了解,虽然看似需要实现的功能很多,貌似一时间不知该如何下手,但我们可以分步分模来分析目的流程,最后再将各部分行整合,所以大家不用担心,跟着我一步一步分析吧!


!!!注意,部分的代只是详细某一部分的实现逻辑,故可能会减一些与部分不相关的代以便大家理解,需要看或拷完整详细的朋友可以移步本文第四部分。


📌分析list的

        我们在之前C语言阶段就已经一起模拟实现过带头双向循环链表,可以知道C语言中带头双向循环链表的构是由两部分的,一部分是,一部分是表本身.因此我们至少要封装两个模板才能够组带头双向循环链.

        但是在C++中,由于STL引入了迭代器,并且因为list的点指在空上不像vector那样连续,不能承担起迭代器的功能,所以点指封装起来,设计一个迭代器模板来完成迭代器相关操作的重以便完成迭代器的功能.

        综上所述,我们在本篇中要实现的结构如下图所示:

​编辑

      根据前面的分析,我们可以先搭建一个代框架(该部分删除了大量的注释,只是了把框架先拎出来给大家参考一下,后续会在具体实现部分有详解): 

namespace mfc

{

    template<class T>//链表结点类模板


//struct定义结点就直接是公有的,如果用class就要将其设为public

    struct list_node

    {

//成员变量

        list_node<T>* _next;

        list_node<T>* _prev;

        T _val;


//构造函数

        list_node(const T& val = T()){}

    };



    template<class T,class Ref,class Ptr>//链表迭代器类模板

    struct __list_iterator

    {

//成员变量

        typedef list_node<T> Node;

        typedef __list_iterator<T, Ref, Ptr> self;

        Node* _node;


//构造函数

        __list_iterator(Node* node){}


        //操作符重载函数

        Ref operator*(){}

        Ptr operator->(){}

        

        self& operator++(){}

        self operator++(int){}

        self& operator--(){}

        self operator--(int){}


        bool operator!=(const self& it) const{}

        bool operator==(const self& it) const{}

    };



    template<class T>//链表类模板

    class list

    {

        typedef list_node<T> Node;


//成员变量

private:

        Node* _head;


//成员函数

    public:

        typedef __list_iterator<T,T&,T*> iterator;

        typedef __list_iterator<T,const T&,const T*> const_iterator;

        

//迭代器相关函数

        iterator begin(){}

        iterator end(){}

        const_iterator begin() const{}

        const_iterator end() const{}


//默认成员函数

        void empty_init(){}

        list(){}

        list(const list<T>& lt){}

        void swap(list<T>& lt){}

        list<T>& operator=(list<T> lt){}

        ~list(){}


//成员函数

        void clear(){}

        void push_front(const T& x){}

        void pop_front(){}

        void push_back(const T& x){}

        void pop_back(){}

        iterator insert(iterator pos, const T& x){}

        iterator erase(iterator pos){}

        size_t size(){}

    };

}


📌实现list模板

🎏构造list员变

        list结点的成员比较简单,我们在第一部分也已经大致介绍过了,即:

        带头双向循环链(Node)需要包含三个成:前指prev,数据域val,后指next.结点(Node)逻辑结构如下:

编辑

        这里还有一个小的点需要提一下,我们在这里实现的list_node类,后续是要给list类使用的,
考虑到后续表的操作函数中会有直接操作点成员变量的情况,如:

prev->_next = newnode; //相当于在list_node外部直接通过类指针访问了类成员变量_next

        基于class的封装特性,class的员变量一般都是默认为私有的,如果我们要允许其他类直接访问class的成员变量和函数,就要将其都设置为public,或者通过友元/内部类来解决成员访问问题.

        既然如此,我们不妨直接使用struct定义结点成员变量和函数,因为struct定的成员变量和函数就是公有,完全可以满足我们的需求.

        综上所述,该部分代码如下:

template<class T>//链表结点类模板


struct list_node

{

    list_node<T>* _next;

    list_node<T>* _prev;

    T _val;

};


🎏实现list构造函数

        list结点的构造函数我们实现两个即可,一个是有参构造,一个是无参构造,而无参构造又可以通过给缺省的方式和有参构造合二,所以我们用初始化列表来实现一下list_node的构造函数:

//缺省值的作用是在无参调用时直接去调用模板实例化的类的无参构造函数

//这里一定不能将缺省值给0/nullptr!因为你不知道模板实例化的类具体到底是内置类型还是自定义类型(如Date)

//所以要显示调用T类型它自己的无参构造函数

list_node(const T& val = T())

    :_next(nullptr)

    ,_prev(nullptr)

    ,_val(val)

{}


📌实现list迭代器模板

🎏构造list迭代器员变

        list迭代器类的目的是改造并封装点指,使其行符合我期望的迭代器行,所以list迭代器的成员变量就是list结点的指针:

struct __list_iterator

{

typedef list_node<T> Node;

//这里typedef是为了防止我们把成员类型写成list_node*

//对于类模板来说,类名不是类型,类名实例化出的类才是类型

//即 list_node 不是类的类型 而 list_node<int> 才是类的类型


Node* _node;

};


🎏实现list迭代器构造函数

        list的迭代器构造的情况都是将一个已存在的点指针传给iterator,使之成list的迭代器,不存在无参构造的情况,因此迭代器的构造都是接收一个Node*的指针参数,然后将它赋值给_node成员变量即可,代码如下:

__list_iterator(Node* node)

    :_node(node)

{}


🎏实现operator*重函数

        对迭代器解引用的操作是list点里面的数据,所以我们重载的operator*函数要完成的就是返回给调用函数这个迭代器指向结点的数据_val,代码如下:

//const迭代器的设计让这里的返回值又套了一个模板参数Ref

//在这里不理解没关系,我们最后实现const迭代器时会详细讲

//在这里可以先认为根据模板的实例化不同 Ref = T& / const T&


Ref operator*()

{

    return _node->_val;

}


🎏实现前置operator++重函数

        迭代器前置++的功能是使迭代器指向下一个,并返回下一个表的,要指向下一个结点,其实就是迭代器的结点指针改为_node->_next,代码如下:

//因为我们把__list_iterator也写成类模板了,而返回值必须写的是类模板实例化的类型

//即__list_iterator<T, Ref, Ptr>

//为了方便,我们不妨typedef一下这个为self 方便后续用



//++前置

self& operator++()

{

    //更新一下*this的_node指针,然后再返回*this

    _node = _node->_next;

    return *this;

}


🎏实现后置operator++重函数

        迭代器后置++的功能是使迭代器指向下一个,并返回表没有++前的,要指向下一个结点,其实就是迭代器的结点指针改为_node->_next,代码如下:

//后置++

self operator++(int)

{

    self tmp(*this);


    //更新一下*this的_node指针,然后再返回*this当前的值

    _node = _node->_next;


    return tmp;

}


🎏实现前置operator--重函数

        迭代器前置--的功能是使迭代器指向上一个,并返回上一个表的,要指向上一个结点,其实就是迭代器的结点指针改为_node->_prev,代码如下:

//--前置

self& operator--()

{

    //更新一下*this的_node指针,然后再返回*this

    _node = _node->_prev;


    return *this;

}


🎏实现后置operator--重函数

        迭代器后置--的功能是使迭代器指向上一个,并返回没有--前表的,要指向上一个结点,其实就是迭代器的结点指针改为_node->_prev,代码如下:

//后置--

self operator--(int)

{

    self tmp(*this);


    //更新一下*this的_node指针,然后再返回*this

    _node = _node->_prev;


    return tmp;

}


🎏实现operator!=重函数

        判断两个迭代器是否不相等,就是判断它是否不指向同一个,即地址是否不相同,代码如下:

bool operator!=(const self& it) const

{

    return _node != it._node;

}


🎏实现operator==重函数

        判断两个迭代器是否相等,就是判断它是否指向同一个,即地址是否相同,代码如下:

bool operator==(const self& it) const

{

    return _node == it._node;

}


🎏实现operator->重函数

        我们先来看一下下面代码里库里的list的使用上有没有什么特别的地方:

​编辑

        可以看到,对迭代器it而言,下面两行代码的结果是一样的,都是取出成员变量x:

it->x ;

(*it).x ;

        但是如果把这段代码用我们实现的list来完成,就会出错:

​编辑

        再看一下 . 操作符 ->操作符的定义:

📖 . 操作符

用法:用于直接访问对象的成员(属性或方法)。

适用:当你有一个对象的实例时,使用 . 操作符来访问其成员。

📖 -> 操作符

用法:用于通过指向对象的指针来访问对象的成员。

适用:当你有一个对象的指针时,使用 -> 操作符来访问其成员。

         综上所述,我们还需要实现 operator-> ()函数,以便可以迭代器直接访问Node型的成_val,对迭代器而言, operator->()函数的作用就是通过迭代器指针直接返回结点Node的数据_val的地址.以便->操作符能够通过operator->()函数的返回值访问_val的成员,代码如下:

//const迭代器的设计让这里的返回值又套了一个模板参数Ptr

//在这里不理解没关系,我们最后实现const迭代器时会详细讲

//在这里可以先认为根据模板的实例化不同 Ptr = T* / const T*


Ptr operator->()

{

    return &_node->_val;

}

        可能有朋友不理解为什么上面的函数里的 it->x 有些奇怪,分析一下好像写成it->->x才,我画图帮大家分析并解释一下原因:

​编辑


🎏实现const修list迭代器模板

        我们在实现list迭代器时有一个无法忽视的问题,就是要实现正常象迭代器和const修饰对象迭代器,先来看一下我们以往在实现vector的时候是怎么实现const迭代器的:

编辑

        先画图演示一下两种const修饰指针的区别,可见上图中vector的const迭代器显然是第一张图示的情况:

​编辑​编辑

        我们创建const迭代器的目的就是const修象在使用迭代器不能通迭代器*或者->的访问修改其指向的数据.那么我们要实现的list的迭代器当然是第一种const修饰的指针,那么我们list就直接套用vector的const迭代器的写法可以吗?像下面这样?

​编辑

        答案是绝对不可以的,简单画图分析一下大家就明白了:

​编辑

        基于这个原因,我们没法通直接使用const来修list迭代器的方式来const_list迭代器,只能寻找其他的方法来实现迭代器.

        通过前面的分析,我们知道,我们实现const迭代器就是要实现迭代器指向的_val是不能改.那我们为什么不在解引用重函数operator*()部分直接它的返回const修型引用呢?就像下面这样:

const T& operator*()

{

    return _node->_val;

}

        同理,operator->()函数也可以通限制其返回来限制_val不能被更改:

const T* operator->()

{

    return &_node->_val;

}

        只要完成两个限制,我们就可以达到const修迭代器的要求,那么再写一个一模一样的类模板,只是operator*()函数和operator->()函数的返回值和普通迭代器不同就可以了.

        但是,既然我们都用类模板了,为什么不便把两个合成一下,写成一个多参数的模板?当我使用普通迭代器,参数就< T , T& , T* > ; 当我使用const迭代器,参数就

< T , const T& , const T* > . 综上所述,list迭代器部分完整代码如下:

//迭代器的本质是通过自定义类型的封装,改变了类型的行为

//内置类型的行为不符合我们的要求时,C++就可以用一个类来封装这个类型,然后自己定义这个类型的行为

//这里的思路是,我们本身就想用结点的指针来做list的迭代器,但是因为list的结构原因

//它的++ / -- / * / != 等操作得到的结果不是我们想要的

//所以我们就把这个结点指针封装起来,重新定义它的++ / -- / * / != 等操作

//使这些操作得到的结果是我们想要的


template<class T,class Ref,class Ptr>

struct __list_iterator

{

    typedef list_node<T> Node;

    typedef __list_iterator<T, Ref, Ptr> self;


//成员变量

    Node* _node;


//成员函数

    __list_iterator(Node* node)

        :_node(node)

    {}


    Ref operator*()

    {

        return _node->_val;

    }


    Ptr operator->()

    {

        return &_node->_val;

    }


    //++前置

    self& operator++()

    {

        //更新一下*this的_node指针,然后再返回*this

        _node = _node->_next;

        return *this;

    }


    //后置++

    self operator++(int)

    {

        self tmp(*this);

        //更新一下*this的_node指针,然后再返回*this

        _node = _node->_next;

        return tmp;

    }


    //--前置

    self& operator--()

    {

        //更新一下*this的_node指针,然后再返回*this

        _node = _node->_prev;

        return *this;

    }


    //后置--

    self operator--(int)

    {

        self tmp(*this);

        //更新一下*this的_node指针,然后再返回*this

        _node = _node->_prev;

        return tmp;

    }    


    bool operator!=(const self& it) const

    {

        return _node != it._node;

    }


    bool operator==(const self& it) const

    {

        return _node == it._node;

    }

};


📌实现list模板

🎏构造list员变

        list类成员变量组成比较简单,就是一个哨兵位的头结点指(如果介意size()函数每次调用O(n)的时间复杂度,那么可以在里再加一个_size成,后续size()函数只需要返回这个成员变量就行,但是每个更改链表结点个数的函数都要记得更新_size,这里我们就只是实现一个O(n)的size()函数吧)

        代码如下:

template<class T>

class list

{

    typedef list_node<T> Node;

public:

/*

    因为iterator和const_iterator只有operator*和operator->的返回值不同

    所以我们不如把operator*和operator->的返回值也设置成模板参数,

    当是iterator的时候,返回值模板就是T&/T*

当是const_iterator的时候,返回值模板就是const T&/const T*

    本质上iterator和const_iterator还是两个类,但是用模板可以简化一些

*/


    typedef __list_iterator<T,T&,T*> iterator;

    typedef __list_iterator<T,const T&,const T*> const_iterator;


private:

Node* _head;

};


🎏实现listempty_init()函数

        因为后面无参构造函数和拷贝构造函数都需要建一个哨兵位的头结,并初始化其成,我们直接将这个操作封装成一个empty_init()函数,代码如下:

void empty_init()

{

    _head = new Node;

    _head->_prev = _head;

    _head->_next = _head;

}


🎏实现list无参构造函数

        list类无参构造函数主要功能是建一个哨兵位的头结,并初始化其成.这个代码块我们之前已经封装成了一个函数,直接调用就行,代码如下:

list()

{

    empty_init();

}


🎏实现list构造函数

        拷贝构造函数的功能是深拷一个一模一,那我第一步是建一个新的头结,再把原表的点一个一个拷贝链接在新表上就可以了,代码如下:

list(const list<T>& lt)

{

    empty_init();


    for (auto& e : lt)

    {

        push_back(e);

    }

}


🎏实现listswap()函数

        swap()函数的功能是两个list,只需要两个里的成员变量即可,我们前面实现时成员只有_head,那就直接交_head就行,如果有加了_size成员的朋友记得还要交换_size,代码如下:

void swap(list<T>& lt)

{

    std::swap(_head, lt._head);

}


🎏实现listoperator=()函数

        我们在string和vector的模拟实现中都使用过一种简单的赋值操作符重载方式,思路就是直接把形参lt的直接拷贝给*this,这样*this里的就是我想要赋给了,代码如下:

list<T>& operator=(list<T> lt)

{

    swap(lt);

    return *this;

}


🎏实现listclear()函数

        clear()函数的作用就是清空表中的所有,但不包括头结.我们序将表中的点逐一即可,代码如下:

void clear()

{

    iterator it = begin();

    while (it != end())

    {

        it = erase(it);

    }

}


🎏实现list析构函数

        析构函数的作用就是销毁整个,其执行逻辑实际上就是除所有+毁头结,我们复用一下clear()再销毁头结点就可以,代码如下:

~list()

{

    clear();


    delete _head;

    _head = nullptr;

}


🎏实现listbegin()函数

🌳实现普通listbegin()函数

        begin()函数就是要返回表第一个有效点的迭代器,实际上就是头结点后一个结点的指针,迭代器的底层实现Node*,所以里直接返回Node*,不强转成迭代器型也没问题,因为单参数的构造函数支持转换,代码如下:

iterator begin()

{

    //return _head->_next;

    //上下两种方式都可以

    return (iterator)_head->_next;

}


🌳实现const修listbegin()函数

        const修饰list的begin()函数和普通list类的begin()函数的区别就是函数接收的是const修的参数,返回的是const修的迭代器,代码如下:

const_iterator begin() const

{

    return (const_iterator)_head->_next;

}


🎏实现listend()函数

🌳实现普通listend()函数

       end()函数就是要返回表最后一个有效点后一个点的迭代器,实际上就是头结点的指针,迭代器的底层实现Node*,所以里直接返回Node*,不强转成迭代器型也没问题,因为单参数的构造函数支持转换,代码如下:

iterator end()

{

    return (iterator)_head;

}


🌳实现const修listend()函数

        const修饰list的end()函数和普通list类的end()函数的区别就是函数接收的是const修的参数,返回的是const修的迭代器,代码如下:

const_iterator end() const

{

    return (const_iterator)_head;

}


🎏实现listinsert()函数

        这里插入的逻辑如下图:

​编辑

        不同之处在于C++插入的位置参数和返回的位置都是迭代器,具体代码逻辑见代码注释,代码如下:

//pos位置之前插入

iterator insert(iterator pos, const T& x)

{

    //纪录下pos位置和pos的上一个位置

    Node* cur = pos._node;

    Node* prev = cur->_prev;


    //创建新结点

    Node* newnode = new Node(x);


    //将pos的上一个结点和新结点相互链接

    prev->_next = newnode;

    newnode->_prev = prev;


    //将新结点和pos结点相互链接

    cur->_prev = newnode;

    newnode->_next = cur;


    //返回新插入的结点的迭代器

    return newnode;

}


🎏实现listerase()函数

        这里删除的逻辑如下图:

​编辑

        不同之处在于C++除的位置参数和返回除后下一个点的位置都是迭代器,具体代码逻辑见代码注释,代码如下:

//删除pos位置的结点

iterator erase(iterator pos)

{

    //不能删哨兵位的头结点

    assert(pos != end());


    //纪录下pos位置, pos的上一个位置和下一个位置

    Node* cur = pos._node;

    Node* prev = cur->_prev;

    Node* next = cur->_next;


    //将pos的上一个位置和下一个位置相互链接

    prev->_next = next;

    next->_prev = prev;


    //删除pos位置结点

    delete cur;


    //返回pos位置的下一个结点的迭代器

    return next;

}


🎏实现listpush_front()函数

        push_front()函数就是在第一个点之前插入,我们直接复用insert()函数即可,代码如下:

void push_front(const T& x)

{

    insert(begin(), x);

}


🎏实现listpop_front()函数

        pop_front()函数就是除第一个,我们直接复用erase()函数即可,代码如下:

void pop_front()

{

    erase(begin());

}


🎏实现listpush_back()函数

        push_back()函数就是在最后一个点之后插入,即头结点之前插入结点,我们直接复用insert()函数即可,代码如下:

void push_back(const T& x)

{

    insert(end(), x);

}


🎏实现listpop_back()函数

        pop_back()函数就是除最后一个,即删除头结点之前的那个结点,我们直接复用erase()函数即可,代码如下:

void pop_back()

{

    erase(--end());

}


🎏实现listsize()函数

        size()有两种求法:

1. 如果list没有成员变量_size,就写一个函数手动遍历一遍计算一下有多少个结点,该方法时间复杂度是O(n).

2. 如果有成员变量_size,就可以直接返回_size的值.

         我们这里采用第一种方式,代码如下:

        

size_t size()

{

    size_t sz = 0;


//通过迭代器遍历链表

    iterator it = begin();

    while (it != end())

    {

        ++sz;

        ++it;

    }


    return sz;

}


四.目完整代

         因为模板定和声明不能分离,所以我们将程序运行的代码分别在两个工程文件中编辑,完整代码如下:

📌test.cpp文件

//仅测试list功能用

#include"STL_List.h"


int main()

{

    mfc::test_list1();

    mfc::test_list2();


    return 0;

}


📌list.h 文件

#pragma once

#include<iostream>

#include<assert.h>

using namespace std;


namespace mfc

{

    template<class T>

    //链表的链和结点分装成两个类

    struct list_node //struct定义结点就直接是公有的,如果用class就要将其设为public

    {

        list_node<T>* _next;

        list_node<T>* _prev;

        T _val;


        list_node(const T& val = T())

            :_next(nullptr)

            ,_prev(nullptr)

            ,_val(val)

        {}

    };


    template<class T,class Ref,class Ptr>

    //迭代器的本质是通过自定义类型的封装,改变了类型的行为


    //内置类型的行为不符合我们的要求时,C++就可以用一个类来封装这个类型,然后自己定义这个类型的行为

    //这里的思路是,我们本身就想用结点的指针来做list的迭代器,但是因为list的结构原因

    //它的++ / -- / * / != 等操作得到的结果不是我们想要的

    //所以我们就把这个结点指针封装起来,重新定义它的++ / -- / * / != 等操作

    //使这些操作得到的结果是我们想要的

    struct __list_iterator

    {

        typedef list_node<T> Node;

        typedef __list_iterator<T, Ref, Ptr> self;

        Node* _node;


        __list_iterator(Node* node)

            :_node(node)

        {}


        //const迭代器的设计

        Ref operator*()

        {

            return _node->_val;

        }


        Ptr operator->()

        {

            return &_node->_val;

        }



        //++前置

        self& operator++()

        {

            //更新一下*this的_node指针,然后再返回*this

            _node = _node->_next;

            return *this;

        }


        //后置++

        self operator++(int)

        {

            self tmp(*this);

            //更新一下*this的_node指针,然后再返回*this

            _node = _node->_next;

            return tmp;

        }



        //--前置

        self& operator--()

        {

            //更新一下*this的_node指针,然后再返回*this

            _node = _node->_prev;

            return *this;

        }


        //后置--

        self operator--(int)

        {

            self tmp(*this);

            //更新一下*this的_node指针,然后再返回*this

            _node = _node->_prev;

            return tmp;

        }    



        bool operator!=(const self& it) const

        {

            return _node != it._node;

        }


        bool operator==(const self& it) const

        {

            return _node == it._node;

        }


    };




    template<class T>

    class list

    {

        typedef list_node<T> Node;

    public:

        //因为iterator和const_iterator只有operator*和operator->的返回值不同

        //所以我们不如把operator*和operator->的返回值也设置成模板参数,

        //当是iterator的时候,返回值模板就是T&/T*

        //当是const_iterator的时候,返回值模板就是const T&/const T*

        //本质上iterator和const_iterator还是两个类,但是用模板可以简化一些

        typedef __list_iterator<T,T&,T*> iterator;

        typedef __list_iterator<T,const T&,const T*> const_iterator;

        

        iterator begin()

        {

            //因为迭代器的底层实现是Node*,所以这里直接返回Node*没问题

            //单参数的构造函数支持隐式类型转换

            //return _head->_next;

            //所以上下两种方式都可以

            return (iterator)_head->_next;

        }


        iterator end()

        {

            return (iterator)_head;

        }


        const_iterator begin() const

        {

            return (const_iterator)_head->_next;

        }


        const_iterator end() const

        {

            return (const_iterator)_head;

        }


        void empty_init()

        {

            _head = new Node;

            _head->_prev = _head;

            _head->_next = _head;

        }



        list()

        {

            empty_init();

        }


        list(const list<T>& lt)

        {

            empty_init();


            for (auto& e : lt)

            {

                push_back(e);

            }

        }


        void swap(list<T>& lt)

        {

            std::swap(_head, lt._head);

        }


        list<T>& operator=(list<T> lt)

        {

            swap(lt);

            return *this;

        }


        ~list()

        {

            clear();


            delete _head;

            _head = nullptr;

        }


        void clear()

        {

            iterator it = begin();

            while (it != end())

            {

                it = erase(it);

            }

        }



        void push_front(const T& x)

        {

            insert(begin(), x);

        }

        void pop_front()

        {

            erase(begin());

        }


        void push_back(const T& x)

        {

            /*

            //找尾

            Node* tail = _head->_prev;

            Node* newnode = new Node(x);

            

            //链接

            tail->_next = newnode;

            newnode->_prev = tail;

            newnode->_next = _head;

            _head->_prev = newnode;

            */

            insert(end(), x);

        }


        void pop_back()

        {

            erase(--end());

        }


        //pos位置之前插入

        iterator insert(iterator pos, const T& x)

        {

            //纪录下pos位置和pos的上一个位置

            Node* cur = pos._node;

            Node* prev = cur->_prev;


            //创建新结点

            Node* newnode = new Node(x);


            //将pos的上一个结点和新结点相互链接

            prev->_next = newnode;

            newnode->_prev = prev;


            //将新结点和pos结点相互链接

            cur->_prev = newnode;

            newnode->_next = cur;


            //返回新插入的结点的迭代器

            return newnode;

        }


        //删除pos位置的结点

        iterator erase(iterator pos)

        {

            //不能删哨兵位的头结点

            assert(pos != end());


            //纪录下pos位置, pos的上一个位置和下一个位置

            Node* cur = pos._node;

            Node* prev = cur->_prev;

            Node* next = cur->_next;


            //将pos的上一个位置和下一个位置相互链接

            prev->_next = next;

            next->_prev = prev;


            //删除pos位置结点

            delete cur;


            //返回pos位置的下一个结点的迭代器

            return next;

        }


        //size求法1:写函数

        //方法2:加一个成员变量_size.然后insert就++,erase就--,初始化记得附0

        size_t size()

        {

            size_t sz = 0;

            iterator it = begin();

            while (it != end())

            {

                ++sz;

                ++it;

            }

            return sz;

        }



    private:

        //写成list_node* _head;是错误的

        //因为有了类模板后,类名就不是类型了,只有类模板显示实例化出的类才是类型

        Node* _head;

    };


    //迭代器测试打印函数

    void Print(const list<int>& lt)

    {

        list<int>::const_iterator it = lt.begin();


        while (it != lt.end())

        {

            cout << *it << " ";

            ++it;

        }

        cout << endl;

    }

    

    //测试函数1

    void test_list1()

    {

        list<int> lt;


        lt.push_back(1);

        lt.push_back(2);

        lt.push_back(3);

        lt.push_back(4);


        list<int>::iterator it = lt.begin();//这个地方把begin()赋给it是拷贝构造

        //而iterator没有实现拷贝构造,则默认就是浅拷贝

        //没有出错的原因就是,这里本身就是应该浅拷贝

        //我把begin()赋值给it,本身就是希望it指向这个结点,而不是指向这个结点的拷贝

        //那么,多个指针指向一个结点没有崩溃的原因是,我们没有进行二次释放操作

        //一般来讲,指针的销毁都伴随着空间的销毁,但是迭代器并没有销毁链表结点的权力

        //所以我们不写迭代器的析构函数,迭代器的销毁不导致结点的释放,所以不会有二次释放的问题

        while (it != lt.end())

        {

            cout << *it << " ";

            ++it;

        }

        cout << endl;


        for (auto e : lt)

        {

            cout << e << " ";

        }

        cout << endl;


        Print(lt);

    }


    //测试函数2

    void test_list2()

    {

        class Point {

        public:

            int x;

            int y;

            Point(int xCoord = 0, int yCoord = 0)

                : x(xCoord)

                , y(yCoord)

            {}

        };


        list<Point> lt;

        lt.push_back(Point(1, 1));

        lt.push_back(Point(2, 2));

        lt.push_back(Point(3, 3));

        lt.push_back(Point(4, 4));

        list<Point>::iterator it = lt.begin();

        while (it != lt.end())

        {

            cout << it->x << "," << it->y << endl;

            cout << (*it).x << "," << (*it).y << endl;

            cout << endl;

            ++it;

        }


    }

}


结语

希望list的实现详大家有所帮助,迎大佬留言或私信与我交流.

学海漫浩浩,我亦苦作舟!关注我,大家一起学,一起!

相关文章推荐

【C++】模 拟实现 vector

【C++】 库类 vector

【C++】模 拟实现 string

【C++】构建第一个C++ :Date

【C++】 的六大默 函数及其特性 (万字 )

【C++】什么是 ? 【C++】什么是 ?


​编辑​

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。