list容器(详解)

list的介绍及使用(了解,后边细讲)

1.1 list的介绍(双向循环链表)

https://cplusplus.com/reference/list/list/?kw=list(list文档介绍)

1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。

2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。

3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。

4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。

1.2 list的使用(可以对照模拟实现看,重要的都有,后边模拟实现都会讲)

list中的接口比较多,此处类似,只需要掌握如何正确的使用,然后再去深入研究背后的原理,已达到可扩展的能力。以下为list中一些常见的重要接口

1.2.1 list的构造

1.2.2 list iterator的使用

此处,大家可暂时将迭代器理解成一个指针,该指针指向list中的某个节点

【注意】

1. beginend为正向迭代器,对迭代器执行++操作,迭代器向后移动

2. rbegin(end)rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

1.2.3 list capacity

1.2.4 list element access

1.2.5 list modifiers

list中还有一些操作,需要用到时大家可参阅list的文档说明。

 list的迭代器失效

        注意,insert不会失效,迭代器依旧指向原来位置,erase会失效(删除后返回下一个地址),跟vector的迭代器失效类比,都是因为没有接收删除后的迭代器。insert不会失效,因为插入后返回新的节点地址,本身就指向新节点,不会失效

错误代码:

void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给
其赋值l.erase(it); ++it;}
}

改正后:

// 改正
void TestListIterator()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){l.erase(it++); // it = l.erase(it);两种写法都对}
}

 list的反向迭代器

  ReverseIterator.h

template<class Iterator,class Ref,class Ptr>
struct ReverseIterator
{typedef ReverseIterator<Iterator, Ref, Ptr> Self;Iterator cur;ReverseIterator(Iterator it):cur(it){ }Self& operator++(){--cur;return *this;}Ref operator*(){Iterator tmp = cur;--tmp;return *tmp;}Ptr operator->(){return &(operator*());}bool operator!=(const Self& s){return cur != s.cur;}
};

List.h

在list类内部多了一些改动,将反向迭代器的类重命名,并且新加两个成员函数

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
#include<list>using namespace std;#include"List.h"int main()
{jzy::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);jzy::list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;return 0;
}

可以看到反向迭代器起了作用,下面我来讲解反向迭代器的原理

反向迭代器可以理解成封装了正向迭代器,正向迭代器又封装了原生指针,反向迭代器++等价于正向迭代器--,反向迭代器解引用相当于正向迭代器--再解引用

因为反向迭代器的开始是正向迭代器结束位置,结束是正向的开始,所以反向迭代器要先--在解引用才是正确的值

反向迭代器的->也就是*拿到存放的值再取地址,和之前讲的是一个道理

typedef ReverseIterator<iterator, T&, T*> reverse_iterator;//typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}

反向迭代器在list类那里要多加一些东西,重命名反向迭代器这个类,当是普通反向迭代器的时候实例化iterator,T&,T*,当是const反向迭代器的时候,实例化参数是const_iterator,const T&,const T*

总体来讲,可以把反向迭代器看成适配器,当实例化参数是普通迭代器,会按照普通迭代器的行为进行操作,当参数是const时,会调用const的操作

list与vector的对比

vector与list都是STL中非常重要的序列式容器,由于两个容器的底层结构不同,导致其特性以及应用场景不同,其主要不同如下:

list模拟实现讲解(超详细)

定义结点结构体,结构体成员是前仆后继指针和元素data,还要写一个构造函数用来初始化结点

迭代器封装为一个类,类定义的对象存放每个节点的地址,也就是_node,相当于迭代器指针被封装成了一个类里存放,typedef是将类型重命名,将长的类型重命名为短的,记住类名不是类型,类名<类型>才是类型

这里模版有三个参数,第一个T是实例化类型,第二个和第三个参数是为了*和->,const类型会匹配T,constT& ,constT* ,正常类型会匹配T,T&,T*

这里将原生指针封装了一层包装在一个类里边,类定义的对象会通过操作指针前后移动来操作结点,解引用拿到对应结点的值,或者->拿到对应的地址

