list类的常用接口实现及迭代器

目录

1. list类的介绍

2.list类的常用接口

2.1 list类的常用构造

2.2 list类对象的容量操作

2.3 list迭代器

2.4 list类的常用操作

3.list的模拟实现


1. list类的介绍

list代表的是双向链表,常见的有创建,增,删,改几个接口(功能),对于list类来说,复杂的是它的迭代器,本章则会讲解list类的常见接口实现以及list类的简单实现。

2.list类的常用接口

2.1 list类的常用构造

构造函数接口说明
list(size_t n,const T& val=T())(注:T代表模版)构造n个val值的元素
list()默认构造
list(const list<T>& x)拷贝构造
list(InputIterator first, InputIterator last)利用迭代器区间构造list
#include<iostream>
#include<string>
#include<list>
using namespace std;
int main()
{list<int> l1;//默认构造list<int> l2(l1);//拷贝构造list<int> l3(10, 1);//构造n个val值string s("123456");list<int> l4(s.begin(), s.end());//利用迭代器区间构造return 0;
}

2.2 list类对象的容量操作

函数名称接口说明
empty判断list是否为空,是返回true,否则返回false
size返回list中有效节点个数

2.3 list迭代器

函数名称接口说明

begin+end

begin返回第一个元素的迭代器
end返回最后一个元素下一个位置的迭代器
rbegin+rend
rbegin返回最后一个元素的迭代器
rend返回第一个元素前一个位置的迭代器
#include<iostream>
#include<string>
#include<list>
using namespace std;
int main()
{list<int> l(10, 1);//构造n个val值for (auto e : l){cout << e << " ";}return 0;
}

2.4 list类的常用操作

函数名称接口说明
front返回list的第一个节点值的引用
back返回list的最后一个节点值的引用
push_front在list首元素前插入值为val的元素
pop_front删除list第一个元素
push_back在list尾部插入值为val的元素
pop_back删除list最后一个元素
insert在list的pos位置中插入值为val的值
erase删除list的pos位置的数据
swap
交换两个list中的元素
clear
清空list中的有效元素
#include<iostream>
#include<string>
#include<list>
using namespace std;
void Print(const list<int>& l)
{list<int>::const_iterator it = l.begin();while (it != l.end()){cout << *it << " ";++it;}cout << endl;}
int main()
{list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);Print(l1);//打印cout << endl;int a = l1.front();cout << a << endl;cout << l1.back() << endl;cout << endl;l1.push_front(10);Print(l1);cout << endl;l1.pop_front();Print(l1);cout << endl;l1.pop_back();Print(l1);cout << endl;list<int>::iterator it = l1.begin();++it;l1.insert(it, 20);Print(l1);cout << endl;l1.erase(it);Print(l1);cout << endl;list<int> l2(10, 1);l1.swap(l2);Print(l1);Print(l2);cout << endl;l1.clear();Print(l1);return 0;
}

3.list的模拟实现

3.1 list的基本结构

list的基本结构由三个类组成,一个是自己本身,一个是list的每个节点,最后就是有关迭代器的类,由于list中的底层结构是不连续的,因此不能用原本指针去访问,要对list的指针进行一个封装

namespace chuxin
{template<class T>struct list_node//链表的节点{T _data;list_node<T>* _prev;list_node<T>* _next;};template<class T>struct list_iterator//迭代器{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;};template<class T>//链表class list{typedef list_node<T> Node;public:typedef list_iterator<T> iterator;private:Node* _head;size_t _size;};
}

3.2 list的构造及析构

对于list来说,三个类都需要构造,但是,析构只有list就够了

namespace chuxin
{template<class T>struct list_node//链表的节点{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& data = T())//构造:_data(data), _prev(nullptr), _next(nullptr){}};template<class T>struct list_iterator//迭代器{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node)//构造:_node(node){}};template<class T>//链表class list{typedef list_node<T> Node;public:typedef list_iterator<T> iterator;list()//默认构造{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(const list<T>& lt)//拷贝构造{empty();for (auto& e : lt){push_back(e);}}~list()//析构{clear();delete _head;_head = nullptr;}private:Node* _head;size_t _size;};
}

