【c++篇】：掌握list--实用的基本使用方法与模拟实现思路

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨个人主页：余辉zmh–CSDN博客
✨文章所属专栏：c++篇–CSDN博客

在这里插入图片描述

文章目录

前言

**在C++编程中，数据结构是理解和应用算法的基础。列表

list

作为线性数据结构的一种，它提供了有序的元素集合，支持高效的插入和删除操作。掌握

list

的基本使用和模拟实现，不仅有助于加深对数据结构的理解，也是提高编程能力的关键。**
**本文将深入探讨

list

的基本概念、常见操作以及模拟实现方法。我们将从

list

的定义开始，逐步介绍如何使用标准库中的

list

类，并进一步探讨如何手动模拟实现一个简单的

list

数据结构。通过理论与实践的结合，帮助读者更好地理解和运用

list

t数据结构。**

一.list的基本概念和使用

在C++中，

list

是一种双向链表容器，属于标准模板库（STL）的一部分。

基本概念

定义：list 是一个序列容器，它允许非连续内存分配，并通过双向链表来管理元素。这意味着list 支持常数时间内的任意位置插入和删除操作，但随机访问元素的时间复杂度较高（因为要顺序查找）。
结构：list 由一系列节点组成，每个节点包含数据部分(_val)和指向前一个(_prev)及后一个(_next)节点的指针。这种结构使得list 在插入和删除操作时不需要移动大量数据，只需调整指针即可。
迭代器：list 提供了双向迭代器，支持向前和向后遍历元素。但需要注意的是，list 的迭代器不是随机访问迭代器（因为内存地址不是连续的），因此不支持通过加减整数来直接访问某个位置的元素，只能（++/–)。

基本操作使用

创建和初始化：- 使用默认构造函数创建一个空list对象：std::list<int> mylist;- 使用初始化列表创建list：std::list<int> mylist={1,2,3,4,5};
添加元素：- 在末尾添加元素：//mylist:1,2,3,4,5//调用尾插函数push_back()mylist.push_back(6);- 在开头添加元素：//mylist:1,2,3,4,5,6//调用头插函数push_front()mylist.push_front(0);- 在指定位置插入元素：//mylist:0,1,2,3,4,5,6//获取begin位置的迭代器std::list<int>::iterator it=mylist.begin();//迭代器it++,指向下一个位置的迭代器it++;//在迭代器it位置前，也就是元素1前插入10//调用插入函数insert()it=mylist.insert(it.10);
删除元素：- 删除指定位置的元素：//mylist:0,10,1,2,3,4,5,6//删除第二个元素10std::list<int>::iterator it=mylist.begin();it++;//调用删除函数erase()it=erase(it);- 删除第一个元素：//mylist:0,1,2,3,4,5,6//调用头删函数pop_frontmylist.pop_front();- 删除最后一个元素：//mylist:1,2,3,4,5,6//调用尾删函数pop_backmylist.pop_back();- 清空整个list：//调用清空函数clear()mylist.clear();
访问元素：- 由于list不是随机访问容器，因此不能通过索引直接访问元素。但可以使用迭代器遍历list来访问元素：std::list<int>::iterator it=mylist.begin();while(it!=mylist.end()){ cout<<*it<<" "}cout<<endl;
大小和容量：- 获取list中元素的数量：//调用size()函数size_t sz=mylist.size();- 判断list是否为空：//调用empty()函数bool ret=mylist.empty(); 注意：list和string，vector这两个类不同的是，list的大小也就是存储的元素个数就是容量，不再区分，size和capacity
排序和查找：- 对list进行排序：//list类中有自己的sort()函数,也可以使用算法库函数里面的mylist.sort();- 查找元素（返回迭代器）：//list类中没有find()函数，所以只能有算法库函数里面的//查找值为4的迭代器位置auto it=mylist.find(mylist.begin(),mylist.end(),4);

二.模拟实现list

