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);}
  4. 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;}
  2. iterator end(){return _head;}//const迭代器
  3. const_iterator begin()const{return _head->_next;}
  4. 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){}
  7. Ref operator*(){return _node->_data;}
  8. Ptr operator->(){return&_node->_data;}//前置++
  9. Self&operator++(){
  10. _node = _node->_next;return*this;}//后置++
  11. Self operator++(int){
  12. Self tmp(*this);
  13. _node = _node->_next;return tmp;}//前置--
  14. Self&operator--(){
  15. _node = _node->_prev;return*this;}//后置--
  16. Self&operator--(int){
  17. Self tmp(*this);
  18. _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;
  19. iterator begin(){return _head->_next;}
  20. iterator end(){return _head;}//const迭代器
  21. const_iterator begin()const{return _head->_next;}
  22. const_iterator end()const{return _head;}//空初始化voidempty_init(){
  23. _head =new Node;
  24. _head->_next = _head;
  25. _head->_prev = _head;
  26. _size =0;}//无参初始化list(){empty_init();}//析构~list(){clear();delete _head;
  27. _head =nullptr;}voidclear(){auto it =begin();while(it !=end()){
  28. it =erase(it);}}//深拷贝list(const list<T>& lt){empty_init();for(auto& e : lt){push_back(e);}}//深赋值voidswap(list<int>& lt){
  29. std::swap(_head, lt._head);
  30. std::swap(_size, lt._size);}
  31. list<T>&operator=(list<T> lt){swap(lt);return*this;}
  32. size_t size()const{return _size;}voidpush_back(const T& x){Insert(end(), x);++_size;}
  33. iterator Insert(iterator pos,const T& x){
  34. Node* cur = pos._node;
  35. Node* prev = cur->_prev;
  36. Node* newnode =newNode(x);
  37. newnode->_next = cur;
  38. cur->_prev = newnode;
  39. newnode->_prev = prev;
  40. prev->_next = newnode;++_size;return newnode;}voidpop_back(){erase(--end());}voidpop_front(){erase(--begin());}
  41. iterator erase(iterator pos){assert(pos !=end());
  42. Node* prev = pos._node->_prev;
  43. Node* next = pos._node->_next;
  44. prev->_next = next;
  45. next->_prev = prev;delete pos._node;--_size;return next;}voidpush_front(const T& x){Insert(begin(), x);}//判空boolempty()const{return _size ==0;}private:
  46. Node* _head;
  47. size_t _size;};}
标签: c++ list windows

本文转载自: https://blog.csdn.net/2301_81044829/article/details/141899367
版权归原作者 夜晚中的人海 所有, 如有侵权,请联系我们删除。

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

还没有评论