0
0

【C++】list的模拟实现

头像🚀个人主页：奋斗的小羊 🚀所属专栏：C++ 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~
动图描述

目录

💥1、list的模拟实现

💥1.1 list简单介绍

list

是带头双向循环链表，它与我们之前学习的

string

和

vector

的最大区别是物理结构不同，

string

和

vector

在逻辑上和物理上都是连续的，但

list

只在逻辑上连续。

list

由一个个节点组合而成，一个节点内存有数据、上一个节点的地址和下一个节点的地址，为了方便处理这里我们将一个节点封装成一个类，这个类还需要我们显示写构造函数，当我们创建一个新节点时需要调用这个默认构造完成对新节点的初始化。
为了使节点类存储不同类型的数据，可以将这个节点类设计为节点类模版。

template<classT>structlist_node{
    T _data;
    list_node<T>* _next;
    list_node<T>* _prev;list_node(const T& x =T()):_data(x),_next(nullptr),_prev(nullptr){}};
  • 对于构造函数，参数部分我们给一个缺省值，为了同时照顾类类型和内置类型，需要使用匿名对象默认构造

同时将

list

类也封装成一个模版，其成员变量是节点类类型的指针，指向

list

的哨兵节点，我们需要在

list

的默认构造函数中创建一个哨兵节点并初始化。
为了方便得到

list

中的节点个数，可以在

list

类中多加一个成员变量

_size

用于记录

list

的节点个数：

template<classT>classlist{typedef list_node<T> Node;public:list(){
        _head =new Node;
        _head->_next = _head;
        _head->_prev = _head;
        _size =0;}private:
    Node* _head;
    size_t _size;}

💥1.2 list主要函数接口

💥1.2.1 构造

构造一个哨兵节点，并使前后指针都指向自己。

list(){
    _head =new Node;
    _head->_next = _head;
    _head->_prev = _head;
    _size =0;}

💥1.2.2 拷贝构造

拷贝构造一个

list

，首先这个

list

需要有哨兵节点，然后再将节点一个一个取出尾插。

voidempty_init(){
    _head =new Node;
    _head->_next = _head;
    _head->_prev = _head;
    _size =0;}list(const list<T>& lt){empty_init();for(auto& e : lt){push_back(e);}}
  • list中有存类类型的可能，范围for这里最好使用引用

💥1.2.3 赋值重载

voidswap(list<T>& lt){
    std::swap(_head, lt._head);
    std::swap(_size, lt._size);}
list<T>&operator=(list<T> lt){swap(lt);return*this;}
  • swap函数参数传引用，但不能用const修饰
  • 赋值重载返回链表的引用，参数部分要用传值传参，为的是调用拷贝构造

💥1.2.4 迭代器

本来需要先通过指向节点的指针来构造一个迭代器再返回，不过我们可以返回指向节点的指针，利用隐式类型转换构造一个临时迭代器返回。

iterator begin(){//iterator it(_head->_next);//return it;return _head->_next;}
iterator end(){return _head;}
const_iterator begin()const{return _head->_next;}
const_iterator end()const{return _head;}
  • begin()是指向第一个节点的迭代器，end()是指向哨兵节点的迭代器

💥1.2.5 插入

在指定位置插入一个节点，首先需要先得到指定位置的前一个节点和当前位置的节点，构造一个新节点后将新节点和前后节点连接起来，最后++

_size

即可。

voidinsert(const iterator& pos,const T& x){
    Node* pcur = pos._node;
    Node* prev = pcur->_prev;

    Node* newnode =newNode(x);
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = pcur;
    pcur->_prev = newnode;++_size;}

| 头插：

voidpush_front(const T& x){insert(begin(), x);}

| 尾插：

voidpush_back(const T& x){insert(end(), x);}

💥1.2.6 删除

voiderase(const iterator& pos){//不能删除哨兵节点assert(pos !=end());
    Node* pcur = pos._node;
    Node* prev = pcur->_prev;
    Node* next = pcur->_next;

    prev->_next = next;
    next->_prev = prev;delete pcur;--_size;}

| 头删：

voidpop_front(){erase(begin());}

| 尾删：

voidpop_back(){erase(--end());}
  • 尾删删除的是最后一个节点，而end()是指向哨兵位的迭代器

💥1.2.7 迭代器失效的问题

对于

list

的迭代器，插入操作不会使迭代器失效，因为

list

的迭代器指向某一个节点，插入一个节点不会改变迭代器的指向。
对于删除操作，删除

pos

位置的节点后迭代器指向的空间已经被释放不能访问，迭代器就失效了。解决这个问题的办法还是和之前一样删除某个节点后返回下一个节点的迭代器。

iterator erase(const iterator& pos){//不能删除哨兵节点assert(pos !=end());
    Node* pcur = pos._node;
    Node* prev = pcur->_prev;
    Node* next = pcur->_next;

    prev->_next = next;
    next->_prev = prev;delete pcur;--_size;return next;}

虽然插入操作不会使迭代器失效，但是库中

insert

也有返回值，其返回的是刚插入节点的迭代器。

iterator insert(const iterator& pos,const T& x){
    Node* pcur = pos._node;
    Node* prev = pcur->_prev;

    Node* newnode =newNode(x);
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = pcur;
    pcur->_prev = newnode;++_size;return newnode;}

💥1.2.8 clear

clear

的功能是从列表容器中删除所有元素，但是不删除哨兵节点。

voidclear(){auto it =begin();while(it !=end()){
        it =erase(it);}}

💥1.2.9 析构

我们需要遍历链表一个节点一个节点的释放，可以先调用

clear

，再释放掉哨兵节点即可。

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

💥1.3 list迭代器

因为

list

在物理结构上不连续，所以其迭代器不能像

string

和

vector

的迭代器一样可以直接++和- -等操作，需要特殊封装重载运算符才能实现。
虽然我们对

list

的迭代器进行了封装，但其核心还是指向节点的指针。

list

迭代器的成员变量是指向节点的指针。

template<classT>structlist_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;
    Node* _node;}

