c++ - list常用接口模拟实现

文章目录

    • 一、模拟list类的框架
    • 二、函数接口实现
      • 1、迭代器接口
      • 2、常用删除、插入接口
      • 3、常用其他的一些函数接口
      • 4、默认成员函数


一、模拟list类的框架

1、使用带哨兵的双向链表实现。
2、链表结点:

// List的结点类
template<class T>
struct ListNode
{ListNode<T>* _pPre; //后继指针ListNode<T>* _pNext; //前驱指针T _val; //数据//构造结点ListNode(const T& val = T()) :_val(val), _pPre(nullptr), _pNext(nullptr){}
};

3、list类的成员变量和构造双向链表的哨兵位结点函数。

 //让哨兵位结点指向自己
typedef ListNode<T> Node;
typedef Node* PNode;void CreateHead(){_pHead = new  Node;_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;}PNode _pHead;   //哨兵位结点

二、函数接口实现

1、迭代器接口

list的迭代器是双向迭代器,支持++、–,但是它们在内存上储存是不连续的,无法简单通过指针去进行++、–操作,所以我们要对list的迭代器进行封装。
(1)list正向迭代器类
成员变量:两个结点指针。

typedef ListNode<T>* PNode;
PNode _pNode;	//结点指针
PNode _P;//保存哨兵位结点指针,用于判断解引用是否访问哨兵位结点

构造函数:

//构造函数 ,获取一个结点指针ListIterator(const PNode & pNode = nullptr, const PNode& const P = nullptr) :_pNode(pNode),_P(P){}

拷贝构造、赋值、析构函数:
因为_pNode的指针指向的内存是有list类释放的,所以该类无需进行资源清理,使用浅拷贝即可,所以拷贝、赋值、析构都使用编译器生成的即可。

重载操作符:

	//Ref为T& Ptr为T*typedef ListIterator<T, Ref, Ptr> Self;//解引用Ref operator*(){assert(_P != _pNode);return _pNode->_val;}//该运算符重载的意义为T为自定义类型时使用,迭代器可以通过该运算符直接访问自定义类型成员Ptr operator->(){return &(_pNode->_val);}//前置++Self& operator++(){_pNode = _pNode->_pNext;return *this;}//后置++Self operator++(int){Self tmp(_pNode);_pNode = _pNode->_pNext;return tmp;}//前置--Self& operator--(){_pNode = _pNode->_pPre;return *this;}//后置--Self& operator--(int){Self tmp(_pNode);_pNode = _pNode->_pPre;return tmp;}//比较bool operator!=(const Self& l){return l._pNode != _pNode;}bool operator==(const Self& l){return l._pNode == _pNode;}

获取成员变量函数:

 //获取该迭代器成员变量PNode get(){return _pNode;}

ListIterator类一览:

//Ref为T& Ptr为T*
template<class T, class Ref, class Ptr>
class ListIterator
{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;
public://构造函数 ,获取一个结点指针ListIterator(const PNode & pNode = nullptr, const PNode& const P = nullptr) :_pNode(pNode),_P(P){}Ref operator*(){assert(_P != _pNode);return _pNode->_val;}Ptr operator->(){return &(operator*());}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self tmp(_pNode);_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){Self tmp(_pNode);_pNode = _pNode->_pPre;return tmp;}bool operator!=(const Self& l){return l._pNode != _pNode;}bool operator==(const Self& l){return l._pNode == _pNode;}PNode get(){return _pNode;}
private:PNode _pNode;PNode _P;
};
};

(2)反向迭代器类
与正向迭代器不一样的有 * 操作符,_pNode保存的是有效元素的下一个位置,如:想要的是_pNode->_pPre指向的元素,但是该迭代器保存的是_pNode的指针,还有++,–与正向迭代器相反。
其他操作与正向迭代器一致。

template<class T, class Ref, class Ptr>
class Reverse_ListIterator
{typedef ListNode<T>* PNode;typedef Reverse_ListIterator<T, Ref, Ptr> Self;
public:Reverse_ListIterator(const PNode& pNode = nullptr, const PNode& const P = nullptr) :_pNode(pNode), _P(P){}Ref operator*(){assert(_P != _pNode ->_pPre);return _pNode->_pPre->_val;}Ptr operator->(){return &(operator*());}Self& operator++(){_pNode = _pNode->_pPre;return *this;}Self operator++(int){Self tmp(_pNode);_pNode = _pNode->_pPre;return tmp;}Self& operator--(){_pNode = _pNode->_pNext;}Self& operator--(int){Self tmp(_pNode);_pNode = _pNode->_pNext;return tmp;}bool operator!=(const Self& l){return l._pNode != _pNode;}bool operator==(const Self& l){return l._pNode == _pNode;}PNode get(){return _pNode;}
private:PNode _pNode;PNode _P;
};

