0
0

解密list的底层奥秘

在这里插入图片描述

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中)
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
金句分享:
✨即使人生还有无数次失望的可能性,✨
✨但我还是想活在理想主义的乌托邦里.✨

目录

本篇通过模拟实现

  1. list

的构造函数,迭代器,和部分成员函数以帮助大家更加深层的理解

  1. list

的原理,希望看完这篇文章使得友友们对

  1. list

有了更加深层的理解.

一、list底层框架

  1. list

的底层是一个带头双向循环链表.
在这里插入图片描述

(1) 节点类

因为

  1. list

中节点可能存储各种类型的值,所以这里使用了一个模板参数

  1. T

.

  1. list <int>
  1. list<doubel>

…

  1. // List的节点类template<classT>structlist_node{list_node(const T& val =T()):_val(val){}//这里的 T() 表示使用类型 T 的默认构造函数创建一个对象，//它将调用 T 类型的默认构造函数来初始化 val。如果类型 T 没有提供默认构造函数，那么代码将无法编译通过。
  2.         list_node<T>* _prev=nullptr;//指向前驱结点
  3.         list_node<T>* _next=nullptr;//指向后继结点
  4.         T _val;//存储数据};

(2) 迭代器类

很多小伙伴会疑问,为什么一个迭代器类却使用了三个模板参数,是不是有些多余呢?
在这里插入图片描述

其实不然,牛牛依次为大家解释.

  1. class T: 是结点类的存储不同数据所需要使用的模板参数.该模板参数表示要处理的元素的类型。它可以是任意类型，例如整数、浮点数、自定义类等等。在模板实例化时，需要提供一个具体的类型。
  2. Ref: 该模板参数表示指向元素类型 T 的引用。它定义了对元素的引用类型，在实例化模板时，将使用指定的引用类型来操作元素。
  3. Ptr: 该模板参数表示指向元素类型 T 的指针。它定义了指向元素的指针类型，在实例化模板时，将使用指定的指针类型来操作元素。
  1. template<class T, class Ref, class Ptr>

意味着

  1.  list_iterator<T, const T&, const T*>;
  1. list

的迭代器用来遍历链表中的元素,外部通过迭代器的

  1. ++

和

  1. --

进行链表的元素访问,这是一种封装,隐藏内部

  1. list

的实现细节,外部只能通过迭代器的方式访问.

  1. //迭代器类template<classT,classRef,classPtr>structlist_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> self;//self表示自己list_iterator(Node* node);//构造list_iterator(const self& list);//拷贝构造
  2.       Ref operator*();
  3.       Ptr operator->();//前置++
  4.       self&operator++();//后置++
  5.       self operator++(int);//前置--
  6.       self&operator--();//后置--
  7.       self&operator--(int);booloperator!=(const self& list)const;booloperator==(const self& list);//成员变量
  8.       Node* _node;};

(3) list类

  1. 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;list()//(无参构造)//n个value构造list(int n,const T& value =T());//迭代器区间构造template<classIterator>list(Iterator first, Iterator last);//拷贝构造list(const list<T>& list);//各种成员函数/...//析构函数~list();
  2.         iterator begin();       
  3.         iterator end();//常属性迭代器
  4.         const_iterator begin()const;
  5.         const_iterator end()const;private:
  6.         Node* _head;
  7.         size_t _size;};

二、构造函数

对于带头双向循环链表,它的初始化操作是必须的,因为必须创建一个头指针.
在这里插入图片描述
对于

  1. list

的构造函数,它是很多种方式的,例如:无参构造,

  1. n

个

  1. val

构造,迭代器区间构造等.
对于每个构造,必须前进行最初的初始化操作,为了避免代码冗余,我们将这个部分单独写成一个初始化操作的函数.

如下:

  1. voidInit_List(){
  2.     _head =new Node;//创建头指针
  3.     _head->_prev = _head;
  4.     _head->_next = _head;
  5.     _size =0;}

(1) 无参构造

调用

  1. Init_List();

初始化函数即可.

  1. list()//初始化很重要(无参构造){Init_List();}

(2) n个value构造

  1. 进行初始化操作.
  2. 尾插n个value.
  1. //n个value构造list(int n,const T& value =T()){Init_List();while(n--){push_back(value);}}

(3) 迭代器区间构造

  1. 进行初始化操作.
  2. 利用迭代器的特性,一次将区间中的数据尾插入链表.
  1. //迭代器区间构造template<classIterator>list(Iterator first, Iterator last){Init_List();while(first != last){push_back(*first);++first;}}

(4) 拷贝构造

链表在物理空间上是不连续的,所以,对于参数是另一个链表的拷贝构造,只能遍历链表进行依次插入数据.

  1. //拷贝构造list(const list<T>& list){Init_List();auto it = list.begin();while(_size!=list._size){push_back(*it);
  2.             it++;}}

三、迭代器

迭代器的实现

① 构造

迭代器本质就是一个 

  1. Node* _node;

结点类的指针.
对于迭代器的构造函数,只需要将结点的地址传过来即可.

  1. list_iterator(Node* node)//默认构造:_node(node){}list_iterator(const self& list)//拷贝构造:_node(list._node){}

②

  1. *

和

  1. ->

(1) 

  1. *
  1. *

运算符重载,表示对迭代器进行解引用.
使用场景:

  1. list<int>::iterator it = L1.begin();int start=*it;

很明显,

  1. *

