【浅尝C++】STL第三弹=>list常用接口使用示例/list底层结构探索/list模拟实现代码详解

在这里插入图片描述

🏠专栏介绍:浅尝C++专栏是用于记录C++语法基础、STL及内存剖析等。
🎯每日格言:每日努力一点点,技术变化看得见。

文章目录

  • list介绍
  • list常用接口使用示例
    • 构造类函数
    • 迭代器
    • 属性与元素获取
    • 增删改操作
  • list底层结构探索
  • list模拟实现
    • 正向迭代器实现
    • 增删操作
    • 属性获取操作
    • 构造类函数
    • 整体代码汇总
  • list与vector比较


list介绍

  1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代
  2. list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
  3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。
  4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
  5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)

list常用接口使用示例

下面仅给出list部分常用接口及使用示例,更多关于list接口的介绍请参阅->list参考文档

构造类函数

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

下面给出上述接口的示例代码↓↓↓

#include <iostream>
#include <string>
#include <list>
using namespace std;

void testList()
{
	list<int>lt1(5,8);
	for(auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	list<int>lt2;
	cout << "lt2's size is " << lt2.size() << endl;

	list<int>lt3(lt1);
	for(auto e : lt3)
	{
		cout << e << " ";
	}
	cout << endl;

	string s = "Jammingpro";
	list<char>lt4(s.begin(), s.end());
	for(auto e : lt4)
	{
		cout << e << " ";
	}
	cout << endl;
}

int main()
{
	testList();
	return 0;
}

在这里插入图片描述

迭代器

接口声明接口描述
begin + end返回第一个元素的迭代器/返回最后一个元素的下一位置的迭代器
rebegin + rend返回最后一个元素的下一位置/返回第一个元素的位置

在这里插入图片描述

list底层是带头双向链表,begin指向第一个有效元素(头结点的后继节点),end指向头结点,迭代器begin每次++,每次向后移动,当与end重合时,则正向迭代结束。rbegin指向头结点,end指向第一个有效元素(头结点的后继节点),当要对rbegin解引用时,rbegin底层会执行*(rbegin->prev),返回rbegin指向节点的前驱节点的数据。即使rbegin指向头结点,但对它解引用获得的是头节后前驱节点的数据;当rbegin与end重合时则迭代结束。

下面来看一下list迭代器的使用示例代码↓↓↓

#include <iostream>
#include <string>
#include <list>
using namespace std;

void testList()
{
	string s = "Jammingpro";
	list<char>lt(s.begin(), s.end());
	
	list<char>::iterator it = lt.begin();
	while(it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	cout << "===================================" << endl;
	list<char>::reverse_iterator rit = lt.rbegin();
	while(rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
}

int main()
{
	testList();
	return 0;
}

在这里插入图片描述
对于const类型的list容器,需要配套使用const_iterator/const_reverse_iterator来进行正反向迭代。

★ps:begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动;rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

属性与元素获取

接口声明接口声明
empty检查list是否为空
size返回list中有效节点的个数
front返回list的第一个节点中的值的引用
back返回list的最后一个节点中的值的引用

上面接口相较简单,这里这届给出示例代码↓↓↓

#include <iostream>
#include <string>
#include <list>
using namespace std;

void testList()
{
	string s = "Jammingpro";
	list<char>lt;
	cout << "lt is empty?" << lt.empty() << endl;
	cout << "The size of lt is " << lt.size() << endl;

	for(auto ch : s)
	{
		lt.push_back(ch);
	}
	cout << "lt is empty?" << lt.empty() << endl;
	cout << "The size of lt is " << lt.size() << endl;
	cout << "The first element is " << lt.front() << endl;
	cout << "The last element is " << lt.back() << endl;
}

int main()
{
	testList();
	return 0;
}

在这里插入图片描述

增删改操作

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

上面接口的使用示例代码如下↓↓↓

#include <iostream>
#include <string>
#include <list>
using namespace std;

void testList()
{
	string s = "Jammingpro";
	list<char>lt(s.begin(), s.end());
	lt.push_back('!');
	lt.push_front('@');
	for(auto e : lt)
	{
		cout << e;
	}
	cout << endl;

	lt.pop_back();
	lt.pop_front();
	for(auto e : lt)
	{
		cout << e;
	}
	cout << endl;
	
	lt.insert(++lt.begin(), '#');
	for(auto e : lt)
	{
		cout << e;
	}
	cout << endl;
	
	lt.erase(++lt.begin());
	for(auto e : lt)
	{
		cout << e;
	}
	cout << endl;

	string s = "xiaoming";
	list<char> lt2(s.begin(), s.end());
	lt.swap(lt2);
	for(auto e : lt)
	{
		cout << e;
	}
	cout << endl;
	cout << "before clear size is " << lt.size() << endl;
	lt.clear();
	cout << "after clear size is " << lt.size() << endl;
}

int main()
{
	testList();
	return 0;
}

在这里插入图片描述

list底层结构探索

由监视窗口可以看到,list容器中包含指向头结点地址的指针及容器内有效元素的个数。每个节点包含前驱指针、后继指针及值域,故list底层是带头双向循环链表
在这里插入图片描述

list模拟实现

在模拟list之前,由于list的结构是双向链表,因而需要定义节点类型。↓↓↓

template<class T>
struct node
{
	node* _prev = nullptr;
	node* _next = nullptr;
	T _data;

	node(const T& x = T())
		:_data(x)
	{}
};

正向迭代器实现

由于链表的各个节点无法实现++或者–操作,因此,我们需要将迭代器封装为一个类(结构体)。在该类(接口体)中重载迭代器的各种操作。其中Ptr就是T*,Ref就是T&。

若定义list<char>::iterator it,则*it是为了获取节点中存的数据,因此operator*中中需要返回节点的数值,即_node->_data。对于it的其他运算符重载如下方代码所示↓↓↓

template<class T, class Ptr, class Ref>
struct __list_iterator
{
	typedef __list_iterator<T, Ptr, Ref> Self;

	node<T>* _node;
	__list_iterator(node<T>* node)
		:_node(node)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp(_node);
		_node = _node->_next;
		return tmp;
	}
	Self& operator--()
	{
		_node = _node->_prev;
		return this;
	}
	Self operator--(int)
	{
		Self tmp(_node);
		_node = _node->_prev;
		return tmp;
	}
	bool operator==(const Self& lt)
	{
		return _node == lt._node;
	}
	bool operator!=(const Self& lt)
	{
		return _node != lt._node;
	}
};

增删操作

void push_back(const T& val)
{
	Node* tail = _head->_prev;
	Node* newnode = new Node(val);

	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;

	_size++;
}
void pop_back()
{
	assert(!empty());
	Node* tail = _head->_prev;
	Node* tailPrev = tail->_prev;
	
	tailPrev->_next = _head;
	_head->_prev = tailPrev;

	delete tail;
	_size--;
}
void push_front(const T& val)
{
	Node* first = _head->_next;
	Node* newnode = new Node(val);

	_head->_next = newnode;
	newnode->_prev = _head;
	newnode->_next = first;
	first->_prev = newnode;

	_size++;
}
void pop_front()
{
	assert(!empty());
	Node* first = _head->_next;
	Node* second = first->_next;

	_head->_next = second;
	second->_prev = _head;
	delete first;
	_size--;
}
void insert(iterator pos, const T& val)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* newnode = new Node(val);

	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;

	_size++;
}
void erase(iterator it)
{
	Node* cur = it._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	prev->_next = next;
	next->_prev = prev;

	delete cur;
	_size--;
}

属性获取操作

bool empty() const
{
	return _size == 0;
}
size_t size() const
{
	return _size;
}

构造类函数

list()
	:_head(new Node)
{
	_head->_next = _head;
	_head->_prev = _head;
}
list(const list<T>& lt)
{
	Node* prev = _head;
	Node* cur = _head;
	Node* p = lt._head->_next;
	while (p != lt._head)
	{
		cur = new Node(p->_data);
		prev->_next = cur;
		cur->_prev = prev;
		p = p->_next;
	}
	_head->_prev = cur;
}
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}

