当前位置: 首页 > news >正文

STL —— list

图片名称

博主首页: 有趣的中国人

专栏首页: C++专栏


    本篇文章主要讲解 list模拟实现的相关内容

    1. list简介


    列表(list)C++标准模板库(STL)中的一个容器,它是一个双向链表数据结构,用于存储元素。与vector不同,列表中的元素在内存中不是连续存储的,而是通过指针相互连接形成链表。这种设计使得列表对于插入和删除操作非常高效,但是在查找特定元素时相对较慢,因为需要按序遍历整个链表。


      2. list模拟实现

      2.1 list类的相关成员变量

      C++的标准库中,list的实现方式是带头双向循环链表,因此在类中,我们需要一个头指针_head。至于每个节点,我们也同样需要构造一个类,其中成员变量包含_prev_next和数据_val

      template<class T>
      struct ListNode
      {ListNode<T>* _prev;ListNode<T>* _next;T _val;ListNode(const T& x = T()):_prev(nullptr),_next(nullptr),_val(x){}
      };
      template<class T>
      class list
      {
      public:typedef ListNode<T> Node;list(){_head = new Node;_head->_prev = _head;_head->_next = _head;}
      private:Node* _head;
      };
      

        2.2 尾插

        尾插太简单了,直接上代码:

        void push_back(const T& x)
        {Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;
        }
        

          2.3 迭代器

          在库中,我们不管迭代器的底层是如何实现的,但是我们都要用相同的方法使用迭代器,例如之前讲过的 vectorstring,在g++中的实现方法就是原生指针,来实现例如++--等功能,但是这里list由于不是连续存储的,所以用原生指针正常的++--等功能并不能达到我们的预期,因此我们可以把迭代器搞成一个类类型,并用运算符重载来改变它的功能。

          下面的代码是迭代器正常的使用方法,我们需要用运算符重载来实现这些功能:
          void list_test1()
          {list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
          }
          

            2.3.1 迭代器类的成员变量

            迭代器类中其实就包含了一个指向结点类型的指针,因为我们的目的就是改变原生指针的相关操作,来实现迭代器相关的操作。
            代码如下:

            struct ListNodeIterator
            {typedef ListNode<T> Node;Node* _node;ListNodeIterator(Node* node):_node(node){}
            };
            

              2.3.2 迭代器类的实现

              template<class T>
              struct ListNodeIterator
              {typedef ListNode<T> Node;typedef ListNodeIterator<T> Self;Node* _node;ListNodeIterator(Node* node):_node(node){}T& operator*(){return _node->_val;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& it){return _node != it._node;}
              };
              

                2.3.3 insert 和 erase

                inserterase传的参数就是iterator,模拟实现代码如下:

                void insert(iterator pos, const T& x)
                {Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;
                }
                void erase(iterator pos)
                {Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;
                }
                
                这里需要注意,在erase的时候由于迭代器指向的空间被释放了,会导致迭代器失效的问题,之前的文章讲过相关的内容,因此我们需要更新iterator,指向被删除的位置的下一个位置即可,代码如下:
                iterator erase(iterator pos)
                {Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;return next;
                }
                

                  2.3.4 begin 和 end

                  beginend是在迭代器中的成员函数,返回头和尾的迭代器即可:

                  typedef ListNodeIterator<T> iterator;
                  iterator begin()
                  {return iterator(_head->_next);// 单参数类型的构造函数支持隐式类型转换,以下依法也可以:// return _head->_next;
                  }
                  iterator end()
                  {return iterator(_head);// return _head;
                  }
                  

                    2.3.5 insert 和 erase的复用

                    push_backpush_frontpop_backpop_front都可以复用inserterase,代码如下:

                    void push_back(const T& x)
                    {/*Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);
                    }
                    void pop_back()
                    {erase(--end());
                    }
                    void push_front(const T& x)
                    {insert(begin(), x);
                    }
                    void pop_front()
                    {erase(begin());
                    }
                    

                    测试代码:

                    void list_test1()
                    {list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;lt.pop_back();lt.pop_back();it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;lt.push_front(100);lt.push_front(200);lt.push_front(300);it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;lt.pop_front();lt.pop_front();it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
                    }
                    

                    在这里插入图片描述


                      2.3.5 operator->的重载

                      • 先看一下这段代码:
                      void list_test2()
                      {struct A{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}};list<A> lt;A a(1, 2);lt.push_back(a);lt.push_back(A(3, 4));lt.push_back({ 5,6 });list<A>::iterator it = lt.begin();while (it != lt.end()){// 主要看这里cout << (*it)._a1 << " " << (*it)._a2 << " ";cout << endl;++it;}
                      }
                      

                      我们注意到当我们访问自定义类型的数据需要这样:(*it)._a1进行访问,但是迭代器就是为了模仿指针的相关操作,例如我们有A*这种类型的指针如何进行访问A中的数据呢?

                      A* aa;
                      (*aa)._a1;
                      // 上面的方法很别扭,我们正常用指针都是用->访问的,所以我们如何实现->的重载呢?
                      aa->_a1;
                      
                      • 实现方法如下:
                      T* operator->()
                      {return &_node->_val;
                      }
                      

                      为什么这样就行了呢,我们知道自定义类型存储在了节点的_val中,这里返回了_val的地址,如果按照正常的思路进行访问,应该按照如下的方式:

                      • cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << " ";

                      所以应该有两个箭头:第一个箭头代表运算符的重载,第二个代表指针解引用访问数据:

                      • cout << it->->_a1 << " " << it->->_a2 << " ";

                      但是编译器进行了简化,两个箭头变成了一个箭头

                      • cout << it->_a1 << " " << it->_a2 << " ";

                      `

                      void list_test2()
                      {struct A{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}};/*A* aa;(*aa)._a1;aa->_a1;*/list<A> lt;A a(1, 2);lt.push_back(a);lt.push_back(A(3, 4));lt.push_back({ 5,6 });list<A>::iterator it = lt.begin();while (it != lt.end()){cout << (*it)._a1 << " " << (*it)._a2 << " ";cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << " ";//cout << it->->_a1 << " " << it->->_a2 << " ";cout << it->_a1 << " " << it->_a2 << " ";cout << endl;++it;}
                      }
                      

                      在这里插入图片描述


                        2.4 const迭代器

                        • 我们先看以下这段代码:
                        void Print(const list<int>& lt)
                        {list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
                        }void list_test3()
                        {list<int> lt;lt.push_back(1);lt.push_back(1);lt.push_back(8);lt.push_back(6);lt.push_back(0);Print(lt);
                        }
                        
                        • 很明显,会报错,提示不能从const转换为非const

                        在这里插入图片描述

                        • 很多人可能会想着在beginend后加上const进行修饰,但其实也不行,这样虽然传入的值是const类型,但是返回的值不是const类型,就会导致返回的值能被修改,但是要求是返回的值是const类型,所以这种想法是不行的,下面是错误的示范:
                        iterator begin() const
                        {return iterator(_head->_next);// 单参数类型的构造函数支持隐式类型转换,以下写法也可以:// return _head->_next;
                        }
                        iterator end() const
                        {return iterator(_head);// return _head;
                        }
                        void Print(const list<int>& lt)
                        {list<int>::iterator it = lt.begin();while (it != lt.end()){// 这里可以修改*it += 10;cout << *it << " ";++it;}cout << endl;
                        }void list_test3()
                        {list<int> lt;lt.push_back(1);lt.push_back(1);lt.push_back(8);lt.push_back(6);lt.push_back(0);Print(lt);
                        }
                        

                        在这里插入图片描述

                        • 那应该如何解决呢?在此之前,我们需要了解一下这段代码:
                        const iterator begin() 
                        {return iterator(_head->_next);// 单参数类型的构造函数支持隐式类型转换,以下写法也可以:// return _head->_next;
                        }
                        const iterator end() 
                        {return iterator(_head);// return _head;
                        }
                        
                        • 当我们在返回值前加上const,代表返回的迭代器不能被修改,例如不能进行++it
                        • 但是我们是想着迭代器指向的内容不能被修改,因此这种方法是不可行的。
                        • 可以类比一下这段代码:
                        // const修饰的是解引用之后的内容
                        const int* a;
                        // const修饰的是指针本身
                        int* const a;
                        
                        • 解决方法其实很简单,之前说过既然不满足要求,那我们就自己造轮子,自己写一个类;
                        • 这个类其实也很简单,就把ListNodeIterator这个类中的两个运算符重载函数的返回值改变一下就可以了,一个是,另一个是->
                        template<class T>
                        struct ListNodeConstIterator
                        {typedef ListNode<T> Node;typedef ListNodeConstIterator<T> Self;Node* _node;ListNodeConstIterator(Node* node):_node(node){}const T& operator*(){return _node->_val;}const T* operator->(){return &_node->_val;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& it){return _node != it._node;}
                        };
                        

                        list类中加入这两个函数:

                        const_iterator begin() const
                        {return const_iterator(_head->_next);// 单参数类型的构造函数支持隐式类型转换,以下写法也可以:// return _head->_next;
                        }const_iterator end() const
                        {return const_iterator(_head);// return _head;
                        }
                        
                        • 这时候就不能修改了

                        在这里插入图片描述
                        在这里插入图片描述


                          2.5 模板的作用

                          我们发现,在两个迭代器中,只用两个函数的返回值不同,其他的全部都一样,看上去非常冗余,那我们可不可以用一种方法来解决这种冗余呢?肯定是可以的,我们这个时候就可以用到模板:

                          template<class T, class Ref, class Ptr>
                          struct ListNodeIterator
                          {typedef ListNode<T> Node;typedef ListNodeIterator<T, Ref, Ptr> Self;Node* _node;ListNodeIterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& it){return _node != it._node;}
                          };
                          template<class T>
                          class list
                          {
                          public:typedef ListNode<T> Node;typedef ListNodeIterator<T, T&, T*> iterator;typedef ListNodeIterator<T,const T&, const T*> const_iterator;iterator begin() {return iterator(_head->_next);// 单参数类型的构造函数支持隐式类型转换,以下写法也可以:// return _head->_next;}iterator end() {return iterator(_head);// return _head;}const_iterator begin() const{return const_iterator(_head->_next);// 单参数类型的构造函数支持隐式类型转换,以下写法也可以:// return _head->_next;}const_iterator end() const{return const_iterator(_head);// return _head;}// ......
                          };
                          

                          这里虽然只写了一份iterator类,但是在编译的时候,编译器会根据你的需要生成两份iterator类,所以模板很强大。


                            3. 拷贝构造、赋值重载、析构

                            3.1 析构函数

                            • 析构函数释放掉空间即可,记住更新一下迭代器。
                            void clear()
                            {iterator it = begin();while (it != end()){it = erase(it);}
                            }~list()
                            {clear();delete _head;_head = nullptr;
                            }
                            

                            3.2 拷贝构造

                            • 拷贝构造新建一个头节点,然后尾插。
                            void empty_init()
                            {_head = new Node;_head->_prev = _head;_head->_next = _head;
                            }list(const list<T>& lt)
                            {empty_init();for (auto& e : lt){push_back(e);}
                            }
                            

                            3.3 赋值重载

                            • 赋值重载现代写法,之前讲过类似的方法:
                            void swap(list<T>& lt)
                            {std::swap(_head, lt._head);
                            }list<int>& operator=(list<T> lt)
                            {swap(lt);return *this;
                            }
                            
                            http://www.lryc.cn/news/333112.html

                            相关文章:

                          1. 申请SSL证书
                          2. 深入浅出 -- 系统架构之负载均衡Nginx环境搭建
                          3. notepad++绿色版添加右键菜单
                          4. 7 个 iMessage 恢复应用程序/软件可轻松恢复文本
                          5. DockerFile启动jar程序
                          6. 基于R、Python的Copula变量相关性分析及AI大模型应用
                          7. 鸿蒙组件学习_Tabs组件
                          8. 【LangChain学习之旅】—(19)BabyAGI:根据气候变化自动制定鲜花存储策略
                          9. thinkphp6入门(21)-- 如何删除图片、文件
                          10. 虚拟内存知识详解
                          11. 数据结构初阶:顺序表和链表
                          12. 在flutter中添加video_player【视频播放插件】
                          13. golang微服务框架特性分析及选型
                          14. 苹果cmsV10 MXProV4.5自适应PC手机影视站主题模板苹果cms模板mxone pro
                          15. GPU的了解
                          16. 鸿蒙实战开发-如何使用Stage模型卡片
                          17. 蓝桥杯刷题 前缀和与差分-[2128]重新排序(C++)
                          18. STM32重要参考资料
                          19. [StartingPoint][Tier0]Preignition
                          20. 数据库系统概论(超详解!!!)第三节 关系数据库标准语言SQL(Ⅴ)
                          21. SpringBoot | Spring Boot“整合Redis“
                          22. SV学习笔记(四)
                          23. Midjourney艺术家分享|By Moebius
                          24. Vue - 1( 13000 字 Vue 入门级教程)
                          25. Vue关键知识点
                          26. Prometheus+grafana环境搭建redis(docker+二进制两种方式安装)(四)
                          27. 宝塔面板安装nginx流媒体服务器(http-flv)
                          28. LNMP环境:揭秘负载均衡与高可用性设计
                          29. 深入理解Java异常处理机制(day20)
                          30. Docker实战教程 第1章 Linux快速入门