0
0

【C++】STL之list容器的模拟实现

在这里插入图片描述

在这里插入图片描述

个人主页：🍝在肯德基吃麻辣烫
分享一句喜欢的话：热烈的火焰，冰封在最沉默的火山深处。

文章目录

前言

本文章进入C++STL之list的模拟实现。

一、list的三个类的关系分析图

在STL标准库实现的list中，这个链表是一个== 双向带头循环链表==。
在这里插入图片描述

说明：
list是一个类，成员变量为_head
节点类node，是每一个节点。
list的迭代器也升级成了类，成员变量为node。

  • 把迭代器升级成类是为了能够重载++，–，*，！=等可以用在vector迭代器上的操作。

vector和list的区别

vectorlist底层结构是一块连续的空间不是连续的空间随机访问支持下标随机访问不支持下标随机访问插入和删除如果是头插头删，效率为O(n) ，如果插入时需要扩容，会付出更高的代价头插头删都很方便，O(1)的效率空间利用情况底层为连续的动态空间，内存碎片小，空间利用率高底层是一块一块不连续的空间，内存碎片多，空间利用率较低迭代器使用天然的原生迭代器将迭代器封装起来再对外开放迭代器失效在进行插入删除时，插入/删除位置及其之后，空间不再属于自己，由于空间是连续的，其之后的迭代器全部失效在插入时迭代器不会失效，只有在删除时迭代器会失效，且不会影响其他迭代器使用场景需要进行大量随机访问，需要高效存储，不关心插入删除。大量插入删除操作时，不关心随机访问
vector在内存中是一块连续的地址空间，vector下标就是天然的迭代器。
list在内存中并不连续，所以不支持随机访问。为了能够让list完成诸如vector的操作，比如：

list<int>:: iterator it = lt1.begin();while(it != lt1.end()){
    cout <<*it <<" ";++it;}

我们对list的迭代器进行封装，重载各种操作符，以便完成上述的操作。

1.节点的成员变量以及构造函数

在数据结构之链表中，我们知道一个节点必须包含prev,next,val三个变量，在STL的list也是如此。

template<classT>//class list_node 如果这样写，节点的所有成员都是私有的，无法直接访问structlist_node{
    list_node<T>* _prev;
    list_node<T>* _next;
    T _val;//节点的构造函数list_node(const T& val =T()):_prev(nullptr),_next(nullptr),_val(val){}};

注意：
1.在C++，struct升级成了类，但如果不标明，struct的所有成员都是公有的。
2.类名不是类型，不能使用list_node*来作为指针的类型。要使用模板来作为类型。

2.list的迭代器

需要注意的一个点：

  • list的迭代器是用来访问的，而不是用来管理节点的空间，所以list的空间是由自己管理和释放的，我们知道，程序崩溃主要就是同一块空间释放两次。
  • 所以list的迭代器在进行拷贝构造时可以使用浅拷贝，不会造成程序的崩溃。
list<int>:: iterator it = lt1.begin();

对这行代码来说，迭代器不是直接赋值给it的，因为迭代器升级成了类，而不是一个指针。这里会调用迭代器的拷贝构造函数。

list迭代器代码如下：

//迭代器也封装起来，形成我们熟悉的*it,++ittemplate<classT,classRef,classPtr>//class __list_iterator 如果这样写，迭代器是私有的，无法直接使用//迭代器使用类模板，为了重载Ref，Ptr，设置3个模板参数struct__list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;//等价于：//typedef __list_iterator<T, T&, T*> self;

    Node* _node;//成员__list_iterator(Node* node):_node(node){}//返回引用，可读可写
    Ref operator*(){return _node->_val;}//返回地址
    Ptr operator->(){return&_node->_val;}//返回迭代器本身
    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& it)const{return _node != it._node;}booloperator==(const self& it)const{return _node == it._node;}};
  • 1.使用三个模板参数的原因：
    • 要求返回指针，如：用指针->访问成员的情况；或者返回迭代器本身的情况，如 ++ ，–操作。
  • 2.在重载operator->()时，返回的是val的地址，所以我们在调用该函数时，需要进行两次->操作才能访问成员变量。 比如：
structA{A(int a1 =0,int a2 =0):_a1(a1),_a2(a2){}int _a1;int _a2;};