迭代器构造函数,当返回值是iterator类型时,会构造一个临时对象来操作

迭代器++,--,和日期类的原理类似,++it是当前指针往后走一步,this是it的地址,然后返回++之后的值,后置++,参数多传一个int就行,构造一个局部对象,指针向后走一步,返回走之前的值,迭代器--和++同理,无非是向前走

operator*是(*it)相当于拿到对应的值,我们就把it当成指针,*it当成解引用地址即可,这里是把指针封装到类里边,和前边string和vector的指针有所区分;->箭头相当于拿到存放对象的地址,当在list内部存放结构体时会用到

最简单的两个运算符重载,当判断不等于的时候会用到

list类要把上边两个类typedef后的类型写上去,方便等会用

迭代器的重载,当我们用begin()或者end()的时候,会调用这四个重载,普通对象调用普通迭代器,返回普通可修改指向对象的迭代器(这个对象可以用类名(),也可以直接返回Node*的结点指针(单参数的构造函数支持隐式类型转换),这两个写法都会生成一个临时对象,然后进行使用),const类型调用const迭代器,返回const不可修改指向对象的迭代器(慢慢理解这部分,其实没有想象的那么难)

list类的私有成员是_head,充当一个指针用来声明第一个哨兵位头结点

默认构造是初始化一个哨兵位头结点,结点内部存放前仆后继指针和data值(是某个类型的默认构造),然后让_head指向第一个哨兵位结点,并且_next和_prev都指向自己,完成哨兵位结点的初始化

析构函数先用clear清理,删除除了哨兵位结点的剩余存放有效数据的结点(释放了空间),最后释放哨兵位结点空间,_head置空就OK

拷贝构造,先初始化一个哨兵位结点,然后将要构造的对象内容依次给给e,尾插到新对象后边

赋值拷贝,先拷贝构造一个lt,将lt和新对象交换,lt是局部对象,出作用域会调用析构函数,新对象引用返回,完成赋值拷贝

insert插入,参数是迭代器指针(生成临时对象+2次拷贝构造)和要插入的值,cur指向要插入位置,prev存放要插入位置前边的指针,new一个新节点是要插入的新结点

三个指针相对位置是这样的,一般都是在某个位置之前插入,所以是这样的关系,然后按顺序链接这三个位置,前一个位置的后继指针和后一个位置的前驱指针都指向中间位置,最后返回插入节点的迭代器(单参数构造函数支持隐式类型转换)

删除很简单,不能删除哨兵位结点,找到要删除节点,记录要删除结点的前一个和后一个,链接两边的节点,最后释放要删除节点的空间,返回下一个节点的迭代器(会隐式类型转换成iterator类型的对象)

尾插,可以自己重新写逻辑,也可以复用insert逻辑,将第一个参数换成最后一个位置的迭代器,相当于在哨兵位节点之前插入,效果是一样的

头插,尾插,尾删是一样的,复用insert,erase逻辑就行

这部分在c语言实现数据结构链表那里讲的很详细了,想看的可以看看

代码样例讲解

这是一个很基础的尾插和打印对象逻辑,可以用第一个迭代器打印,也可以用第二个,范围for打印(范围for底层就是迭代器,无脑替换成迭代器进行打印),可以看到*it和it++,都是我们封装成类的功劳,原理很简单前面讲过

测试插入删除逻辑,可以看到不管是头插,头删,尾插,尾删都很清晰明了,clear是直接删除有效结点只剩哨兵位,所以打印不出来

可以看到,拷贝构造和赋值拷贝都完成了使命,前边讲的很详细,这里不再赘述

这里主要测试普通迭代器和const迭代器,各自调用各自,const迭代器不可修改对象,普通迭代器可以修改对象

最后一个样例,插入AA类对象,*it是拿到存放的结构体变量,.操作符访问结构体成员,拿到1:1,打印第二行是编译器会将*it转换成it.operator*(),效果是一样的

