当前位置： 首页 > article >正文

Lesson10---list

article 2024/10/25 10:13:14

Lesson10—list

第10章 c++的list的使用和实现

文章目录

  • Lesson10---list
  • 前言
  • 一、list的初始化
  • 二、list的遍历
    • 1.迭代器
    • 2.范围for
  • 三、list常用的内置函数
    • 1.sort（慎用）
    • 2.unique
    • 3.reverse
    • 4.merge
    • 5.splice
  • 四、模拟实现
    • 1.基本框架
    • 2.构造函数
    • 3.push_back
    • 4. 遍历
    • 5.const迭代器
    • 6.代码
    • 7.const迭代器改进
    • 8.insert
    • 9.erase
    • 10. pop_back
    • 11. push_front
    • 12.pop_front
    • 13.clear
    • 14.析构函数
    • 15.拷贝构造
    • 16.赋值
    • 17.initializer
  • 五.完整代码
  • 总结

前言

这篇博客写了怎么使用list和怎么实现

list和前面的string 和vector 的有很多重复的就不过多赘述

一、list的初始化

vector的底层是数组，list的底层是结构体，所以list不能用下标的方式去访问，因为这样会让效率变的特别低

可以直接用花括号去初始化这样就不要一个个尾插，vector和list都可以
在这里插入图片描述

二、list的遍历

1.迭代器

在这里插入图片描述
vector的底层是数组，在内存上是连续的但是链表不是，但这里链表依旧可以使用迭代器来遍历，非常的强大

既然可以用迭代器去访问一个在内存上不连续的list那能不能给这个链表用sort排序呢？
答案是不能，因为这样排序效率特别低，如果想要去排序链表，list提供了sort函数
在这里插入图片描述

2.范围for

在这里插入图片描述

有很多和vector重复了就不重复写了感兴趣的可以看我的vector篇

三、list常用的内置函数

1.sort（慎用）

在这里插入图片描述
在这里插入图片描述
默认是升序加上仿函数是降序

list的排序底层用的不是快排用的是归并排序，如果数据很多又要排序就不要用list用vector
在这里插入图片描述
list排序时间是vector的三倍左右，而且特别稳定基本都是三倍左右，虽然归并排序和快排都是nlogn但是list排序还是罗逊vector

甚至把list里面的数据拷贝给vector让vector用快排排序，把排序好的数据在拷贝回来这样会都比list的sort的归并排序快简直拉跨

在这里插入图片描述
在这里插入图片描述

2.unique

unique的作用是去重但数据必须是排序以后或者连续的
在这里插入图片描述
不排序或者不连续就会这样去不干净
在这里插入图片描述

3.reverse

逆置这个链表，比较简单
在这里插入图片描述

4.merge

合并链表，这里必须是要有序的
在这里插入图片描述
在这里插入图片描述

5.splice

这个函数差不多就是剪切的意思，第一个参数要迭代器，第二个参数是链表

从迭代器的位置插入一整个链表
在这里插入图片描述
还可以这样用
在这里插入图片描述

四、模拟实现

模板不建议声明和定义分开会有各种问题，建议直接把定义写在.h文件里面

1.基本框架

#pragma once
#include<iostream>
using namespace std;
template<class T>
struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prve;
	T _data;
};

template<class T>
class my_list
{
public:
	typedef ListNode<T> Node;
private:
	Node* _head;
};

先把基本的框架写好来

2.构造函数

在这里插入图片描述

3.push_back

在这里插入图片描述
这里可以画个草图理解，要尾插就要先找尾巴

void push_back(const T& x)
{
	Node* newnode = new Node(x);
	Node* tail = _head->_prve;
	tail->_next = newnode;
	newnode->_prve = tail;
	newnode->_next = _head;
	_head->_prve = newnode;
}

在这里插入图片描述
运行以后会这个错误

在这里插入图片描述
编译器给的是这个错误，这是因为，new Node 会去调用 node默认构造函数但是这里没有写
在这里插入图片描述

在这里插入图片描述

struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prve;
	T _data;
	ListNode(const T& data = T())
		:_next(nullptr)
		,_prve(nullptr)
		,_data(data)
	{

	}
};

在这里插入图片描述

4. 遍历

链表在逻辑上是连在一起的但是它在物理上就不一定是连续的了是所用它不能想vector一样的用++去遍历vector底层是数组
这里我采用迭代器的方式去遍历，因为指针++需要像数组那样在物理上连续才可以所以这里采用封装然后运算符重载去实现