bit::list<A>lt2;
lt2.insert(lt2.begin(),A(1,1));
lt2.insert(lt2.begin(),A(2,2));
list<A>::iterator it = lt2.begin();while(it != lt2.end()){//迭代器重载了*，返回T&,也就是A本身
    cout << it->_a1 <<" "<< it->_a1 << endl;++it;}
cout << endl;

本质上，应该需要 it->->_al，it->->_a2才能够访问成员。
第一个it->是调用operator->重载，返回val的地址，第二个->是通过地址访问成员。
编译器为了简化操作，以及看起来没有那么别扭，对it->->_a1进行简化成了it->_a1。

  • 3.类模板中的Ref是Reference，是引用的意思，Ptr是Pointer，是指针的意思。通过这两个模板名可以知道迭代器需要支持&，和*的操作。
  • 4.迭代器被重命名成self，也就是迭代器本身，在++，–操作时，需要返回迭代器本身。

二、list的增删查改工作

2.1insert()

在pos位置之前插入val值。

首先要获取pos位置的前一个节点，记为posprev。
将新的节点插入即可。

iterator insert(iterator pos,const T& val){
    Node* newnode =newNode(val);
    Node* inspos = pos._node;
    Node* posprev = inspos->_prev;

    newnode->_next = inspos;
    inspos->_prev = newnode;

    newnode->_prev = posprev;
    posprev->_next = newnode;++_size;return posprev;}

list的插入没有迭代器的失效问题。

2.2erase()

删除pos位置的节点，并返回pos位置的下一个位置的迭代器。

iterator erase(iterator pos){assert(pos !=end());
    Node* erapos = pos._node;
    Node* eraprev = erapos->_prev;
    Node* eranext = erapos->_next;

    eraprev->_next = eranext;
    eranext->_prev = eraprev;

    erapos->_prev = erapos->_next =nullptr;delete erapos;--_size;return eranext;}

erase后pos位置的迭代器会失效，我们需要返回下一个位置的迭代器来防止继续访问出现失效的情况。
在这里插入图片描述
删除后如果迭代器不更新，继续访问会出现野指针问题。

2.3 push_back(),pop_back(),push_front(),pop_front()

这几个函数分别是：尾插，尾删，头插，头删，我们复用insert和erase即可完成。

voidpush_back(const T& x){insert(end(), x);}voidpop_back(){erase(--end());}voidpush_front(const T& x){insert(begin(), x);}voidpop_front(){erase(begin());}

2.4clear()

该函数是将链表的所有节点全部释放，哨兵位头节点除外。

//把所有的节点都释放了，除了哨兵位的头节点voidclear(){
    iterator it =begin();while(it !=end()){//为防止迭代器失效，erase后会返回pos位置的下一个位置，所以it不需要++
        it =erase(it);}

    _size =0;}

注意：erase（）删除pos节点后，会返回pos位置的下一个位置，所以这里不需要++it

三、list的默认成员函数

3.1 构造函数

首先申请一个哨兵位的头节点。

voidempty_init(){
    _head =new Node;
    _head->_prev = _head;
    _head->_next = _head;
    _size =0;}//构造函数，构造出一个链表list(){empty_init();}

2.2 拷贝构造

由于我们将迭代器进行了封装升级，现在可以使用++it等操作。
拷贝构造是深拷贝，先new一个_head哨兵位的头节点，再逐个节点进行尾插。

list(list<T>& lt){empty_init();
    list<T>::iterator it = lt.begin();while(it != lt.end()){push_back(*it);++it;++_size;}}

2.3析构

调用clear函数释放所有空间，再释放头节点。

~list(){clear();delete _head;
    _head =nullptr;}

完整代码

namespace bit
{//c++不喜欢使用内部类，所以把节点类放在list外面//节点封装成类template<classT>//class list_node 如果这样写，节点的所有成员都是私有的，无法直接访问structlist_node{
        list_node<T>* _prev;
        list_node<T>* _next;
        T _val;//节点的构造函数list_node(const T& val =T()):_prev(nullptr),_next(nullptr),_val(val){}};//迭代器也封装起来，形成我们熟悉的*it,++ittemplate<classT,classRef,classPtr>//class __list_iterator 如果这样写，迭代器是私有的，无法直接使用//迭代器使用类模板，为了重载Ref，Ptr，设置3个模板参数struct__list_iterator{typedef list_node<T> Node;typedef __list_iterator<T, Ref, Ptr> self;//等价于：//typedef __list_iterator<T, T&, T*> self;