->箭头访问操作符会特殊处理一个箭头可以当做两个->->,并且编译器会转换成it.operator->()->_a1去访问,会特殊处理,这里当成特殊处理就好

list的模拟实现(代码)

       要模拟实现list,必须要熟悉list的底层结构以及其接口的含义,通过上面的学习,这些内容已基本掌握,现在我们来模拟实现list。

test.cpp


#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
using namespace std;#include"List.h"namespace jzy
{void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){//*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list2(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;lt.push_back(5);lt.push_front(0);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.clear();for (auto e : lt){cout << e << " ";}cout << endl;lt.push_back(10);lt.push_back(20);for (auto e : lt){cout << e << " ";}cout << endl;}void test_list3(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;list<int> copy(lt);for (auto e : copy){cout << e << " ";}cout << endl;list<int> lt1;lt1.push_back(10);lt1.push_back(20);lt1.push_back(30);lt1.push_back(40);lt = lt1;for (auto e : copy){cout << e << " ";}cout << endl;}void print_list(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){//*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print_list(lt);list<int>::iterator it = lt.begin();while (it != lt.end()){*it += 10;cout << *it << " ";++it;}cout << endl;}struct AA{int _a1;int _a2;AA(int a1 = 1, int a2 = 1):_a1(a1), _a2(a2){}};void test_list5(){list<AA> lt;AA aa1;lt.push_back(aa1);lt.push_back(AA());AA aa2(2, 2);lt.push_back(aa2);lt.push_back(AA(2, 2));list<AA>::iterator it = lt.begin();cout << (*it)._a1 << ":" << (*it)._a2 << endl;cout << it.operator*()._a1 << ":" << it.operator*()._a2 << endl;cout << it->_a1 << ":" << it->_a2 << endl;cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;cout << endl;}}int main(){jzy::test_list1();return 0;}

list.h

#pragma once
#include<assert.h>namespace jzy
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};template<class T, class Ref, class Ptr>struct __list_iterator{typedef ListNode<T> Node;typedef __list_iterator<T, Ref, Ptr> self;Node* _node;__list_iterator(Node* x):_node(x){}// ++itself& operator++(){_node = _node->_next;return *this;}// it++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}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& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};//template<class T>//struct __list_const_iterator//{//	typedef ListNode<T> Node;//	typedef __list_const_iterator<T> self;//	Node* _node;//	__list_const_iterator(Node* x)//		:_node(x)//	{}//	// ++it//	self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	// it++//	self operator++(int)//	{//		self tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	self& operator--()//	{//		_node = _node->_prev;//		return *this;//	}//	self operator--(int)//	{//		self tmp(*this);//		_node = _node->_prev;//		return tmp;//	}//	const T& operator*()//	{//		return _node->_data;//	}//	bool operator!=(const self& s)//	{//		return _node != s._node;//	}//	bool operator==(const self& s)//	{//		return _node == s._node;//	}//};template<class T>class list{typedef ListNode<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){//return iterator(_head->_next);return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list(){clear();delete _head;_head = nullptr;}list(const list<T>& lt){empty_init();for (const auto& e : lt){push_back(e);}}// lt1 = lt2;// list<T>& operator=(const list<T>& lt)/*list<T>& operator=(list<T>& lt){if (this != &lt){clear();for (const auto& e : lt){push_back(e);}}return *this;}*/void swap(list<T>& tmp){std::swap(_head, tmp._head);}//list& operator=(list lt)list<T>& operator=(list<T> lt){swap(lt);return *this;}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 push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}// vector insert会导致迭代器失效// list会不会?不会iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);// prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;//return iterator(newnode);return newnode;}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 next;}private:Node* _head;};
}

注意list的const迭代器可以实现为一个类,也可以实现为模版参数实例化后的结果,一般实现为后者,会少写很多冗余代码

以上就是我对list容器内容的讲解,很详细,欢迎大神交流!!!

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

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

相关文章

昆仑万维Java开发面试题及参考答案

