C++ STL->list模拟实现


theme: smartblue

list
list文档

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
  2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向 其前一个元素和后一个元素。
  3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高 效。
  4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率 更好。
    5.与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list 的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间 开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)

list类的函数接口

namespace ding
{
	//结点类
	template<class T>
	struct _list_node
	{
         //构造函数
		_list_node(const T& val = T());

		T _data;                 
		_list_node<T>* _next;   
		_list_node<T>* _prev;   
	};
	//迭代器类
	template<class T, class Ref, class Ptr>
	struct _list_iterator
	{
		typedef _list_node<T> node;
		typedef _list_iterator<T, Ref, Ptr> self;
		//构造函数
		_list_iterator(node* pnode);  

		
		self operator++();
		self operator--();
		self operator++(int);
		self operator--(int);
		bool operator==(const self& s) const;
		bool operator!=(const self& s) const;
		Ref operator*();
		Ptr operator->();

		//成员变量
		node* _pnode;
	};

	//list类
	template<class T>
	class list
	{
	public:
		typedef _list_node<T> node;
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

		//Member functions
		list();
		list(const list<T>& lt);
		list<T>& operator=(const list<T>& lt);
		~list();

		//Iterators:
		iterator begin();
		iterator end();
		const_iterator begin() const;
		const_iterator end() const;

		//Element access:
		T& front();
		T& back();
		const T& front() const;
		const T& back() const;

		//Modifiers:
		void insert(iterator pos, const T& x);
		iterator erase(iterator pos);
		void push_back(const T& x);
		void pop_back();
		void push_front(const T& x);
		void pop_front();

		//Capacity:
		size_t size() const;
		void resize(size_t n, const T& val = T());
		void clear();
		bool empty() const;
		void swap(list<T>& lt);

	private:
		node* _head; 
	};
}

结点类的实现

list底层采用了带头双向循环链表的结构实现。

image.png
在实现list前,需要定义出一个一个结点出来。直接定义一个结点类,让结点类完成结点的构造即可。

template<class T>
struct _list_node
{
        _list_node(const T& val = T())
                :_data(val)
                ,_next(nullptr)
                ,_prev(nullptr)
        {}
        T _data;
        _list_node<T>* _next;
        _list_node<T>* _prev;
};

迭代器类的实现

  • list底层物理空间不再连续,不再支持[]+下标的方式进行访问

image.png

  • 只能用迭代器进行访问
  • list迭代器的实现不能再像string或者vector那种底层物理空间连续的容器使用原生指针进行实现。
  • 底层空间连续,使用原生指针实现,指针自增或者自减就可以访问到对应的元素,而list由于底层物理空间不来连续的原因,不能再使用原生指针

解决方法

  • 定义一个迭代器类,迭代器相关的操作(比如++,!=,*)等操作但都在迭代器类中重载

结合之前string类和vector类的实现得知迭代器要么就是原生指针,要么就是自定义类型对原生指针的一种封装,去模拟指针的行为。比如对结点指针自增就能指向下一个结点

构造函数

迭代器就是对结点指针进行封装,这里只需要一个结点指针成员变量即可。

_list_iterator(node* node)
{
    _node = node;
}

++运算符重载

self operator++()
{
    _node = _node->_next;
    return *this;
}
self operator++(int)
{
    self tmp(*this);
    _node = _node->_next;
    return tmp;
}
  • 这里的self是经过typedef后的typedef _list_iterator<T, Ref, Ptr> self就是迭代器类类型
  • 前置++与后置++重载语法规定后置++的形参必须为int。
  • 后置++先记录一下当前结点,再让结点指向后一个,返回自增前的即可。

–运算符重载

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

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

*运算符重载

解引用操作符,是想拿到地址的内容,直接返回当前结点的数据内容即可。

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

注意
这里的返回值是Ref,在定义迭代器类是时候定义了三个模板参数,T就是指定的类型,Ref则是指定类型的引用类型,也就是T&,Ptr则是指定类型的指针类型,也就是T*。
在list的实现中,

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
  • STL底层源码就是这样设计的,主要就是为了解决const迭代器的问题,如果不用模板解决的话,可以在定义一个const iterator类也可以解决问题,但是在实现以一个const迭代器与普通迭代器的区别就仅仅只是*返回值类型不一样而已,利用模板参数解决更妙。
  • 普通迭代器返回T&类型,const迭代器返回const T&类型。
  • 这里返回引用类型,主要是因为解引用后可能需要对数据进行修改。