**上面我们了解完了如何使用list，接下来，我们将自己模拟实现一个属于自己的list，模拟实现可以帮助我们更好地了解list的底层结构，让我们更好的使用和理解list这个数据结构，而list作为一个双向循环链表，实现一个基本的list需要分别设计三个不同的类，节点类(

_list_node

)，用来封装节点结构；链表类(

list

)，用来封装链表的成员函数和链表结构；迭代器类(

_list_iterator

)，用来封装迭代器。**

注意：

list

类和

vector

类，

string

类不同的是，

list

类需要对迭代器单独使用一个类进行封装，主要原因是因为它们的底层数据结构特性和访问方式的不同

list的底层数据结构：- list是基于链表实现的，链表的节点在内存中的存储位置是不连续的。- 为了在链表中实现顺序访问（即，通过迭代器逐一访问链表中的元素），需要设计一个迭代器类来封装链表节点的指针（可以理解为，迭代器类中的成员变量表示的是一个节点的指针），并通过运算符重载（如++、--、*等）来模拟指针的行为。- 迭代器类内部维护一个指向当前节点的指针，并通过这些运算符重载来移动到下一个或上一个节点，或访问当前节点的数据。
vector和string的底层数据结构：- vector和string是基于数组实现的，它们的元素在内存中是连续存储的。- 由于数组元素的连续性，可以直接使用原生指针（即数组元素的地址）作为迭代器，而无需额外的封装。- 原生指针自然支持顺序访问（通过指针加减来访问相邻元素），因此vector和string的迭代器本质上就是原生指针。

模拟实现的整体框架：

namespace Mylist{template<classT>struct_list_node{//.....};//迭代器类封装template<classT,classRef,classPtr>class_list_iterator{//.....};//链表类封装template<classT>classlist{//.....};}

1.节点类（_list_node)模拟实现

代码实现：template<classT>struct_list_node{//成员变量 _list_node<T>* _prev; _list_node<T>* _next; T _val;//构造函数_list_node(const T& val=T()):_prev(nullptr),_next(nullptr),_val(val){}};
实现原理：- 定义三个成员变量表示一个节点的结构：指向前一个节点的指针_prev，指向后一个节点的指针_next，存储的数据_val- 构造函数初始化时，两个指针都设置为空指针，参数val=T()表示创建的匿名对象（在上一篇vector的模拟实现中有用到，不理解的可以看上一篇文章），自定义类型不如string类型调用对应的构造函数，内置类型也可以调用构造函数初始化。

在这里插入图片描述

2.迭代器类（_list_iterator)模拟实现

基本框架

代码实现：template<classT,classRef,classPtr>struct_list_iterator{typedef _list_node<T> node;typedef _list_iterator<T,Ref,Ptr> self;//成员变量 node* _node;//构造函数_list_iterator(node* node):_node(node){}//....其他成员函数};
实现原理：- _list_iteartor是一个模板类，模版参数有三个，这里参数T比较好理解，表示的是存储的数据类型，而后面两个比较难理解，这里先不做解释，在后面讲到相关函数时在详细解释。- 用typedef对两个类类型名重定义（方便实用），注意，模板类和普通的类有一点不同，普通类，类名就是类型；而模版类，类名加上模版参数才是类型。- 成员变量是一个节点的指针，构造函数将参数节点指针初始化为迭代器（其实本质上还是指针，因为迭代器就是一种指针类型）。

成员函数

1.**

operator++

函数：**

代码实现：//前置++self&operator++(){ _node=_node->_next;return*this;}//后置++self operator++(int){ self tmp(*this); _node=_node->_next;return tmp;}
实现原理：- 因为list的迭代器不能直接加减常数，所以只能++或–，而++又分为前置++和后置++- 前置++，迭代器本身需要+1，并且返回的是+1后的迭代器，直接让当前节点指针指向下一个节点即可，返回类型是self&（_list_iterator<T,Ref,Ptr>&)- 后置++，拷贝构造一个新的迭代器用来保存+1前的迭代器，对原本的迭代器+1，返回保存的迭代器，返回类型时self（_list_iterator<T,Ref,Ptr>)，因为保存的迭代器是一个局部变量，函数调用结束会销毁，所以不能用引用类型的返回。- 后置++参数中的int是用来和前置++构成函数重载，进行区分