3.3 迭代器

迭代器要进行的操作有++,--,比较,以及使用数据

     template<class T>struct list_iterator//迭代器{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node)//构造:_node(node){}T& operator*(){return _node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}bool operator!=(const Self& s)const{return s._node != _node;}bool operator==(const Self& s)const{return s._node == _node;}};

对于list的迭代器,还要重载一个—>,由于list内每个节点内的数据可能是一个结构体,这时候虽然还能用 . 作用符访问,但是较复杂。

struct AA
{int _a1 = 1;int _a2 = 1;
};
void test_list1()
{list<int> lt;list<AA> lta;lta.push_back(AA());lta.push_back(AA());lta.push_back(AA());lta.push_back(AA());list<AA>::iterator ita = lta.begin();while (ita != lta.end()){//cout << (*ita)._a1 << ":" << (*ita)._a2 << endl;// 特殊处理,本来应该是两个->才合理,为了可读性,省略了一个->cout << ita->_a1 << ":" << ita->_a2 << endl;cout << ita.operator->()->_a1 << ":" << ita.operator->()->_a2 << endl;++ita;}cout << endl;
}
 template<class T>struct list_iterator//迭代器{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node)//构造:_node(node){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}bool operator!=(const Self& s)const{return s._node != _node;}bool operator==(const Self& s)const{return s._node == _node;}};

对于迭代器,还要实现一个const的版本,如果要实现一个const的版本,发现两个类的结构大多相似,这时候就可以利用模版

	template<class T,class Ref,class Ptr>struct list_iterator//迭代器{typedef list_node<T> Node;typedef list_iterator<T,Ref,Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}bool operator!=(const Self& s)const{return s._node != _node;}bool operator==(const Self& s)const{return s._node == _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;list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(const list<T>& lt){empty();for (auto& e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}private:Node* _head;size_t _size;
};

此时利用三个模版参数就可以实现简洁化

3.4 赋值,clear,size,begin,end,front,back,empty

这几个较简单,不做叙述

	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;list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(const list<T>& lt){empty();for (auto& e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}// lt1 = lt3void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt);return *this;}iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}size_t size() const{return _size;}T& front(){return _head->_next->_data;}T& back(){return _head->_prev->_data;}bool empty() const{return _size == 0;}private:Node* _head;size_t _size;};

3.5 insert,erase,push_back,push_front,pop_back,pop_front

对于这些增删查改,可以进行一些复用,insert,erase,这里的插入,删除和链表完全相似,也不做详细叙述

		iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;++_size;return newnode;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}iterator erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;--_size;return next;}void pop_front(){erase(begin());}void pop_back(){iterator it = end();--it;erase(it);}

3.5 总代码

List.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace chuxin
{template<class T>struct list_node//链表的节点{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& data = T()):_data(data), _prev(nullptr), _next(nullptr){}};template<class T,class Ref,class Ptr>struct list_iterator//迭代器{typedef list_node<T> Node;typedef list_iterator<T,Ref,Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}bool operator!=(const Self& s)const{return s._node != _node;}bool operator==(const Self& s)const{return s._node == _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;list(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(const list<T>& lt){empty();for (auto& e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}// lt1 = lt3void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt){swap(lt);return *this;}iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;++_size;return newnode;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}iterator erase(iterator pos){assert(pos != end());Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;--_size;return next;}void pop_front(){erase(begin());}void pop_back(){iterator it = end();--it;erase(it);}size_t size() const{return _size;}T& front(){return _head->_next->_data;}T& back(){return _head->_prev->_data;}bool empty() const{return _size == 0;}private:Node* _head;size_t _size;};
}

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

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

相关文章

vscode Cline接入火山引擎的Deepseek R1

创建火山引擎Deepseek R1的API 在火山引擎管理控制台中创建Deepseek R1推理接入点&#xff08;大模型&#xff09;&#xff0c;创建成功后会看到下图效果。在操作中选择API调用&#xff0c;在页面中选择OpenAI SDK&#xff0c;按照步骤找到baseUrl地址和API_KEY&#xff0c;后续…