整体代码汇总

由于我们自己模拟实现的list与库中重名,因此需要将其定义在命名空间内。

#include <iostream>
#include <cassert>

using namespace std;

namespace jammingpro
{
	template<class T>
	struct node
	{
		node* _prev = nullptr;
		node* _next = nullptr;
		T _data;

		node(const T& x = T())
			:_data(x)
		{}
	};

	template<class T, class Ptr, class Ref>
	struct __list_iterator
	{
		typedef __list_iterator<T, Ptr, Ref> Self;

		node<T>* _node;
		__list_iterator(node<T>* node)
			:_node(node)
		{}
		Ref operator*()
		{
			return _node->_data;
		}
		Self* operator->()
		{
			return _node;
		}
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		Self operator++(int)
		{
			Self tmp(_node);
			_node = _node->_next;
			return tmp;
		}
		Self& operator--()
		{
			_node = _node->_prev;
			return this;
		}
		Self operator--(int)
		{
			Self tmp(_node);
			_node = _node->_prev;
			return tmp;
		}
		bool operator==(const Self& lt)
		{
			return _node == lt._node;
		}
		bool operator!=(const Self& lt)
		{
			return _node != lt._node;
		}
	};

	template<class T>
	class list
	{
		typedef node<T> Node;
	public:
		//=====构造类函数=====
		typedef __list_iterator<T, T*, T&> iterator;
		typedef __list_iterator<const T, const T*, const T&> const_iterator;
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}
		list()
			:_head(new Node)
		{
			_head->_next = _head;
			_head->_prev = _head;
		}
		list(const list<T>& lt)
		{
			Node* prev = _head;
			Node* cur = _head;
			Node* p = lt._head->_next;
			while (p != lt._head)
			{
				cur = new Node(p->_data);
				prev->_next = cur;
				cur->_prev = prev;
				p = p->_next;
			}
			_head->_prev = cur;
		}
		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		//=====增删操作=====
		void push_back(const T& val)
		{
			Node* tail = _head->_prev;
			Node* newnode = new Node(val);

			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;

			_size++;
		}
		void pop_back()
		{
			assert(!empty());
			Node* tail = _head->_prev;
			Node* tailPrev = tail->_prev;
			
			tailPrev->_next = _head;
			_head->_prev = tailPrev;

			delete tail;
			_size--;
		}
		void push_front(const T& val)
		{
			Node* first = _head->_next;
			Node* newnode = new Node(val);

			_head->_next = newnode;
			newnode->_prev = _head;
			newnode->_next = first;
			first->_prev = newnode;

			_size++;
		}
		void pop_front()
		{
			assert(!empty());
			Node* first = _head->_next;
			Node* second = first->_next;

			_head->_next = second;
			second->_prev = _head;
			delete first;
			_size--;
		}
		void insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(val);

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			_size++;
		}
		void erase(iterator it)
		{
			Node* cur = it._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;

			delete cur;
			_size--;
		}
		//=====属性获取类函数=====
		bool empty() const
		{
			return _size == 0;
		}
		size_t size() const
		{
			return _size;
		}
	private:
		Node* _head;
		size_t _size = 0;
	};

	void test()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_back(5);
		lt.pop_back();
		lt.pop_back();
		lt.insert(lt.begin(), 888);
		lt.erase(lt.begin());
		lt.push_front(666);
		lt.pop_front();
		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		string s = "jammingpro";
		list<char>lt2(s.begin(), s.end());
		for (char ch : lt2)
		{
			cout << ch << endl;
		}
	}
}