进程和线程的区别是什么? 进程和线程都是操作系统中非常重要的概念,它们在多个方面存在显著的区别。 从定义上看,进程是操作系统进行资源分配和调度的基本单位。每个进程都有自己独立的内存空间,包括代码段、数据段、堆栈段等。例如,当你在电脑上同时打开浏览器和音乐播放…

系统学习算法:专题九 穷举vs暴搜vs深搜vs回溯vs剪枝

其中标题的深搜&#xff0c;回溯&#xff0c;剪枝我们之前专题都已经有过学习和了解&#xff0c;这里多了两个穷举和暴搜&#xff0c;其实意思都差不多&#xff0c;穷举就是穷尽力气将所有情况都列举出来&#xff0c;暴搜就是暴力地去一个一个情况搜索&#xff0c;所以就是全部…

人类心智逆向工程:AGI的认知科学基础

文章目录 引言:为何需要逆向工程人类心智?一、逆向工程的定义与目标1.1 什么是逆向工程?1.2 AGI逆向工程的核心目标二、认知科学的四大支柱与AGI2.1 神经科学:大脑的硬件解剖2.2 心理学:心智的行为建模2.3 语言学:符号与意义的桥梁2.4 哲学:意识与自我模型的争议三、逆向…

VLAN 基础 | 不同 VLAN 间通信实验

注&#xff1a;本文为 “ Vlan 间通信” 相关文章合辑。 英文引文&#xff0c;机翻未校。 图片清晰度限于原文图源状态。 未整理去重。 How to Establish Communications between VLANs? 如何在 VLAN 之间建立通信&#xff1f; Posted on November 20, 2015 by RouterSwi…

渗透测试之文件包含漏洞 超详细的文件包含漏洞文章

目录 说明 通常分为两种类型&#xff1a; 本地文件包含 典型的攻击方式1&#xff1a; 影响&#xff1a; 典型的攻击方式2&#xff1a; 包含路径解释&#xff1a; 日志包含漏洞&#xff1a; 操作原理 包含漏洞读取文件 文件包含漏洞远程代码执行漏洞: 远程文件包含…

蓝桥杯更小的数(区间DP)

题目描述 小蓝有一个长度均为 n 且仅由数字字符 0 ∼ 9 组成的字符串&#xff0c;下标从 0 到 n − 1&#xff0c;你可以将其视作是一个具有 n 位的十进制数字 num&#xff0c;小蓝可以从 num 中选出一段连续的子串并将子串进行反转&#xff0c;最多反转一次。小蓝想要将选出的…

洛谷 P1387 最大正方形 C语言

题目描述 在一个 n m 的只包含 0 和 1 的矩阵里找出一个不包含 0 的最大正方形&#xff0c;输出边长。 输入格式 输入文件第一行为两个整数 n, m (1 ≤ n, m ≤ 100)&#xff0c;接下来 n 行&#xff0c;每行 m 个数字&#xff0c;用空格隔开&#xff0c;0 或 1。 输出格式 …

算法与数据结构(括号匹配问题)

思路 从题干可以看出&#xff0c;只要给出的括号对应关系正确&#xff0c;那么就可以返回true,否则返回false。这个题可以使用栈来解决 解题过程 首先从第一个字符开始遍历&#xff0c;如果是括号的左边&#xff08;‘&#xff08;‘&#xff0c;’[‘&#xff0c;’}‘&…

硬件产品经理:需求引力模型(DGM)

目录 1、DGM 模型简介 2、理论核心&#xff1a;打破传统线性逻辑 3、三大定律 第一定律&#xff1a;暗物质需求法则 第二定律&#xff1a;引力井效应 第三定律&#xff1a;熵减增长律 4、落地工具包 工具1&#xff1a;需求密度热力图 工具3&#xff1a;摩擦力歼灭清单…

小书包:让阅读更美的二次开发之作