新手向:自动化图片格式转换工具

大家好&#xff01;今天我要分享一个非常实用的Python小工具——图片格式批量转换器。如果你经常需要处理大量不同格式的图片文件&#xff0c;或者需要统一图片格式以便于管理&#xff0c;那么这个工具将会成为你的得力助手&#xff01;一、为什么需要图片格式转换&#xff1f;…

CUDA中的内存管理、锁页内存、UVA统一虚拟地址、零拷贝、统一内存

文章目录0 前言1 swap内存跟锁页内存2 UVA(Unified Virtual Addressing)统一虚拟地址3 先看最普通的cuda内存分配、释放、传输4 申请锁页内存4.1 cudaHostAllocDefault4.2 cudaHostAllocPortable4.3 cudaHostAllocWriteCombined4.3 cudaHostAllocMapped4.4 几种锁页内存总结4.5…

微服务环境下的灰度发布与金丝雀发布实战经验分享

微服务环境下的灰度发布与金丝雀发布实战经验分享 在大规模微服务架构中&#xff0c;如何平滑安全地上线新功能是每个后端团队的痛点。本文将结合生产环境中的真实案例&#xff0c;分享灰度发布&#xff08;Gray Release&#xff09;与金丝雀发布&#xff08;Canary Release&am…

MEF 在 WPF 中的简单应用

MEF核心笔记MEF 的开发模式主要适用于插件化的业务场景中&#xff0c;C/S 和 B/S 中都有相应的使用场景&#xff0c;其中包括但不限于 ASP.NET MVC 、ASP WebForms、WPF、UWP 等开发框架。当然&#xff0c;DotNet Core 也是支持的。 以下是搜索到一些比较好的博文供参考&#…

Gitlab跑CICD的时候,maven镜像和pom.xml使用的maven版本冲突导致没办法build成功的解决方法

是这样的&#xff01;最近遇到一个非常棘手的难题&#xff0c;我搞了大概2周时间才把他弄出来&#xff0c;因为自己搭了个私服的maven仓库&#xff0c;他不像maven官方仓库一样&#xff0c;可以跟nginx一样转的&#xff0c;所以遇到好几个难点&#xff01;第一点&#xff1a;就…

Linux内核IPv4路由查找:LPC-Trie算法的深度实践

在互联网基础设施的核心领域,路由查找性能直接决定了网络转发效率。Linux内核作为现代网络系统的基石,其IPv4路由子系统采用了一种名为LPC-Trie(Level-Compressed Trie) 的创新数据结构,在net/ipv4/fib_trie.c文件中实现了高效的路由管理方案。本文将深入剖析这一机制的设…

【设计模式】装饰(器)模式 透明装饰模式与半透明装饰模式

装饰模式&#xff08;Decorator Pattern&#xff09;详解一、装饰模式简介 装饰模式&#xff08;Decorator Pattern&#xff09; 是一种 结构型设计模式&#xff0c;它允许你动态地给对象添加行为或职责&#xff0c;而无需修改其源代码&#xff0c;也不需要使用继承来扩展功能。…

NAT原理与实验指南:网络地址转换技术解析与实践

NAT实验 NAT&#xff08;Network Address Translation&#xff0c;网络地址转换&#xff09;&#xff1a; NAT技术的介绍&#xff1a; 随着Internet用户的快速增长&#xff0c;以及地址分配不均等因素&#xff0c;IPv4地址&#xff08;约40亿的空间地址&#xff09;已经陷入不…

设计模式之【观察者模式】