list与vector比较

vectorlist
底层结构动态顺序表,一段连续空间带头双向循环链表
随机访问支持随机访问,访问某个元素效率为O(1)不支持随机访问,访问某个元素效率为O(N)
插入和删除任意位置插入与删除效率低,需要移动数据,时间复杂度为O(N);同时,插入元素时可能需要扩容(开辟空间并拷贝旧数据,释放旧空间),导致效率较低任意位置插入与删除效率高,无需移动数据,时间复杂度为O(N)
空间利用率底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高底层为动态开辟节点,小节点容易造成内存碎片,空间利用率低,缓存利用率低
迭代器原生指针对原生指针进行封装
迭代器失效在插入元素是,要给迭代器重新赋值;因为插入元素可能导致扩容,导致迭代器指向旧空间(迭代器失效);删除数据时,也需要给迭代器重新赋值(VS下迭代器失效,g++下不失效)插入元素不会导致迭代器失效,删除元素会导致迭代器失效
使用场景需要高效存储,支持随机访问,不关心插入删除效率大量插入和删除操作,不关心随机访问效率

🎈欢迎进入浅尝C++专栏,查看更多文章。
如果上述内容有任何问题,欢迎在下方留言区指正b( ̄▽ ̄)d

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2024年03月CCF-GESP编程能力等级认证Scratch图形化编程一级真题解析

