C++：模拟实现list

前言：

        上篇文章简单介绍了list的接口使用，那么这篇文章将通过模拟实现list以及常用接口来更好的去理解list类,观看本章前将默认读者对链表的数据结构有初步的了解。

        list在库里是一个带哨兵位的双向循环的链表结构，并且list是一个类模板并不是一个指定的类型，所以在模拟实现时需要写成模板。

list的成员变量：

  

        这里仅仅只是介绍关于list里的成员变量，对于其他出现的东西请先不要去深究，之后会有相关介绍。

        那么如上图所见，在list的成员变量里，有一个 list_node(单节点) 的类模板，它的成员变量分别是，存放的数据(val)，上一个节点的指针(prev)，以及下一个节点的指针(next)。

        在list类模板里只有两个成员变量,一个是头节点的指针(_head)，这里是将list_node<T>这个类型typedef为Node,只是为了更好写。以及一个存放节点数量的数据(_size)。

list_node的成员函数

                

        list_node的成员函数只有一个构造函数，这个构造函数传的参数是一个T类型的数值，至于为什么不是0，是因为0是数值数据类型，而list不一定就是int类，有可能是char，double，甚至自定义类型，所以这边传的是一个T()类型(匿名对象),将T()赋值给val，再将val赋值给成员变量(_val)，并将其他的两个指针都指向nullptr。

list的成员函数

        1.emptyInit()

        

       public下方的两个是typedef的迭代器(iterator)类模板暂且先不管

        emptyInit()函数：

                是负责对头节点(哨兵位)进行的初始化，即new一个节点，并将val初始化，同时将_next与_prev指针都指向自己。同时将_size初始化为0。

        2.list() 与 list( const list<T> &lt )

              

        list():

                用于默认构造，直接申请一个头节点。

        list( const list<T> &lt )：

                用于拷贝构造，申请一个头节点后，通过范围for进行单个单个节点的插入,这个要先实现迭代器所以先不着急实现。

        3.~list()

        ~list()：

                析构函数，先通过clear()函数清除头节点外的所有节点(下面会实现),接着释放头节点并赋值为nullptr，再将_size赋值为0。

        4. void push_back( )

        void push_back( ):

                就是正常的双向链表的尾插，获取一个新节点，并更新尾节点，最后将头尾进行链接操作。

        5.iterator begin( )与 iterator end( )

        这里先简单理解list的iterator迭代器为一个结点指针

        iterator begin：返回的是头节点的下一个节点，及第一个有效数据的节点位置。

        iterator end：返回的是头节点。

        6.const iterator begin( ) const与 const iterator end( ) const

        const iterator begin( ) const函数：返回的是const list类型对象的头节点的下一个节点,因为const类型对象不能使用普通的迭代器，否则会造成权限放大导致程序崩溃。

         const与 const iterator end( ) const函数:返回的是const list类型对象的头节点。

        7.iterator insert(iterator pos, const T& val)

        

        iterator insert(iterator pos, const T& val)函数:就是在list的第pos个位置及第pos个节点位置前插入一个新节点。

        8.iterator erase(iterator pos)

        iterator erase(iterator pos)函数：

                删除pos位置的节点，先通过assert断言pos是否在一个正常的位置，接着重新链接pos的_prev节点与pos的_next节点。并释放pos节点，返回next节点的迭代器为了防止内部迭代器失效。

        9.size_t size()

        

        

        10.void clear()

        void clear()函数:

                创建一个list的 iterator 的 it 指针并指向list的begin位置，接着使用while循环，复用erase函数，循环删除list的有效节点，当it指针指向头节点及end位置时候就退出，保留头节点。

