当前位置：首页 > news >正文

stl_list的模拟实现

news 来源：原创 2025/9/1 9:42:45

文章目录

stl_list的模拟实现
- 迭代器的介绍以及分类
- stl_list的基本接口介绍
- stl_list的模拟实现
- - 结点类
  - 迭代器类
  - - 基本迭代器操作
  - 链表类
  - - 链表基本操作
- 结语

我们今天又见面啦，给生活加点impetus！！开启今天的编程之路

作者：٩( ‘ω’ )و260
我的专栏：C++初阶，数据结构初阶，题海探骊，c语言
欢迎点赞，关注！！

stl_list的模拟实现

迭代器的介绍以及分类

在c++中，已经说明了迭代器的作用是用来遍历容器，我们发现每一次写代码是迭代器都是iterator，表面上看这些迭代器都是一样的，但是从底层来看，真的是一样的吗？答案是否定的。

迭代器分为单向迭代器，双向迭代器，随机迭代器

其实这三个迭代器很想套娃，那么有什么区别呢？

单向迭代器支持++，双向迭代器支持++/–，随机迭代器支持++/–/+/-。
但是他们都支持引用，等于，不等于等操作符
不同迭代器适配不同的容器（对迭代器的调整方式）：比如单向迭代器适配于单链表等只能单向遍历的数据结构，双向迭代器适配于那些可以双向遍历的双向链表等的数据结构，随机迭代器适配std::vector、std::deque 和数组，适配于可以随机访问元素的数据结构

其实在单向迭代器中我们还能够来分类，分为输入和输出，看图示：
在这里插入图片描述
其实，我们在看一个一个接口支持迭代器操作的时候，我们就能够得到需要传递什么迭代器，比如：

我们来想一下，为什么迭代器不能支持+/-操作呢？
list的底层是链表，所以我们只能通过地址找到下一个位置的地址，如果要+5的话，本质上就是实现总共++5次，这样效率太低了，所以不如不实现。

总结：
由于容器的底层结构不同，有的是数组，有的是结点，导致我们传递的迭代器的种类不同，不同的迭代器有着不同的作用，适配不同的容器

迭代器介绍

stl_list的基本接口介绍

在string中，已经对一些接口进行了介绍，我们主要来看我们没有见过的接口：
在这里插入图片描述

sort：为什么算法库里面有sort，但是这里还自己实现sort呢？
我们先来看算法库中的sort：
在这里插入图片描述
但是先前已经说过，list的迭代器只能够是双向的，只支持++和–，不支持+和-，因为迭代器类型不支持算法库中的sort，所以我们饿只能够容器中自己包含了。
unique:去除链表中的重复元素，但是条件是链表需要有序，因为本质上遍历的时候两个指针是挨着一起的。
remove：给定一个x值，把链表中等于这个值的结点给删掉
erase删除迭代器以及指向的值，一定涉及迭代器失效。
splice（粘接）：条件：必须是同类型的链表才能使用splice

因为上面的接口用的不是很多，我们这里不再详细叙述

总结：迭代器传递类型一定要与容器匹配
数据量大的时候不要用list容器来排序，效率特别低，应该使用vector来排序，本质还是底层结构不一样，支持的迭代器操作不一样导致的效率差别
补充知识点：有无递归的代码会影响效率，在Debug版本下函数栈帧的创建与销毁的代价大于Release版本

stl_list的模拟实现

首先明白，在链表中，指针不是迭代器，因为++迭代器，与++指针的效果不一样，只有在连续的地址中，指针可以等价为迭代器，所以在list类中，我们需要使用迭代器来封装指针，来达到指针向后遍历的效果！！
可能你会问，那我们为什么要封装指针，为啥就不能直接使用指针呢？
没办法，因为在容器中很多接口都是使用迭代器进行的，所以我们必须封装指针为迭代器。所以我们不能向实现vector和string一样，写typedef指针为迭代器。

这里为什么需要定义三个类？
因为结点和链表肯定不能够等价，不能够合到一起，结点是一小个部分，只能控制这一个结点，而链表肯定需要控制整个链表，实现迭代器还是因为指针大部分算法无法完成。

结点类

结点类，顾名思义，只能够控制一个结点，那么一个结点需要控制哪些呢？肯定是成员变量以及构造函数了：

template<class T>//定义模版，因为结点中数值域存储的数据类型可能各不相同
struct list_node{
public:list_node(const T& data=T())//使用匿名对象，没有实参的话，使用匿名对象调用构造函数赋值给data:_next(nullptr),_prev(nullptr),_data(data){}
private:list_node* _next;list_node*_prev;int _data;
};

为什么这里我使用struct，而非class，我们前面提到，使用一个容器，我们不能暴露他的底层。定义为公有不怕暴露吗？实则很难暴露，虽然为公有，但是每个编译器底层实现容器都是不同的，就算能够访问，但是可能每个变量名称都不同，我们敢去访问吗？
所以，这里我们直接大胆一点，设置为公有即可！！