💥1.3.1 构造

用节点的地址初始化迭代器的成员变量

_node

：

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

💥1.3.2 ++重载

| 前置++：

list

的迭代器++得到的是下一个节点的迭代器：

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

| 后置++：

Self operator++(int){
    Self tmp(*this);//使用编译器默认生成的拷贝构造就行
    _node = _node->_next;return tmp;}

后置++重载需要先保存当前迭代器指向的节点，然后再++指向下一个节点，返回临时节点。

  • 后置++需要用int占位
  • 这里拷贝构造了一个临时节点，只能传值返回，不能传引用返回，因为这个临时节点在出了作用域后就销毁了
  • 这里虽然有拷贝构造，但是我们不需要显示的写拷贝构造函数，使用编译器默认生成的就行，编译器默认生成的拷贝构造函数完成的是浅拷贝，而我们需要的就是浅拷贝
  • 也不需要写析构，因为迭代器的目的只是遍历list，不能释放节点

💥1.3.3 - -重载

和++重载保持一致。

| 前置- -：

Self&operator--(){
    _node = _node->_prev;return*this;}

| 后置- -：

Self operator--(int){
    Self tmp(*this);
    _node = _node->_prev;return tmp;}

💥1.3.4 解引用重载

list

迭代器是一个类，直接解引用不行，需要**重载

*

运算符**才能得到节点中存的数据。

**| 

*

重载：**

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

**| 

->

重载：**

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

当

list

中存的数据类型是类类型时就需要使用到

->

运算符，其运算符重载返回的是节点中数据地址，再用这个地址+

->

来得到类中的数据。

voidtest_list2(){structaa{int _a1 =1;int _a2 =2;};

    list<aa> lt;
    lt.push_back(aa());
    lt.push_back(aa());
    lt.push_back(aa());
    lt.push_back(aa());

    list<aa>::iterator it = lt.begin();while(it != lt.end()){//cout << *it << " ";
        cout << it->_a1 <<" "<< it->_a2 <<" ";++it;}
    cout << endl;}

事实上这里的解引用操作应该是下面这样的：

cout << it.operator->()->_a1 <<" "<< it.operator->()->_a2 <<" ";

只是为了方便省略了其中的一个

->

。

💥1.3.5 ==和!= 重载

判断两个迭代器中的

_node

指向的节点是否相同。

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

💥1.3.6 普通迭代器和const迭代器

我们之前实现的其他类的const迭代器是

const_iterator

，为什么const迭代器不是

const iterator

呢？它们有什么区别？
迭代器笼统的说就是指针，其作用是遍历数据，所以其指向是需要改变的，

const iterator

表示的是迭代器的指向不能改变，而

const_iterator

表示的才是迭代器指向的内容不能改变。

普通迭代器和

const

迭代器我们都需要，常规的做法就是普通迭代器和

const

迭代器分开实现，但是这样实现的两个迭代器中很多内容都是重复的，因为改变迭代器指向的内容只能通过重载的

*

和

->

来完成，所以两个迭代器只有这两个运算符重载不同，其他都是一样的。

为了避免过多重复的代码，我们可以在模版参数上下手：

template<classT,classRef,classPtr>structlist_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;
    Node* _node;
    
    Ref operator*(){return _node->_data;}
    
    Ptr operator->(){return&_node->_data;}}

