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

探索C嘎嘎的奇妙世界:第十九关---STL(list的模拟实现)

news 来源：原创 2024/9/20 11:56:39

1. 基本框架

首先，我们先从节点的准备工作入手，请看示例：        

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
//节点
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& data = T()):_next(nullptr), _prev(nullptr), _data(data){}
};

在上述代码中：先定义一个双向链表的节点结构ListNode。节点结构ListNode包含以下成员变量：
        1. _next：指向下一个节点的指针。
        2. _prev：指向上一个节点的指针。
        3. _data：存储节点数据的变量。

        节点结构ListNode还包含一个构造函数，用于初始化成员变量。构造函数接受一个参数data，用于初始化_data成员变量。如果没有提供参数，则_data成员变量的默认值为T()，即T类型的默认构造函数的返回值。

        该头文件还使用了iostream和assert.h两个标准头文件，并使用了std命名空间。

2. 封装迭代器

请看示例代码：

	//迭代器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){}// ++it;Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};

在上述代码中：定义了一个迭代器结构ListIterator，用于遍历双向链表。迭代器结构ListIterator包含以下成员变量和成员函数：
成员变量： _node：指向当前迭代器所指向的节点的指针。

成员函数如下：
        1. 构造函数：接受一个参数node，用于初始化迭代器的节点指针。
        2. 前置递增运算符（++it）：将迭代器指向下一个节点，并返回自身的引用。
        3. 前置递减运算符（--it）：将迭代器指向上一个节点，并返回自身的引用。
        4. 后置递增运算符（it++）：将迭代器指向下一个节点，并返回之前的迭代器的副本。
        5. 后置递减运算符（it--）：将迭代器指向上一个节点，并返回之前的迭代器的副本。
        6. 解引用运算符（*）：返回迭代器指向节点的数据的引用。
        7. 成员访问运算符（->）：返回迭代器指向节点数据的指针。
        8. 不等于运算符（!=）：判断当前迭代器是否与另一个迭代器不相等。
        9. 等于运算符（==）：判断当前迭代器是否与另一个迭代器相等。

迭代器结构ListIterator还使用了两个类型别名：
        1. Node：表示节点类型ListNode<T>。
        2. Self：表示迭代器自身类型ListIterator<T, Ref, Ptr>。

3. 迭代器和构造函数