目录 观察者模式中的角色 通过一个简单案例来演示观察者模式 被观察者接口 事件类型 up主类作为被观察者 观察者接口 粉丝类作为观察者 测试 测试结果 观察者模式中的角色 被观察者(observable)观察者(observer) 通过一个简单案例来演示观察者模式 被观察者接口 /*…

Linux sudo host权限提升漏洞(CVE-2025-32462)复现与原理分析

免责声明 本文所述漏洞复现方法仅供安全研究及授权测试使用&#xff1b; 任何个人/组织须在合法合规前提下实施&#xff0c;严禁用于非法目的&#xff1b; 作者不对任何滥用行为及后果负责&#xff0c;如发现新漏洞请及时联系厂商并遵循漏洞披露规则。 漏洞简述 Linux sudo是l…

【uni-ui】hbuilderx的uniapp 配置 -小程序左滑出现删除等功能

1.网址&#xff1a;https://ext.dcloud.net.cn/plugin?id181](https://ext.dcloud.net.cn/plugin?id181) 2.csdn讲解&#xff1a;https://blog.csdn.net/qq_40323256/article/details/114337128 3.uni-ui git&#xff1a;https://github.com/dcloudio/uni-ui 4.官方网址文档&…

记一次POST请求中URL中文参数乱码问题的解决方案

POST请求中URL中文参数乱码前言&#xff1a;一个常见的开发痛点一、问题现象与原因深度解析1. 典型问题场景2. 根本原因分析URL编码规范问题&#xff1a;编码解码过程不一致&#xff1a;IE浏览器特殊行为&#xff1a;二、前端解决方案1. 手动编码URL参数&#xff08;推荐&#…

从存储热迁移流程了解 QEMU block layer

文章目录存储热迁移流程总体流程代码路径QEMU Block layer架构简述Block Job结构体设计状态转换Mirror block job拓扑结构构建过程数据结构存储热迁移流程 总体流程 Libvirt migrate 命令提供 copy-storage-all 选项支持存储热迁移&#xff0c;相应地&#xff0c;Libvirt 热迁…

【设计模式】命令模式 (动作(Action)模式或事务(Transaction)模式)宏命令

命令模式&#xff08;Command Pattern&#xff09;详解一、命令模式简介 命令模式&#xff08;Command Pattern&#xff09; 是一种 行为型设计模式&#xff08;对象行为型模式&#xff09;&#xff0c;它将一个请求封装为一个对象&#xff0c;从而使你可以用不同的请求对客户进…

HTML5智能排班日历:动态排班一目了然

这个日历将具备以下功能: 显示一个标准的月度日历视图。可以自由切换上一个月和下一个月。在日历的每一天自动显示当天值班的人员。您可以很方便地在文件中修改值班人员列表和排班的起始日期。包括:动态生成日历网格处理月份切换根据排班规则计算并显示每天的值班人员<!DO…

深度剖析C++生态系统:一门老牌语言如何在开源浪潮中焕发新生?

&#x1f4dd;个人主页&#x1f339;&#xff1a;慌ZHANG-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、前言&#xff1a;C的“长寿秘诀”是什么&#xff1f; C 诞生已超过 40 年。它经历了桌面应用、互联网爆发、移动时代&#xff0c;再…

60个功能OfficeBox 万彩办公大师:PDF 格式转换 OCR识别免费无广告

各位办公小能手们&#xff01;今天给大家介绍个超厉害的免费办公工具套装——OfficeBox万彩办公大师&#xff0c;是广州万彩科技整出来的。软件下载地址安装包 它里面有60多个没广告的绿色组件&#xff0c;简直像个百宝箱&#xff01;涵盖了PDF处理、格式转换、OCR识别、屏幕录…

拥抱主权AI:OpenCSG驱动智能体运营,共筑新加坡智能高地

2025年7月11日&#xff0c;由Linux基金会AI & Data、TikTok及LF Edge联合主办的 【LF AI & Data Day Singapore 2025】 在新加坡TikTok总部盛大启幕。本次大会以“Agent for SWE”为核心议题&#xff0c;汇聚全球顶尖AI开发者、企业领袖及开源社区先锋。作为国家主权AI…

单片机学习笔记.根据芯片数据手册写驱动程序(这里使用的是普中开发版,以DS1302为例)

硬件原理图部分&#xff1a; VCC2:是主电源 VCC1&#xff1a;是备用电源&#xff0c;此处没有使用VCC1 查芯片数据手册的网站&#xff1a; ALLDATASHEETCN.COM - 电子元件和半导体及其他半导体的数据表搜索网站。https://www.alldatasheetcn.com/ 1.由原理图可知对应引脚&…