class ListIterator
{
public:
	typedef ListNode<T> Node;
	typedef ListIterator<T> self;

	Node* _node;
	ListIterator(Node* node)
		:_node(node)
	{

	}
	self& operator++( )
	{
		_node = _node->_next;
		return *this;
	}
	T& operator*()
	{
		return _node->_data;
	}
	bool operator !=(const self& it)
	{
		return _node != it._node;
	}
};

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这样就可以遍历了，也支持范围for
在这里插入图片描述

5.const迭代器

如果有人这样去访问迭代器就会把回来的值改变不安全，有时候还会在不经意间改变原来的值
在这里插入图片描述
在这里插入图片描述
这里还需要重载一个const迭代器，只能去访问但是不能修改里面的值

template<class T>
class ListConstIterator

{
public:

	typedef ListNode<T> Node;
	typedef ListConstIterator<T> self;
	ListConstIterator(Node* node)
		:_node(node)
	{

	}
	Node* _node;
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	self& operator--()
	{
		_node = _node->_prve;
		return *this;
	}
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prve;
		return tmp;
	}
	const T& operator*()
	{
		return _node->_data;
	}
	bool operator !=(const self& it)
	{
		return _node != it._node;
	}
	bool operator ==(const self& it)
	{
		return _node == it._node;
	}
};

这里只需要复制一份原来的迭代器改下名字就行，然后重载一下
在这里插入图片描述
然后加上const就可以了然后再去my_list里面加上就行
在这里插入图片描述
加上const迭代器的begin和end
在这里插入图片描述
在这里插入图片描述
这里就不让改了

6.代码

#pragma once
#include<iostream>
using namespace std;
template<class T>
struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prve;
	T _data;
	ListNode(const T& data = T())
		:_next(nullptr)
		,_prve(nullptr)
		,_data(data)
	{

	}
};
template<class T>
class ListIterator

{
public:

	typedef ListNode<T> Node;
	typedef ListIterator<T> self;
	ListIterator(Node* node)
		:_node(node)
	{

	}
	Node* _node;
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	self& operator--()
	{
		_node = _node->_prve;
		return *this;
	}
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prve;
		return tmp;
	}
	T& operator*()
	{
		return _node->_data;
	}
	bool operator !=(const self& it)
	{
		return _node != it._node;
	}
	bool operator ==(const self& it)
	{
		return _node == it._node;
	}
};
template<class T>
class ListConstIterator

{
public:

	typedef ListNode<T> Node;
	typedef ListConstIterator<T> self;
	ListConstIterator(Node* node)
		:_node(node)
	{

	}
	Node* _node;
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	self& operator--()
	{
		_node = _node->_prve;
		return *this;
	}
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prve;
		return tmp;
	}
	const T& operator*()
	{
		return _node->_data;
	}
	bool operator !=(const self& it)
	{
		return _node != it._node;
	}
	bool operator ==(const self& it)
	{
		return _node == it._node;
	}
};


template<class T>
class my_list
{
public:
	typedef ListNode<T> Node;
	typedef ListIterator<T> iterator;
	typedef ListConstIterator<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);
	}
	
	

	my_list()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prve = _head;
 	}
	void push_back(const T& x)
	{
		Node* newnode = new Node(x);
		Node* tail = _head->_prve;
		tail->_next = newnode;
		newnode->_prve = tail;
		newnode->_next = _head;
		_head->_prve = newnode;
	}

private:
	Node* _head;
};

7.const迭代器改进

上面const迭代器有一个问题，就是只要解引用那一点点不一样甚至只是返回值加了const代码就边长了那么多这里还可以在优化一下

#pragma once
#include<iostream>
using namespace std;
template<class T>
struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prve;
	T _data;
	ListNode(const T& data = T())
		:_next(nullptr)
		, _prve(nullptr)
		, _data(data)
	{

	}
};
template<class T,class Ref>
class ListIterator

{
public:

	typedef ListNode<T> Node;
	typedef ListIterator<T,Ref> self;
	ListIterator(Node* node)
		:_node(node)
	{

	}
	Node* _node;
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	self& operator--()
	{
		_node = _node->_prve;
		return *this;
	}
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prve;
		return tmp;
	}
	Ref operator*()
	{
		return _node->_data;
	}
	bool operator !=(const self& it)
	{
		return _node != it._node;
	}
	bool operator ==(const self& it)
	{
		return _node == it._node;
	}
};
//template<class T>
//class ListConstIterator
//
//{
//public:
//
//	typedef ListNode<T> Node;
//	typedef ListConstIterator<T> self;
//	ListConstIterator(Node* node)
//		:_node(node)
//	{
//
//	}
//	Node* _node;
//	self& operator++()
//	{
//		_node = _node->_next;
//		return *this;
//	}
//	self& operator--()
//	{
//		_node = _node->_prve;
//		return *this;
//	}
//	self operator++(int)
//	{
//		self tmp(*this);
//		_node = _node->_next;
//		return tmp;
//	}
//	self operator--(int)
//	{
//		self tmp(*this);
//		_node = _node->_prve;
//		return tmp;
//	}
//	const T& operator*()
//	{
//		return _node->_data;
//	}
//	bool operator !=(const self& it)
//	{
//		return _node != it._node;
//	}
//	bool operator ==(const self& it)
//	{
//		return _node == it._node;
//	}
//};


template<class T>
class my_list
{
public:
	typedef ListNode<T> Node;
	typedef ListIterator<T,T&> iterator;
	typedef ListIterator<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);
	}



	my_list()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prve = _head;
	}
	void push_back(const T& x)
	{
		Node* newnode = new Node(x);
		Node* tail = _head->_prve;
		tail->_next = newnode;
		newnode->_prve = tail;
		newnode->_next = _head;
		_head->_prve = newnode;
	}

private:
	Node* _head;
};

8.insert

可以画个草图方便理解
在这里插入图片描述

iterator insert(iterator pos ,const T& x)
{
	Node* newnode = new Node(x);
	Node* cur = pos._node;

	newnode->_prve = cur->_prve;
	cur->_prve->_next = newnode;
	newnode->_next = cur;
	cur->_prve = newnode;
	return iterator(newnode);
}

9.erase

iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prve = cur->_prve;
	Node* next = cur->_next;
	
	prve->_next = next;
	next->_prve = prve;
	delete cur;
	return iterator(next);
}

10. pop_back

void pop_back()
{
	erase(--end());
}

11. push_front

void push_front(const T& x)
{
	insert(begin(), x);
}

12.pop_front

void pop_front()
{
	erase(begin());
}

13.clear

void clear()
{
	auto it = begin();
	while (it !=end())
	{
		it=erase(it);
		
	}
}

14.析构函数

~my_list()
{
	clear();
	delete _head;
	_head = nullptr;
}

15.拷贝构造

my_list(const my_list<T>& lt)
{
	_head = new Node;
	_head->_next = _head;
	_head->_prve = _head;
	for (const auto& e : lt)
	{
		push_back(e);
	}
}

16.赋值

my_list<T>& operator = (my_list<T> lt)
{
	swap(lt._head, _head);
	return *this;
}

17.initializer

my_list(initializer_list<T> il)
{
	_head = new Node;
	_head->_next = _head;
	_head->_prve = _head;
	for (auto e : il)
	{
		push_back(e);
	}
}

五.完整代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
struct ListNode
{
	ListNode<T>* _next;
	ListNode<T>* _prve;
	T _data;
	ListNode(const T& data = T())
		:_next(nullptr)
		, _prve(nullptr)
		, _data(data)
	{

	}
};
template<class T, class Ref>
class ListIterator

{
public:

	typedef ListNode<T> Node;
	typedef ListIterator<T, Ref> self;
	ListIterator(Node* node)
		:_node(node)
	{

	}
	Node* _node;
	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	self& operator--()
	{
		_node = _node->_prve;
		return *this;
	}
	self operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	self operator--(int)
	{
		self tmp(*this);
		_node = _node->_prve;
		return tmp;
	}
	Ref operator*()
	{
		return _node->_data;
	}
	bool operator !=(const self& it)
	{
		return _node != it._node;
	}
	bool operator ==(const self& it)
	{
		return _node == it._node;
	}
};
//template<class T>
//class ListConstIterator
//
//{
//public:
//
//	typedef ListNode<T> Node;
//	typedef ListConstIterator<T> self;
//	ListConstIterator(Node* node)
//		:_node(node)
//	{
//
//	}
//	Node* _node;
//	self& operator++()
//	{
//		_node = _node->_next;
//		return *this;
//	}
//	self& operator--()
//	{
//		_node = _node->_prve;
//		return *this;
//	}
//	self operator++(int)
//	{
//		self tmp(*this);
//		_node = _node->_next;
//		return tmp;
//	}
//	self operator--(int)
//	{
//		self tmp(*this);
//		_node = _node->_prve;
//		return tmp;
//	}
//	const T& operator*()
//	{
//		return _node->_data;
//	}
//	bool operator !=(const self& it)
//	{
//		return _node != it._node;
//	}
//	bool operator ==(const self& it)
//	{
//		return _node == it._node;
//	}
//};