2.**

operator--

函数：**

代码实现：//前置--self&operator--(){ _node=_node->_prev;return*this;}//后置--self operator--(int){ self tmp(*this); _node=_node->_prev;return tmp;}
实现原理：- –又分为前置–和后置–- 前置–，迭代器本身需要-1，并且返回的是-1后的迭代器，直接让当前节点指针指向前一个节点即可，返回类型是self&（_list_iterator<T,Ref,Ptr>&)- 后置–，拷贝构造一个新的迭代器用来保存-1前的迭代器，对原本的迭代器-1，返回保存的迭代器，返回类型时self（_list_iterator<T,Ref,Ptr>)，因为保存的迭代器是一个局部变量，函数调用结束会销毁，所以不能用引用类型的返回。- 后置–参数中的int是用来和前置–构成函数重载，进行区分

3.**

operator!=

函数：**

代码实现：booloperator!=(const selt& it){return _node!=it._node;}
实现原理：- 左参数迭代器和右参数迭代器判断是否不等，左参数迭代器是this，右参数迭代器是it- 直接返回两个迭代器是否是同一个节点的指针

4.**

operator*

函数：**

代码实现：T&operator*(){return _node->_val;}const T&operator*(){return _node->_val;}//使用模版参数合二为一Ref operator*(){return _node->_val;}
实现原理：- 首先迭代器是一个指向节点的指针，对其解引用，表示获取节点中的数据域（_val)存储的数据- 返回节点中的数据域(_val)，返回类型是T&- 这里有一个注意点，如果是对const类型的迭代器解引用，直接将返回类型写成T&就会导致const类型的无法调用该函数，写成const T&才可以调用，所以为了解决这个问题，引入了第二个模版参数Ref，用来自动替换这两个不同的类型。

5.**

operator->

函数：**

代码实现：T*operator->(){return&_node->_val;}const T*operator->(){return&_node->_val;}//使用模版参数合二为一Ptr operator->(){return&-node->_val;}
实现原理：- ->运算符重载和*不同的是，operator*，返回的是节点中存储的数据_val的地址，返回类型是T*类型- 和operator*一样，如果有const类型的迭代器使用->，返回类型直接写成T*会导致const类型的无法调用该函数，写成const T* 类型才可以调用，为了解决这个问题，引入了第三个模版参数Ptr，用来自动替换这两个不同的类型。

3.链表类(list)模拟实现

基本框架

代码实现：

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;//...成员函数private://成员变量
    node* _head; 
    size_t _size;};

实现原理：- 将节点类类型重定义，设置成私有，迭代器类类型重定义，设置成公有- 成员变量声明一个哨兵节点，声明一个大小用来记录链表的节点个数

默认成员函数

1.构造函数代码实现：

voidempty_init(){
    _head=new node;
    _head->_next=_head;
    _head->_prev=_head;
    _size=0;}//构造函数list(){empty_init();}

实现原理：- 用一个函数将初始化的内容分开存放，这样方便拷贝构造函数直接调用- 定义一个哨兵节点，该节点的前节点指针和后节点指针都指向该节点，将大小初始化为0

在这里插入图片描述

2.拷贝构造函数代码实现：

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

实现原理：- 先用函数empty_init()函数初始化一个空链表，也就是被拷贝的链表- 用范围for循环，将被拷贝的链表中的节点数据依次插入到拷贝的链表中完成拷贝

3.赋值运算符重载：

swap(list<T>& lt){
    std::swap(_head,lt._head);
    std::swap(_size,lt._size);}
list<T>&operator=(list<T> lt){swap(lt);return*this;}