迭代器类

我们让迭代器的成员函数是一个结点，主要是为了记录此时迭代器已经遍历到哪一个位置了。而且迭代器我们一直都是需要的，所以里面的操作都要设置为公有

基本迭代器操作

定义迭代器结构：

template<class T，class Ref,class Ptr>
struct list_iterator{typedef list_iterator<T,Ref,Ptr> self;//为了书写方便一些typedef list_node<T> Node;//重定义是为了方便一些Node* _node;//成员函数，因为结点都是以指针的形式保存的，所以这里设置为指针
};

为什么我这里设置了三个模版参数，我们这里等下再来解答

那么跌代器里面的基本操作有哪些呢？
++/–（调整结点，前置还是后置），*（获取结点中的数据，涉及这个对象是否可以修改，普通的传引用返回还是要有const修饰）->(获取成员变量中的数据，返会的成员变量是否可以修改，加不加const修饰)，迭代器是否相等/不相等。

我们首先来实现这个类的构造函数：

list_iterator(Node* node):_node(node);//构造函数

实现获取成员函数中的数据，重载*操作符：

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

此时数据是可读可写的，那我们如果让数据只可读呢？

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

但是又有一个问题，这两个函数构成函数重载吗，肯定不构成，因为单单凭借返回值，是不能够实现函数重载的，那我们怎么要让这两个成员函数同时存在呢？第一：实现两个迭代器类，因为不同作用域下的同名函数不受影响，但是这样太麻烦了，第二：我们发现，是不是只有类型不一样，，是的。所以我们直接再定义一个模版Ref，这个就是模版的作用。
来看最终代码：

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

来看->操作符：
我们需要返回成员变量中的指针，为什么呢？因为可能list容器的数据是另一个容器，另一个容器的成员保存着需要访问的数据，需要返回指针，我们才能接着访问

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

如果我们返回的指针不想让他被修改呢？
返回const修饰的结果：

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

还是同样的问题，所以我们这里实现了创建了第三个模版参数Ptr，最终结果：

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

对比一下* 和 ->的1区别：操作符我只是想要获取其中的数据，但是->时，成员可能为自定义类型，我需要获取这个成员变量（自定义类型）的数据
都是实现了模版参数来看返回值是否是可以修改的
可以转化为：
typedef list_iterator<T,T&,T>可修改的迭代器类型
typedef list_const_iterator<T,const T&,const T*>不可修改的迭代器类型

实现迭代器++，++之后我们需要返回一个新的迭代器指向新的位置：
分为前置++和后置++

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;
}

判断跌代器是否相等，还是不相等

//l1!=l2
bool operator !=(const self&lt)const
{return _node!=lt._node;
}
bool operator ==(const self&lt)const
{return _node==lt._node;
}

到这里，我们完成了list类中所有迭代器的操作

链表类

我们主要的操作都在这里面实现，我们通过链表类来对整个链表进行数据的增删查改等操作，前面的两个类主要是为了这一个类来进行铺垫

链表基本操作

先来定义链表结构，我们先来思考成员变量，链表主要是由结点构成，所以成员变量肯定包含结点，而且，双向链表一定会有头结点。此外，我们还添加了了一个成员变量size，用来统计结点的个数。因为我们双向链表中是有一个头结点，哨兵位，所以初始化的方式有点不同

在链表中，我们会实现返回首尾的迭代器（分为指向内容是否可修改，const是否修饰），空初始化（初始化头结点），清除，销毁，插入（头插，尾插），删除（头删，尾删），拷贝构造

来看结构：

template<class T>
class list{typedef list_node<T> Node;
pubilc:typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator;
private:Node*_head;int _size = 0;
}

这里我们需要隐藏掉我们的底层结构，不能够轻易给别人访问到。

我们来实现空初始化，主要是实现初始化头结点，为什么要单拎出来呢？
因为构造，拷贝构造，清除等操作都与空初始化有关：

void emptyinit()
{Node* _head=new Node;_head->next=head;_head->prev=head;_size=0;
}

我们来实现构造函数：
我们可以使用普通的构造，也可以使用其他类来构造
其他类来构造的话就能够实现{}花括号来整体传参，不用再来一个一个的push_back数据了。因为多参数隐式类型转换构造需要使用{}给成员变量括起来。

list()
{emptyinit();//直接利用空初始化完成即可
}
list(initializer_list<T> il)//手动创建空间以及首尾迭代器，所以我们使用范围for
{for(auto& e:il){push_back(e);}
}

实现迭代器（普通迭代器与const修饰的迭代器）
首迭代器其实就是_head的下一个结点，将这个结点作为迭代器的成员变量即可。
尾迭代器其实就是_head的前一个结点，将这个结点作为迭代器的成员变量即可。
迭代器分为可修改版本以及不可修改版本

