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

C++入门之stl六大组件--List源码深度剖析及模拟实现

news 2025/7/8 3:38:18

文章目录

前言

一、List源码阅读

二、List常用接口模拟实现

1.定义一个list节点

2.实现一个迭代器

2.2const迭代器

3.定义一个链表，以及实现链表的常用接口

三、List和Vector

总结

前言

本文中出现的模拟实现经过本地vs测试无误，文件已上传gitee，地址:list: 模仿实现stl的list - Gitee.com

一、List源码阅读

首先我们阅读源码，阅读源码我按照如下方式：先找到单个节点的定义，再找到list里面的主要成员函数。

list_node链表节点的定义，如下：有三个成员，prev,next指针，数据域。

实现链表的接口：增删改查，回想我们用C语言实现的顺序表的时候，使用指针去实现。使用C++的时候，模拟实现string，也是使用迭代器。迭代器就是模拟指针的行为，但是链表直接使用指针++，不一定能访问到下一个节点，所以我们要封装一下原生指针--迭代器，去实现对list的访问。

阅读源码，_list_iterator这个迭代器，有三个模板参数，猜测T应该是类型，Ref是引用，Ptr是指针，为什么有三个模板参数？后续再分析。这个迭代器里实现了一个原生迭代器，一个const迭代器，const调用const对象，然后还有一个self，暂时不明白什么意思。继续往下。

 阅读到这里，重定义了一些参数。注意这里：

  • typedef _list_node<T> * link_type;  
  • link_type node;
  • _list_iterator(link type x):node(x){}

和C语言一样，这里定义了一个节点的指针，作为实现迭代器的最小单元

继续往下阅读，这里有一些运算符重载的函数，比较节点是否相等，以及引用，注意这里引用的返回值使用了reference，上面看出来将Ref重定义成了reference，所以这里可以猜测，ref就是返回引用的值

 这里实现了运算符重载函数，使用迭代器，去访问前后的节点。注意这里的返回值是self，前面读到self就是_list_iterator的一个模板参数。对比之前实现日期类的时候，日期类++,返回的就是一个日期类对象。这里使用迭代器进行++,猜测这里返回的就是一个迭代器。

继续查看迭代器的使用：在list的成员函数中，查看到begin：指向头节点的下一个，end指向头节点。rbegin指向头节点，rend指向头节点的下一个。

判断链表是否为空：判断头节点的下一个是否指向头节点

计算链表的size:根据begin,end去计算

 以及链表中最重要的插入insert,通过迭代器找到pos的位置，根据T去构建一个Node，再进行插入。头插尾插都可以复用Insert。头插头删的时候先保留现在的指针指向情况，再进行修改，修改完了之后再删除这个节点

 往下阅读，到了list的主体部分，有两个模板参数。alloc暂时不明白是什么

 这里实现了一种创建节点的成员函数，create_node：通过T类型的参数x创建一个节点.

empty_initialize 空的初始化，只创建一个节点

二、List常用接口模拟实现

通过上面阅读源码，我们来模仿实现list的一些常用接口。

1.定义一个list节点

template<class T>
struct list_node
{T _data;list_node<T> * _next;list_node<T> * _prev;
}

2.实现一个迭代器

 迭代器要么就是原生指针，要么就是自定义类型对原生指针的封装，模拟指针的行为。

list用一个节点的指针，去构造一个迭代器

template<class T>
struct _list_iterator
{typedef list_node<T> node;typedef _list_iterator<T> self;//定义一个指针，指向链表node * _node;//构造函数 用一个节点指针去构造迭代器_list_iterator(node * n):_node(n){}//实现迭代器的功能//指针++向后遍历，就如日期类，返回的还是一个日期类对象;迭代器++,返回一个迭代器对象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;}T& operator*(){return _ndoe->data;}bool operator == (const self& s){return _node == s._node;}bool operator !=(const self &s){return _node != s._node;}

2.2const迭代器

假设我们传了一个const对象，