实现原理：- 用一个自己实现的交换函数，交换两个链表的哨兵节点和大小，就能达到赋值的效果- 最后将被赋值的链表返回，返回类型是链表类类型list<T>，返回要引用返回

4.析构函数：

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

实现原理：- 用一个自己实现的清空函数，通过迭代器来依次删除链表中的每个节点，再讲大小置为0- 析构函数调用清空函数后，在通过delete函数，释放哨兵节点，最后置为空指针

迭代器成员函数

1.**

begin()

函数代码实现：**

//普通对象类型的迭代器
iterator begin(){return _head->_next;}//const对象类型的迭代器
const_iterator begin()const{return _head->_next;}

实现原理：直接返回哨兵节点的下一个节点即可

2.**

end()

函数代码实现：**

//普通对象类型的迭代器
iterator end(){return _head;}//const对象类型的迭代器
const_iterator end()const{return _head;}

实现原理：直接返回哨兵节点即可

在这里插入图片描述

插入成员函数

1.**

insert()

函数代码实现：**

 iterator insert(iterator pos const T& x){
     node* newnode=newnode(x);
     node* cur=pos._node;
     node* prev=cut->_prev;
     
     prev->_next=newnode;
     newnode->_next=cur;
     cur->_prev=newnode;
     newnode->_prev=prev;
     _size++;return pos
    
 }

实现原理：- 先创建需要插入的新节点newnode，然后找pos迭代器指向的当前节点cur，再找到pos当前指向的节点的前节点prev- 将新节点插入到节点cur和prev中间即可

在这里插入图片描述

2.**

push_back()

尾插函数代码实现：**

voidpush_back(const T& x){//相当于在哨兵节点前插入insert(end(),x);}

3.**

push_front()

头插函数代码实现：**

voidpush_front(const T& x){//相当于在第一个节点前插入，也就是哨兵节点的后一个节点insert(begin(),x);}

删除成员函数

1.**

erase()

删除函数代码实现：**

iteraotr erase(iterator pos){assert(pos!=end());
    node* cur=pos._node;
    node* prev=cur->_prev;
    node* next=cur->_next;
    
    prev->_next=next;
    next->_prev=prev;return next;}

实现原理：- 首先断言判断pos是否是指向哨兵节点的迭代器，因为不能将哨兵节点删除- 找到当前迭代器pos指向的节点，再找到前节点prev，后节点next- 将pos指向的节点删除，返回next指向的节点，也就是删除节点的下一个节点

在这里插入图片描述

2**

pop_back()

尾删函数代码实现:**

voidpop_back(){//相当于删除最后一个节点，也就是哨兵节点的前一个节点erase(--end);}

3.**

pop_front()

头删函数代码实现：**

voidpop_front(){//相当于删除第一个节点，也就是哨兵节点的后一个节点erase(begin());}

三.模拟实现完整代码

list.h

文件

#include<iostream>#include<algorithm>#include<assert.h>usingnamespace std;namespace Mylist
{//节点类封装template<classT>structlist_node{//成员变量，前节点指针，后节点指针，存储的数据val
        list_node<T>* _next;
        list_node<T>* _prev;
        T _val;//构造函数  创造节点list_node(const T& val=T()):_next(nullptr),_prev(nullptr),_val(val){}};//迭代器类封装template<classT,classRef,classPtr>struct_list_iterator{typedef _list_iterator<T,Ref,Ptr> self;typedef list_node<T> node;//成员变量 一个节点的指针
        node* _node;//构造函数 将传入的节点指针变为迭代器_list_iterator(node* node):_node(node){}

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

        Ptr operator->(){return&_node->_val;}booloperator!=(const self& it){return _node!=it._node;}

        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;}};//链表类封装template<classT>classlist{typedef list_node<T> node;voidempty_init(){
             _head=new node;
            _head->_next=_head;
            _head->_prev=_head;
            _size=0;}public://重定义迭代器类型typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T,const T&,const T*> const_iterator; 
        iterator begin(){//隐式类型转换，相当于调用_list_iterator()构造函数，创建迭代器类型的对象返回return _head->_next;}
        iterator end(){return _head;}
        const_iterator begin()const{return _head->_next;}
        const_iterator end()const{return _head;}//构造函数 创建带哨兵节点的链表list(){
            cout<<"list()"<<endl;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;}voidclear(){auto it=begin();while(it!=end()){
            it=erase(it);}
            _size=0;}//析构函数~list(){
            cout<<"~list()"<<endl;clear();delete _head;
            _head=nullptr;}//插入
        iterator insert(iterator pos ,const T& x){
            node* cur=pos._node;
            node* prev=cur->_prev;
            node* newnode=newnode(x);

            prev->_next=newnode;
            newnode->_prev=prev;
            newnode->_next=cur;
            cur->_prev=newnode;
            _size++;return pos;}//尾插voidpush_back(const T& x){/* node* newnode=new node(x);
            node*prev=_head->_prev;
            prev->_next=newnode;
            newnode->_next=_head;
            newnode->_prev=prev;
            _head->_prev=newnode;
            _size++;*/insert(end(),x);}//头插voidpush_front(const T& x){insert(begin(),x);}//删除
        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;
            _size--;return next;}//尾删voidpop_back(){//这里end()要先减后用，所以有前置--erase(--end());}//头删voidpop_front(){erase(begin());}

        size_t size()const{return _size;}private://成员变量 哨兵节点
        node* _head;
        size_t _size;};//测试用例类classA{public:A(int a1=0,int a2=0):_a1(a1),_a2(a2){}int _a1;int _a2;};}