本文收录于专栏《Scratch等级认证CCF-GESP真题解析》,专栏总目录・点这里 一、单选题(每题 3 分,共 30 分) 第1题 小杨的父母最近刚刚给他买了一块华为手表,他说手表上跑的是鸿蒙,这个 鸿蒙是?( )。 A、小程序 B、计时器 C、操作系统 D、神话人物 答案:C 第2题 …

golang语言系列:Web框架+路由 之 Gin

云原生学习路线导航页&#xff08;持续更新中&#xff09; 本文是golang语言学习系列&#xff0c;本篇对Gin框架的基本使用方法进行学习 1.Gin框架是什么 Gin 是一个 Go (Golang) 编写的轻量级 http web 框架&#xff0c;运行速度非常快&#xff0c;如果你是性能和高效的追求者…

HBase基础必备知识-Day1

HBase 简介 概述 HBase是Yahoo!公司开发的后来贡献给了Apache的一套开源的、分布式的、可扩展的、基于Hadoop的非关系型数据库(Non-Relational Database)&#xff0c;因此HBase并不支持SQL(几乎所有的非关系型数据库都不支持SQL)&#xff0c;而是提供了一套单独的命令和API操…

Redis高可用及持久化

文章目录 一、Redis高可用1、Redis高可用概述2、Redis高可用策略 二、Redis持久化1、Redis持久化的功能2、Redis持久化的两种方式2.1 RDB持久化2.2 AOF持久化&#xff08;append only file&#xff09; 3、RDB持久化3.1 触发条件3.1.1 手动触发3.1.2 自动触发3.1.2.1 配置方式3…

[Linux] 排查问题指令top/ps/netstat

在Linux下查看某个端口运行的指令 1. 首先通过netstat来查看端口对应的进程号 比如抓取端口53这个DNS服务的进程 netstat -tulnp | grep 53 可以看到53这个端口号对应的pid是720 2. 通过ps指令来对进程号执行的命令查询 ps aux | grep 720 可以看到pid为720这个进程对应的执…

聚道云助IT公司破解数据同步难,高效转型新利器!

客户介绍&#xff1a; 该公司是一家在信息技术行业具有丰富经验和良好声誉的公司。作为专业的软件服务提供商&#xff0c;他们致力于为客户提供全方位的解决方案和支持服务。公司秉持合规经营的原则&#xff0c;严格遵守相关法律法规&#xff0c;确保客户的数据安全和合法权益…

HTML基础:脚本 script 标签

你好&#xff0c;我是云桃桃。 1枚程序媛&#xff0c;大专生&#xff0c;2年时间从1800到月入过万&#xff0c;工作5年买房。 分享成长心得。 255篇原创内容-公众号 后台回复“前端工具”可获取开发工具&#xff0c;持续更新中 后台回复“前端基础题”可得到前端基础100题汇…

图卷积神经网络GCN

图卷积神经网络GCN 我们的GCN就是用来解决如何确定a、b、c的

Java毕业设计-基于springboot开发的致远汽车租赁系统平台-毕业论文+答辩PPT(附源代码+演示视频)