!= && ==

迭代器经常需要进行判断两个迭代器是否相等不相等的操作,这里这需要判断两个迭代器中的结点是否相等即可,不需要做其他操作,定义出成const更为合理。

bool operator==(const self& s) const
{
    return _node == s._node;
}
bool operator!=(const self& s) const
{
    return _node != s._node;
}

->操作符重载

这个操作符对于迭代器类型并不是很常用,但是为了模拟指针的行为,指针有->操作符,迭代器就模拟实现了。

运算符 -> 必须是一个成员函数。如果使用了 -> 运算符,返回类型必须是指针或者是类的对象。也就是这里返回值必须是Ptr 指定类型T*类型。

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

使用->场景:
当list中存放的是自定义类型,

class Date
{
public:
    Date(int year)
    {
            _year = year;
    }
    int _year = 0;
};
int main()
{
    std::list<Date>lt;
    lt.push_back(2023);
    lt.push_back(2024);
    auto it = lt.begin();
    cout << it->_year << endl;
    return 0;
}

可以使用->访问类的成员变量。

list类的实现

Member functions

构造函数

list()
{
    _head = new node;
    _head->_prev = _head;
    _head->_next = _head;
}

这里的node是经过typedef得。typedef _list_node<T> node;对结点类起的别名
构造一个链表即可,这里得空链表是需要一个头节点得。并且让自己指向自己。

image.png

拷贝构造

申请一个新的头结点,再将源容器中的数据依次尾插到新容器中即可

list(const list<T>& lt)
{
    _head = new node;
    _head->_next = _head;
    _head->_prev = _head;
    for (auto val : lt)
    {
            push_back(val);
    }
}

赋值运算符重载

  • 将原来容器中的数据清空,在依次尾插新元素即可
  • 注意要判断是否自己给自己赋值,不能自己给自己赋值,自己给自己赋值clear后数据丢失了
list<T>& operator=(const list<T>& lt)
{
    if (this != &lt)
    {
            clear();
            for (const auto e : lt)
            {
                    push_back(e);
            }
    }
    return *this;
}

迭代器构造

template<class InputIterator>
list(InputIterator first, InputIterator last)
{
    _head = new node;
    _head->_prev = _head;
    _head->_next = _head;
    while (first != last)
    {
            push_back(*first);
            ++first;
    }
}

析构函数

先清空容器在释放头节点即可

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

clear函数

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

Iterators

begin && end

begin函数返回的是第一个有效数据的迭代器,end函数返回的是最后一个有效数据的下一个位置的迭代器
底层是双向循环链表实现的,所以头结点的下一个就是gebin,头节点就是end。

image.png

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

Modifiers

insert

在pos位置前面插入一个结点

image.png

void insert(iterator pos, const T& x)
{
    node* newnode = new node(x);//创建新结点
    node* cur = pos._node;//pos位置的结点指针
    node* prev = cur->_prev;//pos前一个
    //连接关系
    prev->_next = newnode;
    newnode->_prev = prev;
    newnode->_next = cur;
    cur->_prev = newnode;
}

push_back && push_front

  • 尾插 && 头插
  • 在链表的尾部插入一个结点 && 在链表的头部插入一个结点
  • 有了insert和迭代器,直接函数复用即可
//尾插
void push_back(const T& x)
{
        insert(end(), x);
}
//头插
void push_front(const T& x)
{
    insert(begin(), x);
}

eraser

删除pos位置的结点

image.png

iterator erase(iterator pos)
{
    node* cur = pos._node;//当前结点指针
    node* prev = cur->_prev;//pos位置前一个结点
    node* next = cur->_next;//pops位置后一个结点
    //连接关系
    prev->_next = next;
    next->_prev = prev;
    //释放删除的结点
    delete cur;

    return iterator(next);//防止迭代器失效,返回pos位置下一个迭代器
}

pop_back && pop_front

  • 尾删和头删
  • 复用迭代器和rease即可
  • end是头节点,尾删时需要–end() 才是尾部结点
void pop_back()
{
    erase(--end());
}

void pop_front()
{
    erase(begin());
}

Capacity

size

  • 求容器元素个数
  • 遍历容器求个数(效率太低不推荐)
