0
0

【C++】list底层的模拟实现

在这里插入图片描述
个人主页

在这里插入图片描述

文章目录

🎄一、前言

list是一个双向链表的容器，它可以在其内部中存储各种类型的元素，并且支持动态地添加、删除和修改元素。

🏠二、基本框架

list可以分为三部分：一个是list节点类，一个是迭代器类，还有一个是list类本身。
它们三个类底层的成员变量又分别代表不同的功能。
其中list节点类封装了list的元素以及前后指针，且完成了节点的初始化。
迭代器类封装了指向节点的指针，还负责重载++、–等运算符。
list类本身负责初始化以及负责插入和删除等功能。

🎡三、list节点类的实现

链表中数据以及前后指针的类型都是由模板自动生成的，可以为内置类型或自定义类型。

  1. template<classT>structlist_node{
  2.     T _data;
  3.     list_node<T>* _next;
  4.     list_node<T>* _prev;//构造list_node(const T& data =T()):_data(data),_next(nullptr),_prev(nullptr){};};

🎉四、list迭代器类

因为迭代器涉及普通迭代器和const迭代器，因此我们可以使用模板，在模板里面设置三个不同的类型，分别为节点的数据类型、引用类型和指针类型。

  1. template<classT,classRef,classPtr>structlist_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;//用来访问Node类型的成员变量
  2.     Node* _node;};

迭代器的默认构造函数因为支持基本的隐式类型转换，因此实现起来也很简单。

  1. list_iterator(Node* node):_node(node){}

1.Ref operator*()

负责重载迭代器的解引用，直接返回当前该迭代器指向的节点数据即可。

  1. Ref operator*(){return _node->_data;}

2.Ptr operator->()

由于我们想把迭代器当成指针使用，因此重载->是必要的，其返回值为节点元素的地址。为什么是返回地址呢？这是因为在使用迭代器->时，编译器会自动优化成->->。

  1. Ptr operator->(){return&_node->_data;}

3.Self& operator++()前置和Self& operator–()前置

直接让节点指向下一个和前一个即可。

  1. //前置++
  2. Self&operator++(){
  3.     _node = _node->_next;return*this;}//前置--
  4. Self&operator--(){
  5.     _node = _node->_prev;return*this;}

4.Self operator++(int)后置和Self operator–(int)后置

我们只需把当前迭代器实例化的对象拷贝给一个新的迭代器对象tmp，然后把当前的数据进行处理，最后将tmp进行返回即可。

  1. //后置++
  2. Self operator++(int){
  3.     Self tmp(*this);
  4.     _node = _node->_next;return tmp;}//后置--
  5. Self&operator--(int){
  6.     Self tmp(*this);
  7.     _node = _node->_prev;return tmp;}

5.bool operator!=(const Self& s) const和bool operator==(const Self& s) const

判断节点是否相等不能只判断值是否相等，因为不同的节点可以存放相同的值，因此需要比较其节点是否相等即可。

  1. booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}

⭐五、list类

1.初始化

初始化只需初始化头结点即可。

  1. //无参初始化list(){//通过调用这一函数来创建头节点empty_init();}//空初始化voidempty_init(){
  2.     _head =new Node;
  3.     _head->_next = _head;
  4.     _head->_prev = _head;
  5.     _size =0;}

2.构造函数

当链表为空时，_head节点的头和尾都指向它自己，因此在后续有节点插入时，只需改变一下prev和next指向的位置即可。

  1. list(){
  2.     _head =newNode<T>();
  3.     _head->next = _head;
  4.     _head->prev = _head;}

4.析构函数和clear函数

析构函数是用来释放节点空间的，因此需要先定义一个clear函数用来释放所有的有效节点，确保没有有效节点后再把哨兵位的_head进行删除，然后将_head置为空。

  1. //析构~list(){clear();delete _head;
  2.     _head =nullptr;}voidclear(){auto it =begin();while(it !=end()){
  3.         it =erase(it);}}

5.深拷贝

先对其进行空初始化操作，然后用迭代器依次对其进行访问然后插入即可。

  1. //深拷贝list(const list<T>& lt){empty_init();for(auto& e : lt){push_back(e);}}

6.深赋值

我们可以调用swap函数将两者数据进行交换即可。

  1. //深赋值voidswap(list<int>& lt){
  2.     std::swap(_head, lt._head);
  3.     std::swap(_size, lt._size);}
  5. list<T>&operator=(list<T> lt){swap(lt);return*this;}

7.头插和头删函数

头插函数就是每次在begin位置之前进行插入，因为begin是第一个有效的元素；而头删就是每次在begin位置进行删除。

  1. voidpush_front(const T& x){Insert(begin(), x);}voidpop_front(){erase(--begin());

8.尾插和尾删函数

尾插就是每次在end()位置进行插入，因为end是最后一个有效的元素；而尾删则是在end()的位置上进行删除。
由于我们实现了insert函数，因此就可以调用insert函数在其尾部插入数据即可。

  1. voidpush_back(const T& x){Insert(end(), x);++_size;}voidpop_back(){erase(--end());}

9.insert和erase函数

insert函数就是在pos位置插入值。

  1. iterator Insert(iterator pos,const T& x){//取到pos位置的节点
  2.     Node* cur = pos._node;//保留之前的节点
  3.     Node* prev = cur->_prev;//创建新节点
  4.     Node* newnode =newNode(x);//改变指向，最后更新一下_size
  5.     newnode->_next = cur;
  6.     cur->_prev = newnode;
  7.     newnode->_prev = prev;
  8.     prev->_next = newnode;++_size;return newnode;}

erase函数首先要进行断言，防止删除哨兵位。然后将pos位置节点的前和后进行连接，最后删除pos位置的节点，更新一下_size的大小。

  1. iterator erase(iterator pos){assert(pos !=end());
  2.     Node* prev = pos._node->_prev;
  3.     Node* next = pos._node->_next;
  4.     prev->_next = next;
  5.     next->_prev = prev;delete pos._node;--_size;return next;}

10.迭代器的实现（普通和const)