test.cpp

文件

#include"list.h"voidtest1(){
    Mylist::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);
    cout<<lt.size()<<endl;
    Mylist::list<int>::iterator it=lt.begin();while(it!=lt.end()){
        cout<<*it<<" ";
        it++;}
    cout<<endl;
    lt.pop_back();
    lt.pop_front();for(auto e:lt){
        cout<<e<<" ";}
    cout<<endl;
    cout<<lt.size()<<endl;
    lt.clear();
    cout<<lt.size()<<endl;}voidtest2(){
    Mylist::list<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    Mylist::list<int>v2(v1);
    Mylist::list<int> v3;
    v3=v1;for(auto e:v2){
        cout<<e<<" ";}
    cout<<endl;for(auto e:v3){
        cout<<e<<" ";}
    cout<<endl;}voidtest3(){
    Mylist::list<Mylist::A> lt;
    lt.push_back(Mylist::A(1,1));
    lt.push_back(Mylist::A(2,2));
    lt.push_back(Mylist::A(3,3));
    lt.push_back(Mylist::A(4,4));
    Mylist::list<Mylist::A>::iterator it=lt.begin();while(it!=lt.end()){
        cout<<it->_a1<<","<<it->_a2<<" ";
        it++;}
    cout<<endl;
    it=lt.begin();while(it!=lt.end()){
        cout<<(*it)._a1<<","<<(*it)._a2<<" ";
        it++:}
    cout<<endl;}intmain(){//test1();//test2();test3();return0;}

以上就是关于list的基本使用和模拟实现的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
在这里插入图片描述

标签： c++ list windows

本文转载自: https://blog.csdn.net/2301_82347435/article/details/143627188
版权归原作者 余辉zmh 所有，如有侵权，请联系我们删除。

【c++篇】：掌握list--实用的基本使用方法与模拟实现思路

文章目录

前言

一.list的基本概念和使用

基本概念

基本操作使用

二.模拟实现list

1.节点类（_list_node)模拟实现

2.迭代器类（_list_iterator)模拟实现

基本框架

成员函数

3.链表类(list)模拟实现

基本框架

默认成员函数

迭代器成员函数

插入成员函数

删除成员函数

三.模拟实现完整代码

发表评论

“【c++篇】：掌握list--实用的基本使用方法与模拟实现思路”的评论:

关于作者

overfit同步小助手

相关阅读

文章导航