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

个人主页

文章目录

🎄一、前言

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

🏠二、基本框架

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

🎡三、list节点类的实现

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

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

🎉四、list迭代器类

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

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

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

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

1.Ref operator*()

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

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

2.Ptr operator->()

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

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

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

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

//前置++
Self&operator++(){
    _node = _node->_next;return*this;}//前置--
Self&operator--(){
    _node = _node->_prev;return*this;}

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

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

//后置++
Self operator++(int){
    Self tmp(*this);
    _node = _node->_next;return tmp;}//后置--
Self&operator--(int){
    Self tmp(*this);
    _node = _node->_prev;return tmp;}

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

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

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

⭐五、list类

1.初始化

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

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

2.构造函数

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

list(){
    _head =newNode<T>();
    _head->next = _head;
    _head->prev = _head;}

4.析构函数和clear函数

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

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

5.深拷贝

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

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

6.深赋值

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

//深赋值voidswap(list<int>& lt){
    std::swap(_head, lt._head);
    std::swap(_size, lt._size);}

list<T>&operator=(list<T> lt){swap(lt);return*this;}

7.头插和头删函数

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

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

8.尾插和尾删函数

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

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

9.insert和erase函数

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

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

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

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

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

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

iterator begin(){return _head->_next;}

iterator end(){return _head;}//const迭代器
const_iterator begin()const{return _head->_next;}

const_iterator end()const{return _head;}

11.判空

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

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

12.size()函数

直接返回_size即可。

size_t size()const{return _size;}

🚀六、vector和list函数的区别

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

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

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

🏝️七、源代码

#include<iostream>#include<assert.h>#include<list>usingnamespace std;namespace bit
{template<classT>structlist_node{
        T _data;
        list_node<T>* _next;
        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;
        Node* _node;list_iterator(Node* node):_node(node){}

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

        Ptr operator->(){return&_node->_data;}//前置++
        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;}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;

        iterator begin(){return _head->_next;}

        iterator end(){return _head;}//const迭代器
        const_iterator begin()const{return _head->_next;}

        const_iterator end()const{return _head;}//空初始化voidempty_init(){
            _head =new Node;
            _head->_next = _head;
            _head->_prev = _head;
            _size =0;}//无参初始化list(){empty_init();}//析构~list(){clear();delete _head;
            _head =nullptr;}voidclear(){auto it =begin();while(it !=end()){
                it =erase(it);}}//深拷贝list(const list<T>& lt){empty_init();for(auto& e : lt){push_back(e);}}//深赋值voidswap(list<int>& lt){
            std::swap(_head, lt._head);
            std::swap(_size, lt._size);}

        list<T>&operator=(list<T> lt){swap(lt);return*this;}

        size_t size()const{return _size;}voidpush_back(const T& x){Insert(end(), x);++_size;}

        iterator Insert(iterator pos,const T& x){
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode =newNode(x);
            newnode->_next = cur;
            cur->_prev = newnode;
            newnode->_prev = prev;
            prev->_next = newnode;++_size;return newnode;}voidpop_back(){erase(--end());}voidpop_front(){erase(--begin());}

        iterator erase(iterator pos){assert(pos !=end());
            Node* prev = pos._node->_prev;
            Node* next = pos._node->_next;
            prev->_next = next;
            next->_prev = prev;delete pos._node;--_size;return next;}voidpush_front(const T& x){Insert(begin(), x);}//判空boolempty()const{return _size ==0;}private:
        Node* _head;
        size_t _size;};}