(3)list迭代器接口

//一些类型的重命名typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;typedef Reverse_ListIterator<T, T&, T*> reverse_iterator;typedef Reverse_ListIterator<T, const T&, const T*> reverse_const_iterator;// List Iterator//第一个有效元素位置的迭代器
iterator begin()
{return iterator(_pHead->_pNext,_pHead);
}
//最后一个有效元素位置的下一个位置的迭代器
iterator end()
{return iterator(_pHead,_pHead);
}
//加了const 修饰
const_iterator begin() const
{return const_iterator(_pHead->_pNext,_pHead);
}
const_iterator end()const
{return const_iterator(_pHead,_pHead);
}//反向迭代器
//哨兵位的位置reverse_iterator rbegin(){return reverse_iterator(_pHead,_pHead);}
//第一个有效元素位置reverse_iterator rend(){return reverse_iterator(_pHead ->_pNext,_pHead);}
//加了const修饰reverse_const_iterator rbegin() const{return reverse_const_iterator(_pHead,_pHead);}reverse_const_iterator rend()const{return reverse_const_iterator(_pHead->_pNext,_pHead);}

2、常用删除、插入接口

(1)insert
在迭代器位置前插入一个结点。

// 在pos位置前插入值为val的节点
iterator insert(iterator pos, const T & val)
{//创造一个结点PNode tmp = new Node(val);//获取迭代器中的指针PNode _pos = pos.get();//进行插入PNode prv = _pos->_pPre;prv->_pNext = tmp;tmp->_pPre = prv;tmp->_pNext = _pos;_pos->_pPre = tmp;//返回新迭代器return iterator(tmp);
}

迭代器是否失效:
因为插入新的结点,不会影响到原来的结点,所以该迭代器不会失效。

(2)erase
删除迭代器位置结点。

// 删除pos位置的节点,返回该节点的下一个位置
iterator erase(iterator pos)
{//判断是否为哨兵位结点iterator it = end();assert(pos != it);//获取迭代器结点指针PNode tmp = pos.get();//进行删除PNode next = tmp->_pNext;PNode prv = tmp->_pPre;prv->_pNext = next;next->_pPre = prv;delete tmp;tmp = nullptr;//返回被删除结点的下一个位置的结点迭代器return iterator(next);
}

迭代器是否失效:
因为将结点删除了,所以原本的迭代器是不能使用的,所以迭代器失效了。

(3)push_back、pop_back、push_front、pop_front
这里的头插、尾插、头删、尾删均复用上面两个函数接口。

void push_back(const T & val) { insert(end(), val); }
void pop_back() { erase(--end()); }
void push_front(const T & val) { insert(begin(), val); }
void pop_front() { erase(begin()); }

3、常用其他的一些函数接口

(1)size
返回大小,通过遍历链表即可找到。

size_t size()const
{//保存哨兵位的下一个位置PNode tmp = _pHead->_pNext;//开始遍历size_t count = 0;while (tmp != _pHead){tmp = tmp->_pNext;++count;}return count;
}

(2)empty
是否为空,判断哨兵位结点是否指向自己即可。

bool empty()const
{return _pHead == _pHead->_pNext;
}