请看示例代码：

	template<class T>class list{typedef ListNode<T> Node;public:// 不符合迭代器的行为，无法遍历//typedef Node* iterator;//typedef ListIterator<T> iterator;//typedef ListConstIterator<T> const_iterator;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin(){//iterator it(_head->_next);//return it;return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}list(){_head = new Node();_head->_next = _head;_head->_prev = _head;}

该部分定义了一个双向链表类list。

list类包含以下成员变量和成员函数：
        1. typedef Node：类型别名，表示节点类型ListNode<T>。
        2. typedef iterator：类型别名，表示迭代器类型ListIterator<T, T&, T*>。
        3. typedef const_iterator：类型别名，表示常量迭代器类型ListIterator<T, const T&, const T*>。

成员函数如下：
        1. begin()：返回头节点的下一个节点的迭代器，用于遍历链表。
        2. begin() const：返回头节点的下一个节点的常量迭代器，用于遍历常量链表。
        3. end()：返回头节点的迭代器，用于判断迭代结束。
        4. end() const：返回头节点的常量迭代器，用于判断常量迭代结束。
        5. 构造函数：初始化头节点，将头节点的_next和_prev指向自身。

注意：由于ListIterator的设计不符合迭代器的行为，无法进行迭代，所以在list类中注释掉了typedef iterator和typedef const_iterator的定义。

3. push_back、pop_back、push_front和pop_front

请看示例代码：

void push_back(const T& x)
{/*Node* newnode = new Node(x);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;*/insert(end(), x);
}void pop_back()
{erase(--end());
}void push_front(const T& x)
{insert(begin(), x);
}void pop_front()
{erase(begin());
}

这部分代码实现了list类的push_back、pop_back、push_front和pop_front成员函数。

        1. push_back：在链表末尾添加一个节点。首先创建一个新的节点newnode，然后获取链表末尾的节点tail，将tail的_next指向newnode，newnode的_prev指向tail，newnode的_next指向头节点_head，头节点的_prev指向newnode。最后调用insert函数，在末尾迭代器的位置插入新节点。
        2. pop_back：删除链表末尾的节点。首先获取链表末尾节点的前一个节点，然后调用erase函数，将末尾迭代器的前一个位置的节点删除。
        3. push_front：在链表开头添加一个节点。调用insert函数，在开头迭代器的位置插入新节点。
        4. pop_front：删除链表开头的节点。调用erase函数，将开头迭代器的位置的节点删除。

4. insert和erase

请看示例代码：

		// 没有iterator失效iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;// prev  newnode  curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}// erase 后 pos失效了，pos指向节点被释放了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;return iterator(next);}

这部分代码实现了list类的insert和erase成员函数。

        1. insert：在指定位置前插入一个节点。首先获取迭代器pos所指向的节点cur，创建一个新的节点newnode，然后获取pos的前一个节点prev。将prev的_next指向newnode，newnode的_prev指向prev，newnode的_next指向cur，cur的_prev指向newnode。最后返回一个指向新节点的迭代器。
        2. erase：删除指定位置的节点。首先断言pos不等于end()，即pos不是指向末尾的迭代器。然后获取迭代器pos所指向的节点cur，分别获取cur的前一个节点prev和后一个节点next。将prev的_next指向next，next的_prev指向prev。删除cur节点，并释放内存。最后返回一个指向删除节点后的节点的迭代器。

        需要注意的是，在使用erase函数删除节点时，要确保操作前的迭代器pos不会失效，否则会导致未定义行为。

        到此我们只是简单的模拟实现了一下STL中list的相关接口~,后续我们会一一展开学习的,希望这篇博客能给您带来一些启发和思考!那我们下次再一起探险喽,欢迎在评论区进行讨论~~~

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • Android studio之编译提示Could not find :umeng-asms-v1.2.1
  • 【MySQL数据库之概念性问题】
  • 重点区域分布式无人机探测防御系统详解
  • QUdpSocket 的bind函数详解
  • 14-57 剑和诗人31 - LLM/SLM 中的高级 RAG
  • Hospital Management Startup 1.0 SQL 注入漏洞（CVE-2022-23366）
  • Mongodb索引的删除
  • 源码编译安装 LAMP
  • 部署前端项目
  • 高效前端开发：解密pnpm的存储与链接
  • 第5章-组合序列类型
  • 二叉树的顺序存储
  • linux 进程堆栈分析
  • 精通C#编程需要学习哪些常用框架？
  • [安洵杯 2019]easy_serialize_php
  • httpie使用详解
  • idea + plantuml 画流程图
  • IP路由与转发
  • java2019面试题北京
  • mysql_config not found
  • Netty+SpringBoot+FastDFS+Html5实现聊天App(六)
  • Promise初体验
  • session共享问题解决方案
  • vuex 学习笔记 01
  • 产品三维模型在线预览
  • 从零开始的无人驾驶 1
  • 高度不固定时垂直居中
  • 工程优化暨babel升级小记
  • 回流、重绘及其优化
  • 前端面试总结（at, md）
  • 如何胜任知名企业的商业数据分析师？
  • 收藏好这篇，别再只说“数据劫持”了
  • 推荐一款sublime text 3 支持JSX和es201x 代码格式化的插件
  • 我建了一个叫Hello World的项目
  • 线性表及其算法（java实现）
  • 智能网联汽车信息安全
  • 字符串匹配基础上
  • ​queue --- 一个同步的队列类​
  • ​人工智能书单（数学基础篇）
  • # Redis 入门到精通（九）-- 主从复制（1）
  • # 数据结构
  • #java学习笔记(面向对象)----(未完结)
  • #NOIP 2014# day.1 T3 飞扬的小鸟 bird
  • $分析了六十多年间100万字的政府工作报告，我看到了这样的变迁
  • （Oracle）SQL优化基础（三）：看懂执行计划顺序
  • （二）基于wpr_simulation 的Ros机器人运动控制，gazebo仿真
  • （附源码）springboot 校园学生兼职系统 毕业设计 742122
  • （数据结构）顺序表的定义
  • (四)js前端开发中设计模式之工厂方法模式
  • （一）Kafka 安全之使用 SASL 进行身份验证 —— JAAS 配置、SASL 配置
  • （转）LINQ之路
  • （转）Scala的“=”符号简介
  • （转）项目管理杂谈-我所期望的新人
  • *ST京蓝入股力合节能 着力绿色智慧城市服务
  • .net core 控制台应用程序读取配置文件app.config