由于存在普通成员变量和const成员变量的调用，因此需要实现两个迭代器。
begin迭代器是返回第一个有效位置，由于哨兵位_head并没有数据，因此返回哨兵位的下一个位置。end迭代器是返回最后一个元素的下一个位置，而这个位置是无效的，双向链表无效的位置就只有哨兵位这一个位置，因此返回哨兵位即可。

  1. iterator begin(){return _head->_next;}
  3. iterator end(){return _head;}//const迭代器
  4. const_iterator begin()const{return _head->_next;}
  6. const_iterator end()const{return _head;}

11.判空

直接判断_size是否为空即可。

  1. //判空boolempty()const{return _size ==0;}

12.size()函数

直接返回_size即可。

  1. size_t size()const{return _size;}

🚀六、vector和list函数的区别

首先，vector是一个动态数组，在插入和删除数据的时候会挪动后面的元素，这就有可能会导致迭代器失效；而list则为链表，它可以在任意位置进行插入和删除，因此迭代器的稳定性就更高。

其次，vector的迭代器通常为随机访问迭代器，允许向前向后访问元素，而list迭代器可能为双向迭代器，只能向前或向后移动。

最后，vector的随机访问速度快，因此在查找元素时的效率高，但如果频繁的插入或者删除元素时，list通常会更快，因为它不需要移动大量的元素。

🏝️七、源代码

  1. #include<iostream>#include<assert.h>#include<list>usingnamespace std;namespace bit
  2. {template<classT>structlist_node{
  3.         T _data;
  4.         list_node<T>* _next;
  5.         list_node<T>* _prev;//构造list_node(const T& data =T()):_data(data),_next(nullptr),_prev(nullptr){};};//const迭代器template<classT,classRef,classPtr>structlist_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;
  6.         Node* _node;list_iterator(Node* node):_node(node){}
  8.         Ref operator*(){return _node->_data;}
  10.         Ptr operator->(){return&_node->_data;}//前置++
  11.         Self&operator++(){
  12.             _node = _node->_next;return*this;}//后置++
  13.         Self operator++(int){
  14.             Self tmp(*this);
  15.             _node = _node->_next;return tmp;}//前置--
  16.         Self&operator--(){
  17.             _node = _node->_prev;return*this;}//后置--
  18.         Self&operator--(int){
  19.             Self tmp(*this);
  20.             _node = _node->_prev;return tmp;}booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};template<classT>classlist{typedef list_node<T> Node;public:typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator;
  22.         iterator begin(){return _head->_next;}
  24.         iterator end(){return _head;}//const迭代器
  25.         const_iterator begin()const{return _head->_next;}
  27.         const_iterator end()const{return _head;}//空初始化voidempty_init(){
  28.             _head =new Node;
  29.             _head->_next = _head;
  30.             _head->_prev = _head;
  31.             _size =0;}//无参初始化list(){empty_init();}//析构~list(){clear();delete _head;
  32.             _head =nullptr;}voidclear(){auto it =begin();while(it !=end()){
  33.                 it =erase(it);}}//深拷贝list(const list<T>& lt){empty_init();for(auto& e : lt){push_back(e);}}//深赋值voidswap(list<int>& lt){
  34.             std::swap(_head, lt._head);
  35.             std::swap(_size, lt._size);}
  37.         list<T>&operator=(list<T> lt){swap(lt);return*this;}
  39.         size_t size()const{return _size;}voidpush_back(const T& x){Insert(end(), x);++_size;}
  41.         iterator Insert(iterator pos,const T& x){
  42.             Node* cur = pos._node;
  43.             Node* prev = cur->_prev;
  44.             Node* newnode =newNode(x);
  45.             newnode->_next = cur;
  46.             cur->_prev = newnode;
  47.             newnode->_prev = prev;
  48.             prev->_next = newnode;++_size;return newnode;}voidpop_back(){erase(--end());}voidpop_front(){erase(--begin());}
  50.         iterator erase(iterator pos){assert(pos !=end());
  51.             Node* prev = pos._node->_prev;
  52.             Node* next = pos._node->_next;
  53.             prev->_next = next;
  54.             next->_prev = prev;delete pos._node;--_size;return next;}voidpush_front(const T& x){Insert(begin(), x);}//判空boolempty()const{return _size ==0;}private:
  55.         Node* _head;
  56.         size_t _size;};}
标签： c++ list windows
本文转载自: https://blog.csdn.net/2301_81044829/article/details/141899367
版权归原作者 夜晚中的人海 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【C++】list底层的模拟实现”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？