iterator begin()
{return iterator(_head->_next);
}
const_iterator begin()const
{return iterator(_head->_next);
}
iterator begin()
{return iterator(_head->_prev);
}
const_iterator begin()const
{return iterator(_head->prev);
}

思考：为什么下方迭代器while遍历的时候只能写！=，但是在string，vector中可以写<还能写！=
因为底层结构，因为数组连续，写<可以根据地址大小来比较出结果，淡然底层是数组的时候也可以写!=，但是在底层为链表的时候，只能写！=，因为每一个结点的地址没有明确的大小关系

随后我们再来实现数据的插入以及删除
先来看数据的插入操作，这里默认的是在数据的前面进行插入一个结点的操作。我们需要先利用这个数据构造一个newnode的结点，改变指向，完成插入。

void insert(iterator pos,const T&x)
{Node*newnode = new Node(x);//创建新的结点//列出受影响的几个结点Node*cur=pos._node;Node*prev=cur->_prev;//改变指向prev->next=newnode;newnode->_prev=prev;cur->_prev=newnode;newndoe->_next=cur;++_size;
}

思考：list的insert操作会不会涉及到迭代器失效呢？
答案是否定的，因为这里无论如何，迭代器都不可能变成野迭代器。不同于string，vector，因为涉及扩容，所以insert迭代器可能会失效
总结：insert迭代器失效问题：容器底层的数组的可能面临迭代器失效问题，看是否发生扩容。但是底层为链表迭代器不可能失效

再来看链表的删除操作，删除链表，指向改变受到影响结点的指针就好了。注意：erase操作是不能删除头结点的，必须析构的时候再去删除头结点

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;cur=nullptr;//return iterator(next);//调用拷贝构造return next;//隐式类型转换
}

思考：list的erase操作是否会迭代器失效问题？
答案是肯定的，因为我删除了这个结点，结点被标记，造成结点迭代器失效，所以我需要返回下一个位置的迭代器。
总结：几乎所有的容器的erase都会造成迭代器失效问题，erase都必须返回下一个位置的迭代器，并需要重新赋值给迭代器，随后这个迭代器才能够使用。

再来实现清理数据操作：

void clear()
{iterator it=begin();while(it!=end()){it=erase(it);it++;}
}

接下来我们来实现析构，因为有资源，析构必须手动实现，否则内存泄漏，但是在析构之前我们需要先先清理掉里面的数据

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

我们再来看数据的尾插头插，尾删头删的操作：
因为我们已经实现了insert以及erase，这里我们就可以直接来复用了：
直接看代码：

		void push_back(const T& x){//尾插insert(end(), x);}void push_front(const T& x){//头插insert(begin(), x);}void pop_front(){//头删erase(begin());}void pop_back(){//尾删//erase(end()._node->prev);//或者下面这种方法也行的erase(--end());}

注意：begin（）的返回值是_head的下一个结点，但是end（）返回值就是_head，因为左闭右开。

接下来实现拷贝构造，编译器默认生成的是浅拷贝：
思路：先空初始化，随后调用push_back即可

list(const list<T>& lt)//const对象，肯定会调用const的迭代器
{emptyinit();//先空初始化for(auto& e:lt){push_back(e);}
}}

我们再来实现赋值重载，我们来写现代写法，赋值重载肯定会调用拷贝构造，索性我这里进行传值调用：
因为库中的swap交换内置类型效果太差了，所以只适合交换内置类型

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

最后我们再来总结一下：

-> .这三个操作符：
1：.操作符可以访问对象（自定义类型），不能操作内置类型
2：操作符能够解引用指针，可以访问内置类型的指针，或者自定义类型的指针
3：->操作符一般访问的都是自定义类型，访问内置类型很不常见
但是如果是通过上面的三个操作数去访问自定义类型的成员变量，都是必须要去重载的
总结： ->和个操作符不管是内置类型还是自定义类型，是都可以操作的，.点操作符不可以操作指针。.点操作符可以操作对象，即自定义类型的对象，剩余两个不能够直接操作对象。其实，可以理解为->操作符是基于点操作符和解引用操作符的，是先解引用，再来进行点操作符的

结语

感谢大家阅读我的博客，感谢大家的支持，不足之处欢迎留言指正！

生如蝼蚁，当立鸿鹄之志，冥如薄纸，应有不屈之心，每段风雨之后，眼前是翱翔于游的天水一色，走出荆棘，前面是铺满鲜花的康庄大道，登上山顶，脚下便是积翠如云的空山蒙色。
在这里插入图片描述

文章目录

stl_list的模拟实现

迭代器的介绍以及分类

stl_list的基本接口介绍

stl_list的模拟实现

结点类

迭代器类

基本迭代器操作

链表类

链表基本操作

结语

相关文章：