C++初阶之list的使用和模拟以及反向迭代器的模拟实现

news/2024/11/17 9:56:17/

个人主页：点我进入主页

专栏分类：C语言初阶  C语言进阶  数据结构初阶    Linux    C++初阶    算法

欢迎大家点赞，评论，收藏。

一起努力，一起奔赴大厂

一.list简介

        list是一个带头双向链表，在数据结构的时候，我写过关于带头双向循环链表的实现，可以看博客https://yangking.blog.csdn.net/article/details/134495668，我们可以看下面的图，是list的存储结构，

本次的内容包括list的使用，list的模拟实现，list的迭代器以及反向迭代器的原理，模拟实现和使用，最重要的是迭代器和反向迭代器的内容，在前面string和vector中迭代器是原生的指针，但是在这里不是，具体是什么样子的我们可以看后面的内容。 

二.一个简易的list

2.1.单个节点

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

在这里我们可以使用strcut结构体来创建一个节点

2.2.默认构造

void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}
list()
{empty_init();
}

我们创建一个头节点， 让它指向自己。

2.3push_back

void push_back(const T& val)
{Node* newnode = new Node(val);Node* prev = _head._node->_prev;Node* cur = _head._node;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;
}

在这里我们就是简单的插入操作，不给具体的解释。到这里我们简易的list就完成了，我们依次插入1234可以看到

void test()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);
}

三.迭代器

        我们封装一个迭代器的类，我们的迭代器需要支持

list<int>::iterator it = lt1.begin();
while (it != lt1.end())
{cout << *it << " ";++it;
}
cout << endl;

所以我们里面需要包括!=,*it,++it,以及begin和end这些内容，我们需要知道迭代器模仿的是Node*这个行为，我们看一下模拟代码：

template <class T>
struct ListIterator
{typedef ListNode<T>  Node;typedef ListIterator<T> Self;Node* _node;ListIterator(Node* node):_node(node){}bool operator==(const Self& it){return _node == it._node;}bool operator!=(const Self& it){return _node != it._node;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(_node);_node = _node->_prev;return *tmp;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(_node);_node = _node->_next;return tmp;}T& operator*(){return _node->_data;}
};

我们在list类里面加入

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

我们运行测试代码

void test()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);list<int>::iterator it = l.begin();while (it != l.end()){cout << *it << " ";it++;}cout << endl;
}

运行结果为

四.insert和erase以及复用

4.1insert

 在这里我们的insert用迭代器进行插入，给以个位置，插入它的前面，

 我们的代码如下：

void insert(iterator pos, const T& val)
{Node* newnode = new Node(val);Node* prev = pos._node->_prev;Node* cur  = pos._node;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;
}

有了我们的insert我们的push_back可以复用我们的insert，可以改为

void push_back(const T& val)
{insert(end(), val);
}

在这里我们的insert不会造成迭代器失效，因为指针指向的位置不会发生改变，它是插入到pos位置的前面。

4.2erase以及迭代器失效

对于返回值为什么是iterator，这和我们的迭代器失效有关，我们先用void来展示其中的问题。

void erase(iterator pos)
{Node* prev = pos._node->_prev;Node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;_size--;
}

我们的测试代码如下：
 

void test()
{list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);l.push_back(4);list<int>::iterator it = l.begin();while (it != l.end()){if (*it % 2 == 0) l.erase(it);else it++;}it = l.begin();while (it != l.end()){cout << *it << " ";it++;}cout << endl;
}

在这里会出现错误，原因是迭代器失效，野指针的引用，所以我们需要对迭代器进行维护，所以有了返回值，我们改为

iterator erase(iterator pos)
{Node* prev = pos._node->_prev;Node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;_size--;return next;
}

4.3复用

有了这两个，我们的pop_back，pop_front,push_front就可以有了

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

五.operator->（）

        我们的T是一个结构体

struct A
{int a = 1;int b = 2;
};
void test()
{list<A> l;l.push_back({ 1,2 });l.push_back({ 2,3 });l.push_back({ 3,4 });l.push_back({ 4,5 });list<A>::iterator it = l.begin();while (it != l.end()){/*	cout << (*it).a << " " << (*it).b << endl;*/cout << it._node->_data.a << " " << it._node->_data.b << endl;it++;}
}

 我们的解引用是不是看的非常难受，所有我们需要operator一下，

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

 我们改为

cout << it->a << " " << it->b << endl;

六.const迭代器

        有了我们的非const版本的，那么我们就需要我们的const版本的，const版本就是将所有的都复制一份，然后operator*返回const的

template <class T>
struct ListConstIterator
{typedef ListNode<T>  Node;typedef ListConstIterator<T> Self;Node* _node;ListConstIterator(Node* node):_node(node){}bool operator==(const Self& it){return _node == it._node;}bool operator!=(const Self& it){return _node != it._node;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(_node);_node = _node->_prev;return *tmp;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(_node);_node = _node->_next;return tmp;}const T& operator*(){return _node->_data;}const T* operator->(){return &_node->_data;}
};

由于这个会和非fonst很多内容一样，会造成代码冗余，所以我们可以利用模板来简化我们的代码，我们非const的代码函数的返回值为Self，T&,T*，const版本的是Self，const T&，const T*，所以我们可以写成模板