小书包是在一款知名阅读软件的基础上进行二次开发的产品。在保留原有软件的基本功能和用户体验的同时&#xff0c;对其界面和视觉效果进行了精心美化&#xff0c;让阅读体验更加舒适和愉悦。 内置了171条书源&#xff0c;虽然数量不算多&#xff0c;但都是作者精挑细选出来的&a…

openRv1126 AI算法部署实战之——Tensorflow模型部署实战

在RV1126开发板上部署Tensorflow算法&#xff0c;实时目标检测RTSP传输。视频演示地址 rv1126 yolov5 实时目标检测 rtsp传输_哔哩哔哩_bilibili ​ 一、准备工作 从官网下载tensorflow模型和数据集 手动在线下载&#xff1a; https://github.com/tensorflow/models/b…

蓝桥与力扣刷题(141 环形链表)

题目&#xff1a;给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部使用整数 pos 来表示链表尾连接到链表中的…

【生成模型之十三】SmartEraser

论文&#xff1a;SmartEraser: Remove Anything from Images using Masked-Region Guidance 代码&#xff1a; https://github.com/longtaojiang/SmartEraser 类型&#xff1a;fine-tuned diffusion model 其他&#xff1a;支持简历修改面试辅导 一、背景 到目前为止&#…

生成式AI安全最佳实践 - 抵御OWASP Top 10攻击 (下)

今天小李哥将开启全新的技术分享系列&#xff0c;为大家介绍生成式AI的安全解决方案设计方法和最佳实践。近年来生成式 AI 安全市场正迅速发展。据IDC预测&#xff0c;到 2025 年全球 AI 安全解决方案市场规模将突破 200 亿美元&#xff0c;年复合增长率超过 30%&#xff0c;而…

生成式AI安全最佳实践 - 抵御OWASP Top 10攻击 (上)

今天小李哥将开启全新的技术分享系列&#xff0c;为大家介绍生成式AI的安全解决方案设计方法和最佳实践。近年来&#xff0c;生成式 AI 安全市场正迅速发展。据 IDC 预测&#xff0c;到 2025 年全球 AI 安全解决方案市场规模将突破 200 亿美元&#xff0c;年复合增长率超过 30%…

mysql运维

1、msyqlLinux通用二进制安装 1. MySQL :: Download MySQL Community Server (Archived Versions)https://downloads.mysql.com/archives/community/https://downloads.mysql.com/archives/community/https://downloads.mysql.com/archives/community/https://downloads.mysql…

蓝桥杯刷题DAY3:Horner 法则 前缀和+差分数组 贪心

所谓刷题&#xff0c;最重要的就是细心 &#x1f4cc; 题目描述 在 X 进制 中&#xff0c;每一数位的进制不固定。例如&#xff1a; 最低位 采用 2 进制&#xff0c;第二位 采用 10 进制&#xff0c;第三位 采用 8 进制&#xff0c; 则 X 进制数 321 的十进制值为&#xff…

使用VCS对Verilog/System Verilog进行单步调试的步骤

Verilog单步调试&#xff1a; System Verilog进行单步调试的步骤如下&#xff1a; 1. 编译设计 使用-debug_all或-debug_pp选项编译设计&#xff0c;生成调试信息。 我的4个文件&#xff1a; 1.led.v module led(input clk,input rst_n,output reg led );reg [7:0] cnt;alwa…

【单层神经网络】softmax回归的从零开始实现(图像分类)

softmax回归 该回归分析为后续的多层感知机做铺垫 基本概念 softmax回归用于离散模型预测&#xff08;分类问题&#xff0c;含标签&#xff09; softmax运算本质上是对网络的多个输出进行了归一化&#xff0c;使结果有一个统一的判断标准&#xff0c;不必纠结为什么要这么算…

Docker使用指南(一)——镜像相关操作详解(实战案例教学,适合小白跟学)

目录 1.镜像名的组成 2.镜像操作相关命令 镜像常用命令总结&#xff1a; 1. docker images 2. docker rmi 3. docker pull 4. docker push 5. docker save 6. docker load 7. docker tag 8. docker build 9. docker history 10. docker inspect 11. docker prune…