(3)clear
清空链表,遍历链表逐个清空,保留哨兵位结点,再让哨兵位结点自己连接自己。

  void clear(){//保存有效结点位置PNode tmp = _pHead->_pNext;//遍历删除while (tmp != _pHead){PNode p = tmp->_pNext;delete tmp;tmp = p;}//重新指向_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;

(4)swap
交换,只需要交换指向哨兵位结点的指针即可。
在这里插入图片描述

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

(4)front
获取第一个位置的元素。

T& front()
{assert(!empty());return _pHead->_pNext->_val;
}
const T& front()const
{assert(!empty());return _pHead->_pNext->_val;
}

(5)back
获取最后一个位置元素。

T& back()
{assert(!empty());return _pHead->_pPre->_val;
}
const T& back()const
{assert(!empty());return _pHead->_pPre->_val;
}

4、默认成员函数

(1)构造函数
构造函数都会先进行构造哨兵位结点,再进行下面的操作,除了无参构造,其他都复用了尾插,将元素尾插到链表结尾。

//无参构造
list() 
{   //构造一个哨兵位结点CreateHead(); 
}//利用n个val值进行构造
list(int n, const T& value = T())
{//构造一个哨兵位结点CreateHead();//将元素尾插入while (n != 0){push_back(value);--n;}
}//这里用迭代器区间构造,重写一个模板,使其可以使用其他容器的迭代器
template <class Iterator>
list(Iterator first, Iterator last)
{//构造一个哨兵位结点CreateHead();//将元素尾插入while (first != last){push_back(*first);++first;}
}//拷贝构造
list(const list<T>& l)
{//构造一个哨兵位结点CreateHead();//遍历+将元素尾插入PNode tmp = l._pHead->_pNext;while (tmp != l._pHead){push_back(tmp->_val);tmp = tmp->_pNext;}
}

(2)重载赋值运算符
通过传值传参构造一个临时容器 l ,再将其与原来的容器交换,当出了函数作用域之后临时容器就会调用析构函数,对临时容器的资源进行清理(就是原来容器的资源)。

list<T>& operator=(list<T> l)
{//与临时变量进行交换swap(l);return *this;
}

(3)析构函数
对链表清理。

~list()
{//清空链表clear();//删除哨兵位结点delete _pHead;_pHead = nullptr;
}

三、总代码

#pragma once
#include<iostream>
#include<assert.h>
#include<string>
using namespace std;namespace xu
{// List的结点类template<class T>struct ListNode{ListNode<T>* _pPre; //后继指针ListNode<T>* _pNext; //前驱指针T _val; //数据//构造结点ListNode(const T& val = T()) :_val(val), _pPre(nullptr), _pNext(nullptr){}};//List的正向迭代器类//Ref为T& Ptr为T*template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public://构造函数 ,获取一个结点指针ListIterator(PNode pNode = nullptr) :_pNode(pNode){}Ref operator*(){return _pNode->_val;}Ptr operator->(){return &(operator*());}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self tmp(_pNode);_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){Self tmp(_pNode);_pNode = _pNode->_pPre;return tmp;}bool operator!=(const Self& l){return l._pNode != _pNode;}bool operator==(const Self& l){return l._pNode == _pNode;}PNode get(){return _pNode;}private:PNode _pNode;};//List的反向迭代器类template<class T, class Ref, class Ptr>class Reverse_ListIterator{typedef ListNode<T>* PNode;typedef Reverse_ListIterator<T, Ref, Ptr> Self;public:Reverse_ListIterator(PNode pNode = nullptr) :_pNode(pNode){}Ref operator*(){return _pNode->_pPre->_val;}Ptr operator->(){return &(operator*());}Self& operator++(){_pNode = _pNode->_pPre;return *this;}Self operator++(int){Self tmp(_pNode);_pNode = _pNode->_pPre;return tmp;}Self& operator--(){_pNode = _pNode->_pNext;}Self& operator--(int){Self tmp(_pNode);_pNode = _pNode->_pNext;return tmp;}bool operator!=(const Self& l){return l._pNode != _pNode;}bool operator==(const Self& l){return l._pNode == _pNode;}PNode get(){return _pNode;}private:PNode _pNode;};//list类template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;typedef Reverse_ListIterator<T, T&, T*> reverse_iterator;typedef Reverse_ListIterator<T, const T&, const T*> reverse_const_iterator;public://默认构造list() {   //构造一个哨兵位结点CreateHead(); }list(int n, const T& value = T()){//构造一个哨兵位结点CreateHead();//将元素尾插入while (n != 0){push_back(value);--n;}}template <class Iterator>list(Iterator first, Iterator last){//构造一个哨兵位结点CreateHead();//将元素尾插入while (first != last){push_back(*first);++first;}}list(const list<T>& l){//构造一个哨兵位结点CreateHead();//遍历+将元素尾插入PNode tmp = l._pHead->_pNext;while (tmp != l._pHead){push_back(tmp->_val);tmp = tmp->_pNext;}}list<T>& operator=(list<T> l){//与临时变量进行交换swap(l);return *this;}~list(){//清空链表clear();//删除哨兵位结点delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return iterator(_pHead->_pNext);}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead->_pNext);}const_iterator end()const{return const_iterator(_pHead);}reverse_iterator rbegin(){return reverse_iterator(_pHead);}reverse_iterator rend(){return reverse_iterator(_pHead ->_pNext);}reverse_const_iterator rbegin() const{return reverse_const_iterator(_pHead);}reverse_const_iterator rend()const{return reverse_const_iterator(_pHead->_pNext);}///// List Capacitysize_t size()const{PNode tmp = _pHead->_pNext;size_t count = 0;while (tmp != _pHead){tmp = tmp->_pNext;++count;}return count;}bool empty()const{return _pHead == _pHead->_pNext;}// List AccessT& front(){assert(!empty());return _pHead->_pNext->_val;}const T& front()const{assert(!empty());return _pHead->_pNext->_val;}T& back(){assert(!empty());return _pHead->_pPre->_val;}const T& back()const{assert(!empty());return _pHead->_pPre->_val;}// List Modifyvoid push_back(const T & val) { insert(end(), val); }void pop_back() { erase(--end()); }void push_front(const T & val) { insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T & val){//创造一个结点PNode tmp = new Node(val);//获取迭代器中的指针PNode _pos = pos.get();//进行插入PNode prv = _pos->_pPre;prv->_pNext = tmp;tmp->_pPre = prv;tmp->_pNext = _pos;_pos->_pPre = tmp;//返回新迭代器return iterator(tmp);}// 删除pos位置的节点,返回该节点的下一个位置iterator erase(iterator pos){//判断是否为哨兵位结点iterator it = end();assert(pos != it);//获取迭代器结点指针PNode tmp = pos.get();//进行删除PNode next = tmp->_pNext;PNode prv = tmp->_pPre;prv->_pNext = next;next->_pPre = prv;delete tmp;tmp = nullptr;//返回被删除结点的下一个位置的结点迭代器return iterator(next);}void clear(){//保存有效结点位置PNode tmp = _pHead->_pNext;//遍历删除while (tmp != _pHead){PNode p = tmp->_pNext;delete tmp;tmp = p;}//重新指向_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;}void swap(list<T>& l){std::swap(_pHead, l._pHead);}private://让哨兵位结点指向自己void CreateHead(){_pHead = new  Node;_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;}PNode _pHead;   //哨兵位结点};};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Docker之路(三)docker安装nginx实现对springboot项目的负载均衡

Docker之路&#xff08;三&#xff09;dockernginxspringboot负载均衡 前言&#xff1a;一、安装docker二、安装nginx三、准备好我们的springboot项目四、将springboot项目分别build成docker镜像五、配置nginx并且启动六、nginx的负载均衡策略七、nginx的常用属性八、总结 前言…

Android WebView上传文件/自定义弹窗技术,附件的解决方案

安卓内核开发 其实是Android的webview默认是不支持<input type"file"/>文件上传的。现在的前端页面需要处理的是&#xff1a; 权限 文件路径AndroidManifest.xml <uses-permission android:name"android.permission.WRITE_EXTERNAL_STORAGE"/&g…

计算机网络ppt和课后题总结(上)

试在下列条件下比较电路交换和分组交换。要传送的报文共 x(bit)。从源点到终点共经过 k 段链路&#xff0c;每段链路的传播时延为 d(s)&#xff0c;数据率为 b(b/s)。在电路交换时电路的建立时间为 s(s)。在分组交换时分组长度为 p(bit)&#xff0c;且各结点的排队等待时间可忽…

数据觉醒时代,以“存力”激活数据资产潜能

近日&#xff0c;质汇“杨数浦”主题研讨会首场活动在杨浦滨江举行&#xff0c;是杨浦区筹推进数字经济与城市数字化发展的一大重要举措&#xff0c;各行业协会、科研院所及企业代表参加活动&#xff0c;共商行业发展新机遇。活动现场&#xff0c;优刻得董事长兼CEO季昕华被授予…

Mysql的两种安装方式

文章目录 第一种安装方式国内镜像库下载解压安装配置环境变量初始化数据库安装mysql登录mysql设置root密码退出登录假如忘记了密码&#xff0c;重置密码的步骤1、步骤一&#xff1a;停止 MySQL 服务2、步骤二&#xff1a;使用安全模式启动 MySQL3、步骤三&#xff1a;重置密码4…

大数据之Schedule调度错误(一)

当我们在利用ooize发起整个任务的调度过程中,如果多个调度任务同时运行并且多个调度任务操作了相同的表,那么就会出现如下的错误关系: Invalid path hdfs://iZh5w01l7f8lnog055cpXXX:8000/user/admin/xxx: No files matching path hdfs://iZh5w01l7f8lnog055cpXXX:8000/user/ad…

线性表、单循环链表学习

背景&#xff1a; 单循环链表是一种链表结构&#xff0c;其中最后一个节点指向第一个节点&#xff0c;从而形成一个环。 实现单循环链表通常涉及节点定义、插入节点、删除节点以及遍历链表等操作。以下是如何在Python中实现单循环链表的示例。 单循环链表的实现 1. 节点类 …

掌握ChatGPT的正确打开方式

引言 随着人工智能技术的飞速发展&#xff0c;自然语言处理&#xff08;NLP&#xff09;领域取得了显著的突破。其中&#xff0c;聊天生成预训练变换器&#xff08;ChatGPT&#xff09;作为一种新型的对话式AI模型&#xff0c;引起了广泛关注。本文将详细介绍ChatGPT的正确使用…

使用html2canvas和jspdf导出pdf包含跨页以及页脚

首先要下载两个文件&#xff0c;一个为html2canvas.min.js&#xff0c;另一个是jspdf.umd.min.js这两个文件分别下载的地址我也附录上&#xff0c;都在官网git&#xff1a; html2canvas.min.js: https://html2canvas.hertzen.com/dist/html2canvas.min.js jspdf.umd.min.js: …

vue-pdf 部分中文显示错误,第二次打开是空白,解决方法

首先鸣谢 1. https://blog.csdn.net/m0_71537867/article/details/131614868?spm1001.2014.3001.5506 2. https://blog.csdn.net/weixin_43763952/article/details/133769647 3. https://github.com/FranckFreiburger/vue-pdf/issues/229 4. https://blog.csdn.net/weixin_449…

康谋技术 | 自动驾驶:揭秘高精度时间同步技术(一)

众所周知&#xff0c;在自动驾驶中&#xff0c;主要涵盖感知、规划、控制三个关键的技术层面。在感知层面&#xff0c;单一传感器采集外界信息&#xff0c;各有优劣&#xff0c;比如摄像头采集信息分辨率高&#xff0c;但是受外界条件影响较大&#xff0c;一般缺少深度信息&…

推荐一个免费的相亲工具

推荐一个免费的相亲工具&#xff0c;步骤如下&#xff1a; 1&#xff09;微信里面搜索公众号“光源桥”&#xff0c;并关注 2&#xff09;输入搜索条件进行搜索对象 例如下面搜索&#xff1a;

Pinterest免费引流实操演示

这篇文章中你将了解到 1.Pinterest网站介绍&#xff0c;用户群体&#xff0c;适合做什么品类。 2.现在的商家都在上面做什么&#xff1f;案例展示。 3.我们在这个站免费引流要怎么做以及注意事项。 1.Pinterest网站介绍&#xff0c;用户群体&#xff0c;适合做什么品类。 P…

【Excel】Excel中将日期格式转换为文本格式,并按日期显示。

【问题需求】 在使用excel进行数据导入的过程中&#xff0c; 有的软件要求日期列必须是文本格式。 但是直接将日期列的格式改为文本后&#xff0c;显示一串数字&#xff0c;而不按日期显示。 进而无法导入使用。 【解决方法】 使用【TXET】函数公式进行处理&#xff0c; 在单…

百度ERNIE系列预训练语言模型浅析(4)-总结篇

总结&#xff1a;ERNIE 3.0与ERNIE 2.0比较 &#xff08;1&#xff09;相同点&#xff1a; 采用连续学习 采用了多个语义层级的预训练任务 &#xff08;2&#xff09;不同点&#xff1a; ERNIE 3.0 Transformer-XL Encoder(自回归自编码), ERNIE 2.0 Transformer Encode…

泛微开发修炼之旅--05Ecode入门讲解、接口调用源码示例及踩坑总结

文章链接&#xff1a;泛微开发修炼之旅--05Ecode入门讲解、接口调用源码示例及踩坑总结

操作系统复习-linux的进程管理

linux的进程管理 linux进程的相关概念 进程的类型 前台进程 前台进程就是具有终端&#xff0c;可以和用户交互的进程&#xff0c;会占用终端shell&#xff0c;不可以输入其他的命令。 后台进程 前台进程就是具有终端&#xff0c;可以和用户交互的进程。 不会占用终端shell&a…

数据分析必备:一步步教你如何用Pandas做数据分析(17)

1、Pandas 连接 Pandas 连接的操作实例 Pandas具有与SQL等关系数据库非常相似的功能齐全的高性能内存中连接操作。 Pandas提供单个功能merge作为DataFrame对象之间所有标准数据库联接操作的入口点 pd.merge(left, right, howinner, onNone, left_onNone, right_onNone,left_i…

实战|基于YOLOv10与MobileSAM实现目标检测与分割【附完整源码】

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…

[240605] FreeBSD 发布 v14.1 | ChatGPT 出现故障,部分用户无法使用

目录 FreeBSD 发布 v14.1ChatGPT 出现故障&#xff0c;部分用户无法使用 FreeBSD 发布 v14.1 一、概述 FreeBSD 项目发布了 FreeBSD 14.1-RELEASE&#xff0c;这是 stable/14 分支的第二个稳定版本。 二、主要更新 C 库在 amd64 架构上实现了 SIMD 字符串和内存操作&#x…