template<class T>
class my_list
{
public:
	typedef ListNode<T> Node;
	typedef ListIterator<T, T&> iterator;
	typedef ListIterator<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);
	}
	void empty()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prve = _head;
	}
	my_list()
	{
		empty();
	}
	//lt2(lt1)
	my_list(initializer_list<T> il)
	{
		empty();
		for (auto e : il)
		{
			push_back(e);
		}
	}
	my_list(const my_list<T>& lt)
	{
		empty();
		for (const auto& e : lt)
		{
			push_back(e);
		}
	}
	~my_list()
	{
		clear();
		delete _head;
		_head = nullptr;
	}
	//lt3 = lt1
	my_list<T>& operator = (my_list<T> lt)
	{
		swap(lt._head, _head);
		return *this;
	}
	void push_back(const T& x)
	{
		/*Node* newnode = new Node(x);
		Node* tail = _head->_prve;
		tail->_next = newnode;
		newnode->_prve = tail;
		newnode->_next = _head;
		_head->_prve = newnode;*/
		insert(end(), x);
	}
	iterator insert(iterator pos ,const T& x)
	{
		Node* newnode = new Node(x);
		Node* cur = pos._node;

		newnode->_prve = cur->_prve;
		cur->_prve->_next = newnode;
		newnode->_next = cur;
		cur->_prve = newnode;
		return iterator(newnode);
	}
	iterator erase(iterator pos)
	{
		assert(pos != end());
		Node* cur = pos._node;
		Node* prve = cur->_prve;
		Node* next = cur->_next;
		
		prve->_next = next;
		next->_prve = prve;
		delete cur;
		return iterator(next);
	}
	void pop_back()
	{
		erase(--end());
	}
	void push_front(const T& x)
	{
		insert(begin(), x);
	}
	void pop_front()
	{
		erase(begin());
	}
	void clear()
	{
		auto it = begin();
		while (it !=end())
		{
			it=erase(it);
			
		}
	}
private:
	Node* _head;
};

总结

例如：以上就是要讲的内容，本文仅仅简单介绍了list的使用和简单的模拟实现


http://www.kler.cn/news/364272.html

相关文章：

  • 戴维南,叠加,稳态笔记
  • Node + HTML搭建自己的ChatGPT [基础版]
  • 计算机大类推荐职业方向
  • chrome清除https状态
  • Python异步编程：使用`asyncio`和`aiofiles`进行高效的文件批量写入
  • 硬件基础知识补全计划【一】电阻
  • Oracle SQL Developer 同时打开多个table的设置
  • Mysql索引结构前缀匹配原理
  • arcpy实现批量分区统计
  • 【如何获取股票数据18】Python、Java等多种主流语言实例演示获取股票行情api接口之沪深A股解禁限售数据获取实例演示及接口API说明文档
  • 分享一个开源的、自托管的 API 创建工具——Strapi
  • 【Unity踩坑】无法关闭Unity（Application.Shutdown.CleanupEngine）
  • 高边坡稳定安全监测预警系统解决方案
  • 文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《考虑负荷时空迁移的5G基站与配电网协同优化运行 》
  • mfc 最小二乘法
  • 道可云人工智能元宇宙每日资讯｜咸阳首个人工智能算力中心投运
  • openpnp - 解决“底部相机校正成功后, 开机归零时，吸嘴自动校验失败的问题“
  • 使用freemarker实现在线展示文档功能开发，包括数据填充
  • 【NPM】工程化依赖包/库开发 之 基础知识
  • 【2024工业图像异常检测代码复现】GLASS
  • 【Linux】进程池
  • 前端——原生Selection api操作选中文本 样式、取消样式（解决标签的无限嵌套问题）
  • 《Java与API的浪漫邂逅：一键获取商品详情》
  • 在Centos7.9服务器上使用LVM方式挂载磁盘以及Windows磁盘性能测试与Linux磁盘性能测试命令hdparm详细
  • 构建简单的梯度提升决策树（GBDT）模型：MATLAB 实现详解
  • 酒店定制门牌的材质有哪些