[STL-list]介绍、与vector的对比、模拟实现的迭代器问题

一、list使用介绍

  1.  list的底层是带头双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
  2. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好
  3. list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;
常用接口:

构造函数:

构造函数接口说明
list (size_type n, const value_type& val = value_type())构造的list中包含n个值为val的元素
list()构造空的list
list (const list& x)拷贝构造函数
list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list

代码演示:

    list<int> l1;                         // 构造空的l1list<int> l2(4, 100);                 // l2中放4个值为100的元素list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end())左闭右开的区间构造l3list<int> l4(l3);                    // 用l3拷贝构造l4// 以数组为迭代器区间构造l5int array[] = { 16,2,77,29 };list<int> l5(array, array + sizeof(array) / sizeof(int));// 列表格式初始化C++11list<int> l6{ 1,2,3,4,5 };

list iterator的使用

对于迭代器的使用我们可以把它理解为一个指针,指向ist的某个节点

函数声明接口说明
begin + end返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin+ rend返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置reverse_iterator,即begin位置

【注意】
1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
2. rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

代码演示:

    list<int> lt(4, 100);  list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}       cout << endl;// C++11范围for的方式遍历for (auto& e : lt)cout << e << " ";cout << endl;

list modifiers

函数声明接口说明
push_front在list首元素前插入值为val的元素
pop_front删除list中第一个元素
push_back在list尾部插入值为val的元素
pop_back删除list中最后一个元素
insert在list position 位置中插入值为val的元素
erase删除list position位置的元素
swap交换两个list中的元素
clear清空list中的有效元素

代码演示:

void TestList1()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4,头部插入0L.push_back(4);L.push_front(0);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();
}// insert /erase 
void TestList2()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值为4的元素L.insert(pos, 4);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);// 在pos前插入[v.begin(), v.end)区间中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());// 删除pos位置上的元素L.erase(pos);// 删除list中[begin, end)区间中的元素,即删除list中的所有元素L.erase(L.begin(), L.end());
}// resize/swap/clear
void TestList3()
{// 用数组来构造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 交换l1和l2中的元素list<int> l2;l1.swap(l2);// 将l2中的元素清空l2.clear();cout << l2.size() << endl;
}

其他接口

二、与vector对比

vectorlist



动态顺序表,一段连续空间带头结点的双向循环链表


访
支持随机访问,访问某个元素效率O(1)不支持随机访问,访问某个元素效率O(N)




任意位置插入和删除效率低,需要搬移元素,时间复杂度为O(N),插入时有可能需要增容,增容:开辟新空间,拷贝元素,释放旧空间,导致效率更低任意位置插入和删除效率高,不需要搬移元素,时间复杂度为
O(1)




底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低


原生态指针对原生态指针(节点指针)进行封装




在插入元素时,要给所有的迭代器重新赋值,因为插入
元素有可能会导致重新扩容,致使原来迭代器失效,删
除时,当前迭代器需要重新赋值否则会失效
插入元素不会导致迭代器失效,删除元素时,只会导致当前迭代器失效,其他迭代器不受影响
使


需要高效存储,支持随机访问,不关心插入删除效率大量插入和删除操作,不关心随机访问

vector与list排序效率对比:

void test_op1()
{srand(time(0));const int N = 1000000;list<int> lt1;list<int> lt2;vector<int> v;for (int i = 0; i < N; ++i){auto e = rand() + i;lt1.push_back(e);v.push_back(e);}int begin1 = clock();// sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();printf("vector sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}

 

void test_op2()
{srand(time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (int i = 0; i < N; ++i){auto e = rand();lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();// vectorvector<int> v(lt2.begin(), lt2.end());// sort(v.begin(), v.end());// lt2lt2.assign(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();printf("list copy vector sort copy list sort:%d\n", end1 - begin1);printf("list sort:%d\n", end2 - begin2);
}

可见list的排序效率是非常低的,甚至将list的数据导入vector中排完序在导回来的效率都比直接在list中排序的效率快,这是因为list不支持下标随机访问,只能依靠迭代器迭代到指定位置访问,而排序过程中避免不了需要访问大量中间元素,所以list并不适合对数据进行排序

三、list迭代器问题

链表节点与链表结构

节点包含三部分:前驱指针、后驱指针、数据。list封装了头节点的指针,可以根据该指针对后续节点进行遍历

    template<class T>struct ListNode{ListNode* _next;ListNode* _prev;T _data;//节点的构造函数ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};template<class T>class list{void Empty_Init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}//构造函数list(){Empty_Init();}private:Node* _head;size_t _size;};
如何设定list迭代器

        在string与vector的模拟实现中,迭代器使用的都是原生指针T*,这是因为原生指针可以满足迭代器的要求,++可以指向下一个元素,解引用可以访问该元素,他们可以使用原生指针的根本原因是他们储存数据的结构都是连续的物理地址。

        在list中原生指针Node*不能满足我们的要求,因为list的节点都是依靠指针连接起来的,其物理地址并不是连续的,++指向的并不是下一个元素,而是指向了跳过了一个Node的大小的的地址,并且迭代器希望解引用直接可以访问节点中的数据,而*(Node*)却是一个节点类型,所以在list中使用原生指针并不符合迭代器的要求。

         所以我们可以自己新建一个类,作为迭代器的类型,在其中封装了头节点,就可以访问该链表了,并且我们在该类中可以通过运算符重载改变++与解引用的行为,这样就可以使用迭代器访问链表数据了

    template<class T>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T> Self;Node* _node;ListIterator(Node* _node):_node(_node){}T& operator*(){return _node->_data;}//前置++Self& operator++(){_node = _node->_next;return *this;}//后置++Self operator++(int){Self tmp(_node);_node = _node->_next;return tmp;}};template<class T>class list{void Empty_Init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}//构造函数list(){Empty_Init();}iterator begin(){//隐式类型转换return _head->_next;}iterator end(){//隐式类型转换return _head;}private:Node* _head;size_t _size;};
完善迭代器功能  
operator->的重载

        但是上述代码具有一定的局限性,例如当T为一个结构体A时,*iterator返回的是结构体A,想要访问结构体中的数据还需要用 例如:*(it).a1,但是这样写有点多次一举,因为迭代器it本身就是指向节点的指针,访问数据可以直接使用 ->,例如:it->a1,所以我们还需要将->重载一下

  T* operator->(){//返回数据的地址return &_node->_data;}

结构体A存储在节点的_data中,这里返回了_data的地址,如果按照正常的思路进行访问,应该按照如下的方式:it.operator->()->_a1 应该是两个箭头,第一个箭头代表运算符的重载,第二个代表指针解引用访问数据。
但是编译器为了方便查看会进行优化,将两个箭头变成了一个箭头 it->_a1 ,这样直接可以访问

const迭代器

const的本质就是为了禁止对成员进行修改,所以我们只需要const迭代器只需要对非const迭代器稍加修改即可

    template<class T>struct ListConstIterator{typedef ListNode<T> Node;typedef ListConstIterator<T> Self;Node* _node;ListConstIterator(Node* _node):_node(_node){}const T& operator*(){return _node->_data;}const T* operator->(){return &_node->_data;}};

但是这样const迭代器与非const迭代器这两个类的重合度非常高,仅仅是函数返回值前是否加用const修饰的区别,所以我们可以利用模板

    typedef ListIterator<T,T&,T*> iterator;typedef ListIterator<T,const T&,const T*> const_iterator;---------------------------------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){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//前置++Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(_node);_node = _node->_next;return tmp;}};
完整代码:
#include<iostream>
using namespace std;
namespace zyq
{template<class T>struct ListNode{ListNode* _next;ListNode* _prev;T _data;ListNode(const T& x = T()):_next(nullptr),_prev(nullptr),_data(x){}};//template<class T>//struct ListIterator//{//	typedef ListNode<T> Node;//	typedef ListIterator<T> Self;//	Node* _node;//	ListIterator(Node* _node)//		:_node(_node)//	{}//	T& operator*()//	{//		return _node->_data;//	}//     T* operator->()//	{//		return &_node->_data;//	}//	//前置++//	Self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	Self operator++(int)//	{//		Self tmp(_node);//		_node = _node->_next;//		return tmp;//	}//	bool operator!=(const Self& it)//	{//		return !(_node == it._node);//	}//	bool operator==(const Self& it)//	{//		return _node == it._node;//	}//};//template<class T>//struct ListConstIterator//{//	typedef ListNode<T> Node;//	typedef ListConstIterator<T> Self;//	Node* _node;//	ListConstIterator(Node* _node)//		:_node(_node)//	{}//	const T& operator*()//	{//		return _node->_data;//	}//	const T* operator->()//	{//		return &_node->_data;//	}//	//前置++//	 Self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	Self operator++(int)//	{//		Self tmp(_node);//		_node = _node->_next;//		return tmp;//	}//	bool operator!=(const Self& it)//	{//		return !(_node == it._node);//	}//	bool operator==(const Self& it)//	{//		return _node == it._node;//	}//};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){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}//前置++Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(_node);_node = _node->_next;return tmp;}bool operator!=(const Self& it){return !(_node == it._node);}bool operator==(const Self& it){return _node == it._node;}};template<class T>class list{public:typedef ListNode<T> Node;//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(){//隐式类型转换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;_size = 0;}//构造函数list(){Empty_Init();}//拷贝构造list(const list<T>& lt){Empty_Init();for (auto& e : lt){push_back(e);}}void swap(list<T> lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//赋值运算符重载list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){iterator it = begin();while (it != end()){it=erase(it);}delete _head;_head = nullptr;}size_t size(){return _size;}/*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;_size++;}*/void push_back(const T& x){insert(end()  , x);}void  push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}iterator erase(iterator pos){Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;_size--;return next;}private:Node* _head;size_t _size;};template<class T>void PrintList(const list<T>& clt){typename list<T>::const_iterator it = clt.begin();while (it != clt.end()){cout << *it << " ";it++;}cout << endl;}void testlist1(){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()){cout << *it << " ";it++;}cout << endl;/*lt.push_back(9);lt.pop_front();*/PrintList(lt);list<int> lt1(lt);PrintList(lt1);list<int> lt2;lt2 = lt;PrintList(lt2);}struct A{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}};void testlist2(){list<A> lt;lt.push_back({ 1,2 });lt.push_back(A(1,2));list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " " << (*it)._a2 << " ";cout << it->_a1 << " " << it->_a2 << " ";it++;}cout << endl;}
}

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

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

相关文章

[Apple Vision Pro]开源项目 Beautiful Things App Template

1. 技术框架概述&#xff1a; - Beautiful Things App Template是一个为visionOS设计的免费开源软件&#xff08;FOSS&#xff09;&#xff0c;用于展示3D模型画廊。 2. 定位&#xff1a; - 该模板作为Beautiful Things网站的延伸&#xff0c;旨在为Apple Vision Pro用户…

CNAS软件测试公司有什么好处?如何选择靠谱的软件测试公司?

CNAS认可是中国合格评定国家认可委员会的英文缩写&#xff0c;由国家认证认可监督管理委员会批准设立并授权的国家认可机构&#xff0c;统一负责对认证机构、实验室和检验机构等相关机构的认可工作。 在软件测试行业&#xff0c;CNAS认可具有重要意义。它标志着一个软件测试公…

C# 如何修改项目名称

目录 背景具体步骤1、Visual Studio中修改项目名和程序集名称以及命名空间2、修改项目文件夹名3、修改解决方案里项目的路径4、再次打开解决方案&#xff0c;问题解决步骤总结 名词解释解决方案&#xff08;Solution&#xff09;项目&#xff08;Project&#xff09;程序集&…

浏览器工作原理与实践--虚拟DOM:虚拟DOM和实际的DOM有何不同

虚拟DOM是最近非常火的技术&#xff0c;两大著名前端框架React和Vue都使用了虚拟DOM&#xff0c;所以我觉得非常有必要结合浏览器的工作机制对虚拟DOM进行一次分析。当然了&#xff0c;React和Vue框架本身所蕴含的知识点非常多&#xff0c;而且也不是我们专栏的重点&#xff0c…

JavaWeb前端基础(HTML CSS JavaScript)

本文用于检验学习效果&#xff0c;忘记知识就去文末的链接复习 1. HTML 1.1 HTML基础 结构 头<head>身体<body> 内容 图片<img>段落<p>图标<link> 标签 单标签双标签 常用标签 div&#xff1a;分割块span&#xff1a;只占需要的大小p&…

sqlserver问题记录

今天在利用sql查询数据时出现如下错误 在执行批处理时出现错误。错误消息为: 引发类型为“System.OutOfMemoryException”的异常。 症状 使用 SSMS 运行返回大量数据的 SQL 查询时&#xff0c;会收到类似于以下内容的错误消息&#xff1a; 执行批处理时出错。 错误消息为&…

nginx工作原理解析

目录 1、master-workers 的工作机制介绍 2、master-workers 的机制的好处 3、设置多少个 worker 4、最大连接数和支持的最大并发数的计算 1、master-workers 的工作机制介绍 nginx在启动后&#xff0c;会有一个master进程和一个或者多个相互独立的worker进程 过来的请求由…

C++模仿qq界面

#include "mywidget.h"MyWidget::MyWidget(QWidget *parent): QWidget(parent) {//设置窗口的大小this->resize(645,497);//设置窗口名字this->setWindowTitle("QQ");//设置窗口图标this->setWindowIcon(QIcon("C:\\zhouzhouMyfile\\qt_proj…

Linux网络编程: TCP协议之SACK与D-SACK详解

一、参考RFC https://www.ietf.org/rfc/rfc2018 https://www.ietf.org/rfc/rfc2883.txt 二、SACK选项&#xff08;RFC2018&#xff09; SACK实现的需要发送方和接收方协作。为此&#xff0c;TCP首部实际上定义了两种选项&#xff1a;SACK允许选项、SACK选项。 SACK允许选项…

突破校园网限速:使用 iKuai 多拨分流负载均衡 + Clash 代理(内网带宽限制通用)

文章目录 1. 简介2. iKuai 部署2.1 安装 VMware2.2 安装 iKuai(1) 下载固件(2) 安装 iKuai 虚拟机(3) 配置 iKuai 虚拟机(4) 配置 iKuai(5) 配置多拨分流 2.3 测试速度 3. Clash 部署(1) 配置磁盘分区(2) 安装 Docker(3) 安装 Clash(4) 设置代理 4. 热点&#xff1a;一起瓜分互…

Redis基本概念

什么是Redis Redis&#xff08;Remote Dictionary Server &#xff09;&#xff0c;即远程字典服务&#xff0c;是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库&#xff0c;并提供多种语言的API。 Redis的用处 缓存 缓存现在几…

shell脚本2

变量 变量是在程序中保存用户数据的一段内存存储空间&#xff0c;变量名是内存空间的首地址 字母、数字、下划线组成&#xff0c;不能以数字开头 原则&#xff1a;直接使用&#xff0c;不需要变量声明 格式&#xff1a;变量名 变量的值 环境变量 关闭窗口即会失效 若要永久生…

数据结构—红黑树

红黑树介绍 红黑树&#xff08;Red Black Tree&#xff09;是一种自平衡二叉查找树。由于其自平衡的特性&#xff0c;保证了最坏情形下在 O(logn) 时间复杂度内完成查找、增加、删除等操作&#xff0c;性能表现稳定。 在 JDK 中&#xff0c;TreeMap、TreeSet 以及 JDK1.8 的 …

数据生成 | Matlab实现基于K-means和SVM的GMM高斯混合分布的数据生成

数据生成 | Matlab实现基于K-means和SVM的GMM高斯混合分布的数据生成 目录 数据生成 | Matlab实现基于K-means和SVM的GMM高斯混合分布的数据生成生成效果基本描述模型描述程序设计参考资料 生成效果 基本描述 1.Matlab实现基于K-means和SVM的GMM高斯混合分布的数据生成&#xf…

深度学习实践(一)基于Transformer英译汉模型

本文目录 前述一、环境依赖二、数据准备1. 数据加载程序解析word_tokenize()将字符串分割为一个个的单词&#xff0c;并由列表保存。 2. 构建单词表程序解析&#xff08;1&#xff09;将列表里每个子列表的所有单词合并到一个新列表&#xff08;没有子列表&#xff09;中。&…

RabbitMQ3.13.0起支持MQTT5.0协议及MQTT5.0特性功能列表

RabbitMQ3.13.0起支持MQTT5.0协议及MQTT5.0特性功能列表 文章目录 RabbitMQ3.13.0起支持MQTT5.0协议及MQTT5.0特性功能列表1. MQTT概览2. MQTT 5.0 特性1. 特性概要2. Docker中安装RabbitMQ及启用MQTT5.0协议 3. MQTT 5.0 功能列表1. 消息过期1. 描述2. 举例3. 实现 2. 订阅标识…

浅聊java集合框架中的java.util.LinkedList

java集合框架总览 Java集合框架是一个用来代表和操纵集合的统一架构&#xff0c;它为管理和组织对象的集合提供了一组类和接口。这个框架包含三个主要部分&#xff1a;接口、实现和算法。 接口&#xff1a; Collection&#xff1a;这是集合框架的根接口&#xff0c;定义了集…

亚马逊运营必看!如何运用自养号测评获得买家评论转销量?

作为亚马逊卖家&#xff0c;相信大家对亚马逊的产品星级评分 (Rating) 都不陌生&#xff0c;这几颗亮眼的星星&#xff0c;不仅可以让你的Listing脱颖而出&#xff0c;获得足够多、足够高的产品评分&#xff0c;也是促使消费者下单的重要因素之一。 那么&#xff0c;亚马逊运营…

3D可视化技术亮相高铁站,引领智慧出行新潮流

在科技飞速发展的今天&#xff0c;我们的生活正经历着前所未有的变革。高铁站作为现代交通的重要枢纽&#xff0c;也在不断地创新和进步。 3D可视化技术通过三维立体的方式&#xff0c;将高铁站内部和外部的结构、设施、流线等以更加直观、生动的形式呈现出来。乘客们只需通过手…

全国高等学校sql

教育部颁发的最新高等学校名单&#xff0c;sql已整理好(按照省份树形结构)&#xff0c;是mysql8版本的 全国高等学校:预览地址&#xff1a;https://kdocs.cn/l/ckaFzCWMV1jn sql下载地址&#xff1a; https://pan.imgbed.link/file/22581