运算符是需要获取结点所存储的数据.为了减少拷贝以及对数据进行修改,这里采用传引用(

  1. Ref

)返回.

  1.  Ref operator*(){return _node->_val;//获取该结点的数据}

(2) 

  1. ->

上面链表中的数据是简单的类型

  1. int

在这里插入图片描述

  1. Ptr operator->(){return&_node->_val;// 等价于 return &(_node->_val);}

③ 前置++与后置++

对于链表,迭代器++表示向后访问下一个(后继)结点.学过链表的友友们应该知道.
也就是 

  1. _node = _node->_next

;

前置++,返回++后的结点的迭代器
后置++,返回++前的结点的迭代器

  1. //前置++
  2.   self&operator++(){
  3.       _node = _node->_next;return*this;}//后置++
  4.   self operator++(int){
  5.       Node* tmp=_node;//保存++之前的值
  6.       _node = _node->_next;return tmp;//返回++之前的值}

④ 前置–与后置–

同理,返回当前结点迭代器的前驱结点.
也就是:

  1. _node = _node->_prev;

前置–,返回–后的结点的迭代器
后置–,返回–前的结点的迭代器

  1. //前置--
  2.  self&operator--(){
  3.      _node = _node->_prev;return*this;}//后置--
  4.  self&operator--(int){
  5.      Node* tmp = _node;//保存 -- 之前的值
  6.      _node = _node->_prev;return tmp;//返回 -- 之前的值}

⑤ 比较运算符

比较迭代器是否相等,实际就是比较迭代器所指向的结点是否相等.

  1. booloperator!=(const self& list)const{return _node != list._node;}booloperator==(const self& list){return _node == list._node;}

list类中的迭代器

在这里插入图片描述

  1. iterator begin()

: 返回第一个有效元素位置的迭代器

  1. iterator end()

: 返回最后一个有效元素位置的迭代器

  1. typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator;
  2.     iterator begin(){return _head->_next;//也可以强转一下//return iterator(_head->_next);}
  3.       
  4.     iterator end(){return _head;//也可以强转一下// return iterator(_head);}//常属性迭代器
  5.     const_iterator begin()const{return _head->_next;}
  6.     const_iterator end()const{return _head;}

front和back

在这里插入图片描述

  1.  T&front(){return _head->_next->_val;//返回值}const T&front()const{return _head->_next->_val;}
  2.  T&back(){return _head->_prev->_val;}const T&back()const{return _head->_prev->_val;}

四、Modifiers:

其实带头双向循环链表的增删改查较于单链表,更加简单,我们画图分析还是很容易实现的.

(1) insert()

在这里插入图片描述
(图片为博主原创,不得随意截图使用)

特殊情况:这是尾插:
在这里插入图片描述(图片为博主原创,不得随意截图使用)

代码示例

  1. // 在pos位置前插入值为val的节点
  2.  iterator insert(iterator pos,const T& val){//pos.node  而不是pos->node
  3.      Node* newnode =newNode(val);
  4.      Node* _prev_node = pos._node->_prev;//pos位置结点的 原前置 结点
  5.      Node* _cur_node = pos._node;//pos位置的结点
  7.      _prev_node->_next = newnode;
  8.      newnode->_prev = _prev_node;
  10.      _cur_node->_prev = newnode;
  11.      newnode->_next = _cur_node;++_size;//有效数据的个数+1.return newnode;}

(2) erase()

在这里插入图片描述

  1. // 删除pos位置的节点，返回该节点的下一个位置
  2.   iterator erase(iterator pos){
  3.       
  4.       Node* _prev_node = pos._node->_prev;//pos位置结点的 原前置(prev) 结点
  5.       Node* _next_node = pos._node->_next;//pos位置结点的 原后置(next) 结点
  7.       _next_node->_prev = _prev_node;
  8.       _prev_node->_next = _next_node;delete pos._node;--_size;return _next_node;}

(3) push_back() 和 push_front()

  1. //尾插//void push_back(const T& val)//{//    Node* newnode = new Node(val);//    Node* _tail_node = _head->_prev;      // 原尾结点//    _tail_node->_next = newnode;//    newnode->_prev = _tail_node;//    _head->_prev = newnode;//    newnode->_next = _head;//    //    ++_size;//有效数据的个数+1.//}//复用insert更加方便voidpush_back(const T& val){insert(end(),val);//在头结点前面插入,即为尾插}//头插voidpush_front(const T& val){insert(begin(), val);}

(4) pop_back() 和 pop_front()

复用即可,不过多介绍了.

  1. //尾删voidpop_back(){erase(--end());}//头删voidpop_front(){erase(begin());}

(5) clear()

  1. clear

:清除

  1. list

中的有效数据
遍历链表进行依次删除结点,并将size置为0.

  1. voidclear(){
  2.       iterator it =begin();while(it !=end()){
  3.           it =erase(it);}
  5.       _size =0;}

(6) swap()

交换两个链表的成员变量即可.

  1. voidswap(list<T>& list){swap(_head, list._head);swap(_size, list._size);}

结语

看完这篇文章,相信大家对list有了更加深层的理解,对于list的迭代器,它并不像前面的

  1. string

和

  1. vector

那种原生指针,而是封装成了类,使得链表的迭代器也可以执行

  1. ++

和

  1. --

等操作,因为迭代器类重载了这些运算符.

今天就分享到这里了,如果觉得有帮助的话,可以给牛牛来一个一键三连吗?谢谢支持!
在这里插入图片描述

标签： list 数据结构 stl
本文转载自: https://blog.csdn.net/qq_67276605/article/details/132439135
版权归原作者 初阶牛 所有， 如有侵权，请联系我们删除。
登录后发布评论

“解密list的底层奥秘”的评论:

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

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

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

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

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

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

Kafka学习笔记

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