  • void print_list(const list<int>&lt)。
  • 对象的类型是一个const list<int> * ，调用不了普通迭代器,是一个经典的权限放大，所以我们要对this加一个const。此时变成了const* _head,指针本身不能改变，但是指向的内容可以改变。即我们还是可以对对象进行改变。
  • 在stl库中，它使用const修饰*this,返回值也是一个const_iterator。但是，对于所有的成员函数都使用const修饰*this和返回值类型很冗余，所以我们这里增加了一个模板参数class Ref。
	template<class T>struct __list_const_iterator{typedef list_node<T> node;typedef __list_const_iterator<T> self;node* _node;__list_const_iterator(node* n):_node(n){}//保护返回的值不能被修改const T& operator*(){return _node->_data;}//... 其他成员函数都相同};

template<class T,class Ref, class Ptr>struct _list_iterator
{typedef list_node<T> node;typedef _list_iterator<T,Ref,Ptr> self;node  * _node;_list_iterator(node * n):_node(n){}Ref operator*(){return _ndoe->data;}//注意这里 如果我定义了一个AA类型的链表，通过迭代器去访问,指针类型为AA*// 现在要访问它的成员 可以这样： *(it)._a1; //也可以it->->a1 一个是运算符重载调用，it是自定义类型，无法直接使用箭头，it-> 就相当于运算符重载operator-> AA*//一个是找成员 //这里为了增强可读性 省略了一个箭头 it->_a1;Ptr operator->(){return &_node->data;}self& operator--(){}//其余运算符操作类似
}template<class T>
class list
{//注意这里模板参数 调用普通迭代器 T&传给ref, 调用const迭代器 const T& 传给ref typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T,const T&, const T*> const_iterator;iterator begin(){return iterator(_head->_next);}const iterator begin(){return const_iterator(_head->_next);}//..其余类似
}

3.定义一个链表，以及实现链表的常用接口

template<class T>
struct _list
{typedef list_node<T> node;typedef _list_iterator<T> iterator;//list的成员node* _head;//list的构造 初始只有一个头节点list(){_head = new node;_head->_next = _head;_head->_prev = _head;}//list的一些成员函数 //通过迭代器定位begin和enditerator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//通过迭代器对指定pos位置进行增删改查void  insert(iterator pos, const T& x){node new_node = new node(x);//iterator cur = pos;//这里是要通过pos的指针，找到这个节点 对pos进行解引用node * cur = pos._node;node * prev = cur->_prev;prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;}void push_back(){insert(end(),x);}void push_front(){insert(begin(),x);}void 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;}void pop_back(){erase(end());}void pop_front(){erase(begin());}//打印void print_list(const list<T> & lt){iterator it = lt.begin();while(it != lt.end()){cout<<*it;++it;}cout<<endl;}}

三、List和Vector对比

vector与list都是stl中非常重要的序列容器，由于两个容器的底层结构不同，导致特性以及应用场景不同

vectorlist
底层结构动态顺序表，一段连续的空间带头节点的双向循环链表
随机访问支持随机访问，访问某个元素效率O(1）不支持随机访问，访问某个元素效率O(N)
插入和删除在任意位置插入删除元素效率较低，时间复杂度O(N),插入可能需要扩容，开辟新空间，拷贝元素，释放旧空间任意位置插入和删除效率高，不需要搬移元素。时间复杂度O(1)
空间利用率底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器原生指针对原生指针（节点指针）进行封装
迭代器失效在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能导致扩容，导致原来迭代器失效，删除时，也可能失效。需要重新给迭代器赋值插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，因为那个节点已经被删除。其他迭代器不受影响
使用场景需要高效存储，支持随机访问，不关心插入删除效率大量插入和删除操作，不关心随机访问

总结

本文主要对stl源码中list内容进行阅读，并模拟实现。技术有限，如有错误请指正。

http://www.lryc.cn/news/112734.html

相关文章：

  • windows下以指定用户访问SMB服务器进行读写
  • 数组根据属性去重
  • 无损音乐从哪找？五个网站+免费下载，你确定不来看看？
  • 2023华数杯数学建模B题思路模型论文分析
  • K8S系列文章之 使用Kind部署K8S 并发布服务
  • 从0到1开发go-tcp框架【4实战片— — 开发MMO之玩家聊天篇】
  • 无重复字符的最长子串 LeetCode热题100
  • Docker搭建zookeeper
  • LeetCode 热题 100 JavaScript--160. 相交链表
  • AWS S3 协议对接 minio/oss 等
  • 手机便签内容不见了怎么恢复正常？
  • 【架构】Java 系统架构演进的思考
  • Python爬虫——解析_jsonpath
  • 华为发布数字资产继承功能
  • 阿里云NAS文件存储基本介绍与购买使用
  • 大模型使用——超算上部署LLAMA-2-70B-Chat
  • 机器学习笔记：李宏毅ChatGPT课程1：刨析ChatGPT
  • Llama 2 with langchain项目详解（三）
  • 牛客 AB30 排序（快排模板）
  • 【Linux旅行记】第一个小程序“进度条“！
  • DeepMind将AI用于可控核聚变：将等离子体形状模拟精度提高65%
  • Scrum是什么意思，Scrum敏捷项目管理工具有哪些？
  • 【从零单排Golang】第十三话：使用WaitGroup等待多路并行的异步任务
  • WSL2安装CentOS7和CentOS8
  • 不平衡电网条件下基于变频器DG操作的多目标优化研究（Matlab代码Simulink实现）
  • 【Leetcode】（自食用）简单题||单词数
  • C语言代码的x86-64汇编指令分析过程记录
  • 基于springboot+vue的房屋租赁系统(前后端分离)
  • Python文件读写操作详解：从基础到高级
  • ThreadLocal基本介绍