size_t size() const
{
    size_t size = 0;
    auto it = begin();
    while (it != end())
    {
            size++;
            it++;
    }
    return size;
}
  • 在定义一个成员变量统计元素个数(以空间换时间,更推荐)

clear

  • 清空list中的结点,除了头结点。
  • 利用迭代器遍历尾删即可
void clear()
{
    auto it = begin();
    while (it != end())
    {
            pop_back();
    }
}

empty

bool empty() const
{
    return _head->_next;
}

resize

  • 扩容加初始化函数
  • resize规则
  • 若当前容器的size小于所给n,则尾插结点,直到size等于n为止。
  • 若当前容器的size大于所给n,则只保留前n个有效数据。
void resize(size_t n, const T& val = T())
{
    size_t sz = size();
    if (sz < n)//扩容
    {
            for (; sz < n; ++sz)
            {
                    push_back(val);
            }
    }
    else//不扩容
    {
            if (sz > n)//缩容
            {
                    int len = sz - n;
                    cout << len << endl;
                    while (len--)
                    {
                            pop_back();
                    }
            }
    }

}

swap函数

交换两个容器的头指针即可

void swap(list<T>& lt)
{
    std::swap(_head, lt._head);
}

参考源码

  • gitee 码云 - 开源中国
  • 欢迎在评论区提出问题或留下你的观点

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/390712.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

solara,好用的 Python 太阳能系统的建模库!

🏷️个人主页:鼠鼠我捏,要死了捏的主页 🏷️付费专栏:Python专栏 🏷️个人学习笔记,若有缺误,欢迎评论区指正 前言 大家好,今天为大家分享一个超级厉害的 Python 库 - solara。 Github地址:https://github.com/widgetti/solara 在可持续能源领域,太阳能是一种…

Github 2024-02-17 开源项目日报 Top10

根据Github Trendings的统计&#xff0c;今日(2024-02-17统计)共有10个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量Python项目4TypeScript项目3Rust项目2Jupyter Notebook项目1PowerShell项目1JavaScript项目1 Black&#xff…

linux系统---防火墙

目录 一、防火墙的认识 1.防火墙定义 2.防火墙分类 二、Linux系统防火墙 1.Netfilter 2.防火墙工具介绍 2.1iptables 2.2firewalld 2.3nftables 2.4netfilter的五个勾子函数和报文流向 2.4.1五个勾子 2.4.2三种报文流向 3.iptables 3.1iptables概述 3.2iptables…

移动WEB开发知识总结

浏览器现状 PC端常见浏览器 360浏览器、谷歌浏览器、火狐浏览器、QQ浏览器、百度浏览器、搜狗浏览器、IE浏览器。 移动端常见浏览器 UC浏览器&#xff0c;QQ浏览器&#xff0c;欧朋浏览器&#xff0c;百度手机浏览器&#xff0c;360安全浏览器&#xff0c;谷歌浏览器&#xf…

TenorFlow多层感知机识别手写体

文章目录 数据准备建立模型建立输入层 x建立隐藏层h1建立隐藏层h2建立输出层 定义训练方式建立训练数据label真实值 placeholder定义loss function选择optimizer 定义评估模型的准确率计算每一项数据是否正确预测将计算预测正确结果&#xff0c;加总平均 开始训练画出误差执行结…

微信网页版能够使用(会顶掉微信app的登陆)

一、文件结构 新建目录chrome新建icons&#xff0c;其中图片你自己找吧新建文件manifest.json新建文件wx-rules.json 二、文件内容 对应的png你们自己改下 1、manifest.json {"manifest_version": 3,"name": "wechat-need-web","author…

揭开Markdown的秘籍:引用|代码块|超链接

&#x1f308;个人主页&#xff1a;聆风吟 &#x1f525;系列专栏&#xff1a;Markdown指南、网络奇遇记 &#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 文章目录 &#x1f4cb;前言一. ⛳️Markdown 引用1.1 &#x1f514;引用1.2 &#x1f514;嵌套引用1.3 &…

网络原理-TCP_IP(6)

网络层 在复杂的网络环境中确定一个合适的路径. IP协议 与TCP协议并列,都是网络体系中最核心的协议. 基本概念 主机:配有IP地址,但是不进行路由控制的设备; 路由器:即配有IP地址,又能进行路由控制; 节点:主机和路由器的统称; 协议头格式 4位版本号(version):指定IP协议的版…

