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

list库实现

list库实现的要点:

构建list类时,需要同时构建struct Node来存储节点信息,list类中只存储哨兵位节点信息,迭代器类需要template<T,Ptr,Ref>来构建const和非const迭代器,迭代器中也是存储节点信息。反向迭代器也是同样道理,但是可以用迭代器来构建反向迭代器。具体代码如下 

#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;template<class T>
struct __list_node
{__list_node(const T& val = T()):_data(val),_prev(nullptr),_next(nullptr){}__list_node* _prev;__list_node* _next;T _data;
};//构建每个节点//构建迭代器struct
template<class T, class Ptr, class Ref>
struct __list_iterator
{typedef __list_node<T> Node;typedef __list_iterator<T, Ptr, Ref> Self;Node* _node;//成员变量还是节点,只是在成员函数做手脚__list_iterator(Node* val ):_node(val){}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int)//后置{Self tmp = *this;++(*this);return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp = *this;--(*this);return tmp;}Ptr operator->(){return &(_node->_data);}Ref operator*(){return _node->_data;}bool operator!= ( const Self& val ){return !(_node == val._node);}};
template<class T,class Ptr,class Ref>
struct __list_reverse_iterator
{typedef __list_iterator<T, T*, T&> iterator;typedef __list_reverse_iterator<T, T*, T&> Self;iterator _it;__list_reverse_iterator(iterator it):_it(it){}Self operator++(){_it = _it._node->_prev;return *this;}T& operator*(){return _it._node->_data;}bool operator!=(const Self& rit){return !(_it._node == rit._it._node);}};//构建双向带头循环链表
template<class T>
class list
{typedef __list_node<T> Node;
public:typedef __list_iterator<T,T*,T&> iterator;typedef __list_iterator<T, const T*, const T&> const_iterator;typedef __list_reverse_iterator<T, T*, T&> reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(--end());}reverse_iterator rend(){return reverse_iterator(end());}iterator begin(){return iterator(_phead->_next);}const_iterator begin()const{return const_iterator(_phead->_next);}iterator end(){return iterator(_phead);}const_iterator end()const{return const_iterator(_phead);}list()//开头空间,初始化{_phead = new Node;_phead->_next = _phead;_phead->_prev = _phead;}~list(){clear();delete _phead;_phead = nullptr;}//拷贝构造(先创建一个哨兵位,然后再pushback)list(const list<T>& l){_phead = new Node;_phead->_next = _phead;_phead->_prev = _phead;for (auto& x : l){push_back(x);}}list<T>& operator=(const list<T>& l){list<T> tmp(l);swap(_phead, tmp._phead);return *this;}//尾插入void push_back(const T& val){//Node* tail = _phead->_prev;//Node* newnode = new Node(val);更变链接//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _phead;//_phead->_prev = newnode;insert(end(), val);}//头插void push_front(const T& val){insert(begin(), val);}//头删除void pop_front(){erase(begin());}//尾删除void pop_back(){erase(--end());}//清空节点(除了哨兵位,都清除)void clear(){iterator it = begin();while (it != end()){it = erase(it);}}//随机插入void insert(iterator pos, const T& val){Node* pcur = pos._node;Node* prev = pcur->_prev;Node* newnode = new Node(val);//构建联系newnode->_prev = prev;newnode->_next = pcur;prev->_next = newnode;pcur->_prev = newnode;}//删除指定位置(不能将哨兵位删掉!!iterator erase(iterator pos){assert(pos != end());Node* pcur = pos._node;Node* prev = pcur->_prev;Node* next = pcur->_next;delete pcur;pcur = nullptr;prev->_next = next;next->_prev = prev;return iterator(next);}private:Node* _phead;
};

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

相关文章:

  • MFC工控项目实例二十三模拟量输入设置界面
  • 排序算法总结(三)希尔排序
  • 如何迁移 Linux 服务器 第一部分 - 系统准备
  • 网络IO模型都有哪些
  • 数据结构: 数组在算法中的应用
  • js快速转换时间(时间戳转换成年月日时分秒)
  • LeetCode15.三数之和
  • SpringBoot3.3 优雅启停定时任务
  • 数据结构之二叉搜索树(key模型与key_value模型)
  • 图说几何学2300年重大错误:附着在直线z上的直线段必是z的一部分
  • 汽车网关(GW)技术分析
  • Telnet命令详解:安装、用法及应用场景解析
  • C++之LIST模拟实现(代码纯享版)
  • 华为OD机试 - 括号匹配 - 栈(Python/JS/C/C++ 2024 E卷 100分)
  • 打破欧美10年芯片垄断,杨振宁教授关门弟子,仅用三年创造奇迹
  • OpenCV视频I/O(20)视频写入类VideoWriter之用于将图像帧写入视频文件函数write()的使用
  • 音视频入门基础:FLV专题(14)——FFmpeg源码中,解码Script Tag的实现
  • 小猿口算APP脚本(协议版)
  • 【长文梳理webserver核心】核心类篇
  • [实用工具]Docker安装nextcloud实现私有云服务和onlyoffice
  • 基于STM32设计的生猪健康检测管理系统(NBIOT+OneNet)(240)
  • springboot kafka多数据源,通过配置动态加载发送者和消费者
  • 【华为】基于华为交换机的VLAN配置与不同VLAN间通信实现
  • 力扣题11~20
  • 更美观的HTTP性能监测工具:httpstat
  • 在2024 VDC,听一曲“蓝心智能”的江河协奏
  • Python编写的数字光刻仿真程序,使用了Hopkins光刻模型和粒子群优化(PSO)算法来优化掩模设计
  • 【AD那些事 11】绘制PCB板时“隔离” 的那些事(笔记摘抄)
  • sublime配置(竞赛向)
  • 双向数据库迁移工具:轻松实现 MySQL 与 SQLite 数据互导