文章目录 前言一、毕设成果演示&#xff08;源代码在文末&#xff09;二、毕设摘要展示1、开发说明2、需求分析3、系统功能结构 三、系统实现展示1、系统功能模块2、管理员功能模块3、业务员功能模块3、用户功能模块 四、毕设内容和源代码获取总结 Java毕业设计-基于springboot…

Sora 基础作品之 DiT:Scalable Diffusion Models with Transformer

Paper name Scalable Diffusion Models with Transformers (DiT) Paper Reading Note Paper URL: https://arxiv.org/abs/2212.09748 Project URL: https://www.wpeebles.com/DiT.html Code URL: https://github.com/facebookresearch/DiT TL;DR 2022 年 UC Berkeley 出…

LeetCode 59 螺旋矩阵(模拟)

给你一个正整数 n &#xff0c;生成一个包含 1 到 n2 所有元素&#xff0c;且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;[[1,2,3],[8,9,4],[7,6,5]]示例 2&#xff1a; 输入&#xff1a;n 1 输出&…

模型训练----parser.add_argument添加配置参数

现在需要配置参数来达到修改训练的方式&#xff0c;我现在需要新建一个参数来开关wandb的使用。 首先就是在def parse_option():函数里添加上你要使用的变量名 parser.add_argument("--open_wandb",type bool,defaultFalse,helpopen wandb) 到config文件里增加你的…

2024-04-02 作业

作业要求&#xff1a; 整理思维导图使用模板类&#xff0c;实现顺序栈写一个char类型的字符数组&#xff0c;对该数组访问越界时抛出异常&#xff0c;并做处理。 作业1&#xff1a; 作业2&#xff1a; 运行代码: #include <iostream>using namespace std; #define LEN …

OpenGL_Learn16(模板测试)

模板缓冲首先会被清除为0&#xff0c;之后在模板缓冲中使用1填充了一个空心矩形。场景中的片段将会只在片段的模板值为1的时候会被渲染&#xff08;其它的都被丢弃了&#xff09;。 模板缓冲操作允许我们在渲染片段时将模板缓冲设定为一个特定的值。通过在渲染时修改模板缓冲的…

LeetCode_394(字符串解码)

双栈法 public String decodeString(String s) {String res "";Stack<Integer> countStack new Stack<>();Stack<String> resStack new Stack<>();int idx 0;while (idx < s.length()){char cur s.charAt(idx);//处理数字if(Charact…

css基础(一文读懂css)

1.css简介 css是一种用于描述网页样式和布局的样式表语言。它与HTML结合使用&#xff0c;用于控制网页中各个元素的外观和排版。 2.css样式引入方式 2.1 行内样式 行内优先级最高&#xff0c;针对当前标签 2.2 行外头部引入 行外头部&#xff1a;style&#xff0c;针对当前…

ISELED-演示项目代码

目录 一、main函数二、点灯函数一、main函数 int main(void) {/* Write your local variable definition here */iseledInitType.crcEnable = 1;iseledInitType.firstLedAdr = 1;iseledInitType.tempCmpEnable = 0;iseledInitType.voltSwing = 0;/*** End of Processor Expert…

【二叉树】Leetcode 105. 从前序与中序遍历序列构造二叉树【中等】

从前序与中序遍历序列构造二叉树 给定两个整数数组 preorder 和 inorder &#xff0c;其中 preorder 是二叉树的先序遍历&#xff0c; inorder 是同一棵树的中序遍历&#xff0c;请构造二叉树并返回其根节点。 示例1&#xff1a; 输入: preorder [3,9,20,15,7], inorder …

基于Springboot的一站式家装服务管理系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的一站式家装服务管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体…

微信小程序开发学习笔记——4.7 api中navigate路由接口与组件的关系

>>跟着b站up主“咸虾米_”学习微信小程序开发中&#xff0c;把学习记录存到这方便后续查找。 一、跳转 1、方法一&#xff1a;组件 组件-导航-navigator <navigator url"/pages/demo/demo?id123" open-type"reLaunch">go demo page <…