        Node* _node;//成员__list_iterator(Node* node):_node(node){}//返回引用，可读可写
        Ref operator*(){return _node->_val;}//返回地址
        Ptr operator->(){return&_node->_val;}//返回迭代器本身
        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& it)const{return _node != it._node;}booloperator==(const self& it)const{return _node == it._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 iterator(_head->_next);return _head->_next;// 单参数的构造函数可以进行隐式类型转换，从节点的指针转换成一个类}

        iterator end(){//return iterator(_head);return _head;}

        const_iterator begin()const{returnconst_iterator(_head->_next);//return _head->_next; // 单参数的构造函数可以进行隐式类型转换，从节点的指针转换成一个类}

        const_iterator end()const{returnconst_iterator(_head);//return _head;}voidempty_init(){
            _head =new Node;
            _head->_prev = _head;
            _head->_next = _head;
            _size =0;}//构造函数，构造出一个链表list(){empty_init();}//拷贝构造//lt2(lt1)list(list<T>& lt){empty_init();
            list<T>::iterator it = lt.begin();while(it != lt.end()){push_back(*it);++it;++_size;}}//析构~list(){clear();delete _head;
            _head =nullptr;}//把所有的节点都释放了，除了哨兵位的头节点voidclear(){
            iterator it =begin();while(it !=end()){//为防止迭代器失效，erase后会返回pos位置的下一个位置，所以it不需要++
                it =erase(it);}

            _size =0;}voidswap(list<T>& tmp){
            std::swap(_head, tmp._head);
            std::swap(_size, tmp._size);}//赋值运算符重载//先调用拷贝构造，再调用赋值重载//lt3 = lt1//lt1先拷贝构造给tmp
        list<T>&operator=(list<T> tmp){swap(tmp);//出了作用域，调用析构return*this;}

        size_t size()const{return _size;}//尾插传过来的是一个数据，而不是一个节点voidpush_back(const T& x){//Node* tail = _head->_prev;调用构造//Node* newnode = new Node(x);//tail->_next = newnode;//newnode->_prev = tail;//_head->_prev = newnode;//newnode->_next = _head;insert(end(), x);}voidpop_back(){//Node* del = _head->_prev;//_head->_prev = del->_prev;//del->_prev->_next = _head;//del->_next = del->_prev = nullptr;//delete del;//左闭右开，需要--erase(--end());}voidpush_front(const T& x){insert(begin(), x);}voidpop_front(){erase(begin());}//在pos位置之前插入val//不会出现迭代器失效问题
        iterator insert(iterator pos,const T& val){
            Node* newnode =newNode(val);
            Node* inspos = pos._node;
            Node* posprev = inspos->_prev;

            newnode->_next = inspos;
            inspos->_prev = newnode;

            newnode->_prev = posprev;
            posprev->_next = newnode;++_size;return posprev;}//迭代器封装成了类，所以需要通过迭代器找到节点//防止迭代器失效，返回删除节点的下一个
        iterator erase(iterator pos){assert(pos !=end());
            Node* erapos = pos._node;
            Node* eraprev = erapos->_prev;
            Node* eranext = erapos->_next;

            eraprev->_next = eranext;
            eranext->_prev = eraprev;

            erapos->_prev = erapos->_next =nullptr;delete erapos;--_size;return eranext;}private:
        Node* _head;
        size_t _size;};}

总结

本文章完成了list的常用接口的模拟实现。

标签： c++ list windows
本文转载自: https://blog.csdn.net/w2915w/article/details/131785105
版权归原作者 在肯德基吃麻辣烫 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【C++】STL之list容器的模拟实现”的评论:

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

智能对决：提示词攻防中的AI安全博弈

使用密钥文件 SSH 登录服务器：Windows、macOS使用终端或连接工具

【Linux】进程地址空间和进程调度队列

Selenium之Web元素定位

Python 单元测试：深入理解与实战应用20240919

客达天下接口测试（验证码和登录接口自动关联）

VS CODE+Visual Studio Code零基础入门

文章导航