在

list

类中这样重定义普通迭代器和

const

迭代器：

typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator;

传不同的模版参数，按需实例化出合适的类。 如果多个类高度相似，我们就可以想方设法的搞成模版，避免过多重复。

💥2、list模拟实现完整代码

list.h:

#pragmaonce#include<iostream>#include<assert.h>usingnamespace std;namespace yjz
{template<classT>structlist_node{
        T _data;
        list_node<T>* _next;
        list_node<T>* _prev;list_node(const T& x =T()):_data(x),_next(nullptr),_prev(nullptr){}};template<classT,classRef,classPtr>structlist_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;
        Node* _node;list_iterator(Node* node =nullptr):_node(node){}

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

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

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

        Self&operator--(){
            _node = _node->_prev;return*this;}

        Self operator++(int){
            Self tmp(*this);//使用编译器默认生成的拷贝构造就行
            _node = _node->_next;return tmp;}

        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;voidempty_init(){
            _head =new Node;
            _head->_next = _head;
            _head->_prev = _head;
            _size =0;}list(){empty_init();}list(const list<T>& lt){empty_init();for(auto& e : lt){push_back(e);}}voidswap(list<T>& lt){
            std::swap(_head, lt._head);
            std::swap(_size, lt._size);}

        list<T>&operator=(list<T> lt){swap(lt);return*this;}~list(){clear();delete _head;
            _head =nullptr;}voidclear(){auto it =begin();while(it !=end()){
                it =erase(it);}}//void push_back(const T& x)//{//    Node* newnode = new Node(x);//    Node* tail = _head->_prev;//    tail->_next = newnode;//    newnode->_prev = tail;//    _head->_prev = newnode;//    newnode->_next = _head;//    ++_size;//}voidpush_front(const T& x){insert(begin(), x);}voidpush_back(const T& x){insert(end(), x);}

        iterator insert(const iterator& pos,const T& x){
            Node* pcur = pos._node;
            Node* prev = pcur->_prev;

            Node* newnode =newNode(x);
            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = pcur;
            pcur->_prev = newnode;++_size;return newnode;}

        iterator erase(const iterator& pos){//不能删除哨兵节点assert(pos !=end());
            Node* pcur = pos._node;
            Node* prev = pcur->_prev;
            Node* next = pcur->_next;

            prev->_next = next;
            next->_prev = prev;delete pcur;--_size;return next;}voidpop_front(){erase(begin());}voidpop_back(){erase(--end());}

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

        size_t size()const{return _size;}boolempty()const{return _size ==0;}private:
        Node* _head;
        size_t _size;};}

test.cpp:

#define_CRT_SECURE_NO_WARNINGS#include"list.h"namespace yjz
{voidtest_list1(){
        list<int> lt;
        lt.push_back(1);
        lt.push_back(2);
        lt.push_back(3);
        lt.push_back(4);
        lt.push_back(5);

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

        lt.erase(++lt.begin());
        lt.insert(--lt.end(),10);for(auto e : lt){
            cout << e <<" ";}
        cout << endl;}voidtest_list2(){structaa{int _a1 =1;int _a2 =2;};

        list<aa> lt;
        lt.push_back(aa());
        lt.push_back(aa());
        lt.push_back(aa());
        lt.push_back(aa());

        list<aa>::iterator it = lt.begin();while(it != lt.end()){//cout << *it << " ";
            cout << it->_a1 <<" "<< it->_a2 <<" ";
            cout << it.operator->()->_a1 <<" "<< it.operator->()->_a2 <<" ";++it;}
        cout << endl;}voidtest_list3(){
        list<int> lt1;
        lt1.push_back(1);
        lt1.push_back(2);
        lt1.push_back(3);
        lt1.push_back(4);

        list<int> lt2 = lt1;

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

        list<int> lt3;
        lt3.push_back(10);
        lt3.push_back(20);
        lt3.push_back(30);
        lt3.push_back(40);
        
        lt2 = lt3;

        list<int>::iterator i = lt2.begin();while(i != lt2.end()){
            cout <<*i <<" ";++i;}
        cout << endl;}}intmain(){
    yjz::test_list3();return0;}
标签： c++ list windows
本文转载自: https://blog.csdn.net/2301_78843337/article/details/141141666
版权归原作者 小羊在奋斗 所有， 如有侵权，请联系我们删除。
登录后发布评论

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

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

如何给SaaS应用做安全

【软件测试】自动化常用函数

postman变量和脚本功能介绍

Python Selenium常见的报错以及措施

idea导出配置文件

如何在visual studio中 生成 并 使用dll和lib文件

Docker homeassistant 反向代理 外网访问

文章导航