Vue的一些基础设置

1.浏览器控制台显示Vue 设置找到扩展&#xff0c;搜索Vue 下载这个 然后 点击扩展按钮 点击详细信息 选择这个&#xff0c;然后重启一下就好了 ——————————————————————————————————————————— 2.优化工程结构 src的components里要…

wayland(xdg_wm_base) + egl + opengles 纹理贴图进阶实例(四)

文章目录 前言一、使用gstreamer 获取 pattern 图片二、代码实例1. pattern 图片作为纹理数据源的代码实例1.1 基于opengles2.0 接口的 egl_wayland_texture2_1.c1.2 基于opengles3.0 接口的 egl_wayland_texture3_1.c2. xdg-shell-client-protocol.h 和 xdg-shell-protocol.c3…

IDEA中的神仙插件——Smart Input (自动切换输入法)

IDEA中的神仙插件——Smart Input &#xff08;自动切换输入法&#xff09; 设置 更多功能详见官方文档&#xff1a;Windows版SmartInput使用入门

面试经典150题——串联所有单词的子串(困难)

"Opportunities dont happen, you create them." ​ - Chris Grosser 1. 题目描述 2. 题目分析与解析 2.1 思路一——暴力求解 遇见这种可能刚开始没什么思路的问题&#xff0c;先试着按照人的思维来求解该题目。对于一个人来讲&#xff0c;我想要找到 s 字符串中…

Hive拉链表设计、实现、总结

水善利万物而不争&#xff0c;处众人之所恶&#xff0c;故几于道&#x1f4a6; 文章目录 环境介绍实现1. 初始化拉链表2. 后续拉链表数据的更新 总结彩蛋 - 想清空表的数据&#xff1a;转成内部表&#xff0c;清空数据后&#xff0c;再转成外部表&#xff0c;将分区目录删掉&am…

无心剑英译仓央嘉措《永在我心》

永在我心 Forever in My Heart 仓央嘉措 By Tsangyang Gyatso 这么多年 你一直在我心口幽居 我放下过天地 放下过万物 却从未放下过你 so many years slipped away you’ve been living in my heart I’ve dropped heaven and earth even dropped everything but never dr…

OWASP TOP10

OWASP TOP10 OWASP网址&#xff1a;http://ww.owasp.org.cn A01&#xff1a;失效的访问控制 例如&#xff1a;越权漏洞 案例1&#xff1a; 正常&#xff1a;每个人登录教务系统&#xff0c;只能查询自己的成绩信息 漏洞&#xff1a;张三登录后可以查看自己的成绩 例如&…

人工智能学习与实训笔记(五):神经网络之推荐系统处理

目录 ​​​​​​​七、智能推荐系统处理 7.1 常用的推荐系统算法 7.2 如何实现推荐​​​​​​​ 7.3 基于飞桨实现的电影推荐模型 7.3.1 电影数据类型 7.3.2 数据处理 7.3.4 数据读取器 7.3.4 网络构建 7.3.4.1用户特征提取 7.3.4.2 电影特征提取 7.3.4.3 相似度…

智能网卡(SmartNIC):增强网络性能

在当今的数字时代&#xff0c;网络性能和数据安全是各行各业面临的关键挑战。智能网卡是一项颠覆性的技术创新&#xff0c;对增强网络性能和加强数据安全性具有关键推动作用。本文旨在探讨智能网卡的工作原理及其在不同应用场景中的重要作用。 什么是智能网卡&#xff1f; 智…

Rust 基本环境安装

rust 基本介绍请看上一篇文章&#xff1a;rust 介绍 rustup 介绍 rustup 是 Rust 语言的安装器和版本管理工具。通过 rustup&#xff0c;可以轻松地安装 Rust 编译器&#xff08;rustc&#xff09;、标准库和文档。它也允许你切换不同的 Rust 版本或目标平台&#xff0c;以及…

太以假乱真了,大家小心

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

.NET Core MongoDB数据仓储和工作单元模式封装

前言 上一章我们把系统所需要的MongoDB集合设计好了&#xff0c;这一章我们的主要任务是使用.NET Core应用程序连接MongoDB并且封装MongoDB数据仓储和工作单元模式&#xff0c;因为本章内容涵盖的有点多关于仓储和工作单元的使用就放到下一章节中讲解了。仓储模式&#xff08;R…