template <class T,class Ref,class Ptr>
struct ListIterator
{typedef ListNode<T>  Node;typedef ListIterator< T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}bool operator==(const Self& it){return _node == it._node;}bool operator!=(const Self& it){return _node != it._node;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(_node);_node = _node->_prev;return *tmp;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(_node);_node = _node->_next;return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}
};

我们在list类里面写入

typedef ListIterator<T,T&,T*> iterator;
typedef ListIterator<T,const T&,const T*> const_iterator;

这样我们由我们自己写改为了编译器去写。

七.反向迭代器

        我们的反向得带起是使用正向迭代器进行写的，它的rbegin是正向迭代器的end，rend是正向迭代器的begin，所以它的operator*是解引用前一个的。

template <class Iterator, class Ref, class Ptr>
struct ReverseIterator
{typedef ReverseIterator<Iterator, Ref, Ptr> Self;Iterator _it;ReverseIterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;--tmp;return *tmp;}Ptr operator->(){return _it.operator->();}Self rbegin(){return ReverseIterator(_it.end());}Self rend(){return ReverseIterator(_it.begin());}Self operator++(){--_it;return *this;}Self operator++(int){Iterator tmp = _it;--_it;return tmp;}Self operator--(){++_it;return *this;}Self operator--(int){Iterator tmp = _it;tmp = _it;++_it;return tmp;}bool operator!=(Self it){return _it != it._it;}};

到这里我们的内容结束了。


http://www.ppmy.cn/news/1456018.html

相关文章

前后端分离项目中的一些疑惑

前后端分离项目中的一些疑惑

1、前后端分离项目&#xff0c;浏览器发起请求后&#xff0c;请求的是前端服务器还是后端服务器&#xff1f; 在前后端分离的项目中&#xff0c;当浏览器发起请求时&#xff0c;它首先会请求的是前端服务器。 前后端分离的工作流程大致如下&#xff1a; 用户在浏览器中输入网…
阅读更多...
实用的Chrome浏览器命令

实用的Chrome浏览器命令

Chrome浏览器是一款功能强大的浏览器&#xff0c;以下是一些实用的Chrome浏览器命令&#xff1a; Ctrl T&#xff1a;打开新标签页。Ctrl Shift T&#xff1a;恢复最近关闭的标签页。Ctrl W&#xff1a;关闭当前标签页。Ctrl L&#xff1a;选中地址栏。Ctrl D&#xff1…
阅读更多...
Java_JVM_JVMs

Java_JVM_JVMs

JVM 官方文档说明文档目录 官方文档 JVM Specification 说明 以Java SE 17为标准 文档目录 2&#xff1a;JVM 结构 class文件数据类型 基本数据类型引用数据类型 运行时数据区 栈帧 其他内容 对象的表示浮点数运算特殊方法 初始化方法【实例、类】多态方法 3&#xff…
阅读更多...
Matlab|考虑不确定性的含集群电动汽车微电网随机优化调度

Matlab|考虑不确定性的含集群电动汽车微电网随机优化调度

目录 主要内容 1.1 集群电动汽车模型 1.2 场景生成与缩减 部分代码 结果一览 下载链接 主要内容 该模型研究的是一种并网型微电网&#xff0c;其中包括分布式电源&#xff08;汽轮机&#xff09;、需求响应负荷&#xff08;可平移负荷&#xff09;、可再生能源…
阅读更多...
偏微分方程算法之混合边界条件下的差分法

偏微分方程算法之混合边界条件下的差分法

目录 一、研究目标 二、理论推导 三、算例实现 四、结论 一、研究目标 我们在前几节中介绍了Poisson方程的边值问题&#xff0c;接下来对椭圆型偏微分方程的混合边值问题进行探讨&#xff0c;研究对象为&#xff1a; 其中&#xff0c;为矩形区域&#xff0c;为上的连续函数…
阅读更多...
银河麒麟服务器系统audit服务组件升级、进程彻底关闭介绍

银河麒麟服务器系统audit服务组件升级、进程彻底关闭介绍

银河麒麟服务器系统audit服务组件升级、进程彻底关闭介绍 一 系统环境二 组件升级2.1 联网升级audit2.1.1 配置外网源&#xff08;默认配置如下&#xff0c;不用修改&#xff09;2.1.2 通过dnf命令进行升级&#xff08;未指定版本的话会升级到最新se.12版本&#xff0c;建议升级…
阅读更多...
01 JVM -- JVM 体系结构、HotSpot

01 JVM -- JVM 体系结构、HotSpot

1. JVM、HotSpot、 OpenJDK 的区别 JVM (Java Virtual Machine) 是一个虚拟机HotSpot 是 JVM 规范的一个实现。HotSpot 虚拟机通过即时编译 (JIT) 技术将 Java 字节码转换为本地机器码&#xff0c;以提高程序的执行效率。OpenJDK 是一个项目名&#xff0c;它在 HotSpot 的基础…
阅读更多...
深度学习中的优化算法：选择现有的还是自创？

深度学习中的优化算法：选择现有的还是自创？

深度学习中的优化算法 深度学习中的优化算法&#xff1a;选择现有的还是自创&#xff1f;现有优化算法的优势**优点包括**&#xff1a; 开发新的优化算法的考虑**开发新算法的原因**&#xff1a;**开发新算法的风险**&#xff1a; 实用建议结论 深度学习中的优化算法&#xff1…
阅读更多...
最新文章

Copyright @ 2022~2023