list的迭代器(iterator)

        首先我们要知道list的迭代器并不是普通原生的指针类型，因为list链表是各个不一样地址的空间通过指针进行链接起来的。并不像vector，string一样是一段连续的物理空间。如果仅仅只是将list迭代器++，是在单个节点的迭代器上++，并不会到达下一个节点的位置，而是变成一个野指针。

        所以，通过将迭代器进行封装为一个类模板，接着再在类模板里自己通过operator++等运算符重载来自己控制++等操作，就能解决这个这个问题。

       

 _list_iterator的成员变量：

        

        list的迭代器里面存放的不可能是一个节点，而是节点的指针,通过operator 运算符重载使得节点指针能够走向下一个或上一个节点，甚至解引用取得节点里的val。

        上图创建了一个 _list_iterator的类模板，在list的类模板了将_list_iterator类模板定义为iterator。

        接着迭代器的类里再次typedef list_node<T>为Node，_list_iterator<T,Ref,Por>为self(自己)。typed仅仅只是为了更方便以及更好读，并没有其他层次的意义。

        

        _list_iterator(Node*node )

           

                _list_iterator(Node*node )函数：

                        通过外面传入的node（节点指针）赋值给自身的_node。

        Ref operator*( )         

                

           

        Ref operator*()函数:

               通过对迭代器的理解 operator* 是将指针解引用，并返回指向的val的引用。

                所以返回类型Ref 就是 T&。

        

        self&operator++( )

        self&operator++()函数：

                根据自身理解，迭代器++会指向下一个位置，那么对于list节点++，会指向下一个节点。

                所以 _node = _node->_next; 将自身的下一个节点赋值给自身，这样_node就指向下一个节点位置，而迭代器的返回类型还是迭代器自身 self （_list_iterator<T,Ref,Por>）。

        self operator++(int)

               self operator++(int)函数：

                         self&operator++()是前置++，self operator++(int)是后置++。

                         所以需要创建一个新的迭代器对象temp并初始化temp自身的_node为*this的_node。在将this的_node指向自身的下一个位置。

        self& operator--()与self& operator--(int)

        

        Por operator->()

                   Por operator->()函数：

                        返回的是_val值的地址，因为_val不一定是内置类型，也有可能是自定义类型，而自定义类型的_val是类型的对象，需要再次解引用才能得到_val里的值。所以返回的是_val的地址，那么 Por =T*。

        

        bool operator!=(const  self& it)const与bool operator ==(const  self& it)const

        

                        operator!=比较的是两个对象，所以，这里比较的是两个迭代器类型对象的成员变量_node是否指向同一块地址空间。

        list迭代器小结：

        由于list是不连续的空间，不能使用内置的--++操作。所以我们通过封装迭代器类型，让让我们自身去控制迭代器的++与--等。由于迭代器的通用性，使得我们在上层的使用中，并不会觉得迭代器++以及--是一个复杂的操作 和普通的内置++--看起来并无差别，这就是封装带来的好处。

模拟实现list完整代码

        

#pragma once
#include<iostream>
#include<stdbool.h>
#include<assert.h>
using namespace std;namespace mabo
{template<class T>struct list_node{list_node(T val=T()):_next(nullptr),_prev(nullptr),_val(val){}T _val;list_node* _next;list_node* _prev;};template<class T, class Ref,class Por>struct _list_iterator{typedef list_node<T> Node;typedef _list_iterator<T,Ref,Por> self;_list_iterator(Node*node ):_node(node){}Ref operator*(){return _node->_val;}self&operator++(){_node = _node->_next;return *this;}self operator++(int){self temp(*this);_node = _node->_next;return temp;}self& operator--(){_node = _node->_prev;return *this;}self& operator--(int){self temp(*this);_node = _node->_prev;return *this;}Por operator->(){return  &_node->_val;}bool operator!=(const  self& it)const{return _node != it._node;}bool operator ==(const  self& it)const{return _node == it._node;}Node* _node;};template<class T>class list{typedef list_node<T> Node;public:typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T,const T&,const T*> const_iterator;void emptyInit(){_head = new Node(T());_head->_next = _head->_prev = _head;_size = 0;}list(){emptyInit();}list(const list<T>&lt){emptyInit();for (auto& e:lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;_size = 0;}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>&operator=(list<T> lt){swap(lt);return *this;}void push_back(const T&val){Node* newnode = new Node(val);Node* tail = _head->_prev;newnode->_next = _head;newnode->_prev = tail;tail->_next = newnode;_head->_prev = newnode;}void push_front(const T& val){insert(begin(), val);}iterator begin(){return _head->_next;}iterator end(){return _head;}const iterator begin() const{return _head->_next;}const iterator end() const{return _head;}iterator insert(iterator pos, const T& val){Node* newnode = new Node(val);newnode->_next = pos._node;newnode->_prev = pos._node->_prev;pos._node->_prev->_next = newnode;pos._node->_prev = newnode;_size++;return newnode; }iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return next;}size_t size(){return _size;}void clear(){iterator it = begin();while (it!=end()){it=erase(it);}_size = 0;}private:Node* _head;size_t _size;};struct A{A(int a1 = 1, int a2 = 2):_a1(a1), _a2(a2){}int _a1;int _a2;};}

        

模拟实现list测试用例

#include"2024_8_26.h"
using namespace mabo;void test01()
{mabo::list<int> li;li.push_back(1);li.push_back(2);li.push_back(3);li.push_back(4);mabo::list<int>::iterator it = li.begin();while (it!=li.end()){cout << (*it) << " ";++it;}cout << endl;for (auto e:li){cout << e << " ";}cout << endl;
}
void test02()
{list<A> li;li.push_back(A(1, 2));li.push_back(A(3, 4));mabo::list<A>::iterator it = li.begin();while (it != li.end()){cout <<it->_a1 << " "<< it->_a2<<endl;++it;}cout << endl;}void test03()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_front(5);lt.push_front(6);lt.push_front(7);lt.push_front(8);for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();list<int> lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt = lt1;for (auto e : lt){cout << e << " ";}cout << endl;}void test04()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;list<int> lt1 = lt;for (auto e : lt1){cout << e << " ";}cout << endl;
}void test05()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int> lt1;lt1.push_back(5);lt1.push_back(6);lt1.push_back(7);lt1.push_back(8);lt = lt1;for (auto e : lt){cout << e << " ";}cout << endl;}