Lesson10---list

embedded/2024/10/25 4:22:45/

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 = lt1my_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.ppmy.cn/embedded/132237.html

相关文章

微调大模型-2-Qwen基座模型使用

微调大模型-2-Qwen基座模型使用

下载Qwen源码 Qwen作为中文支持非常nice的模型&#xff0c;很适合用于LLM学习。在云服务器里clone Qwen工程。 git clone https://github.com/QwenLM/Qwen2.5.git原始模型使用主要基于cli_demo.py-命令行调用&#xff0c;web_demo.py-网页调用。 预览这两个文件时&#xff0c…
阅读更多...
Android音视频 MediaCodec框架-创建流程(3)

Android音视频 MediaCodec框架-创建流程(3)

Android音视频 MediaCodec框架-创建流程 简述 之前我们介绍并且演示了MediaCodec的接口使用方法&#xff0c;我们这一节来看一下MediaCodec进行编解码的创建流程。 java层的MediaCodec只是提供接口&#xff0c;实际的逻辑是通过jni层实现的&#xff0c;java层的MediaCodec通过…
阅读更多...
1024程序员节- AI智能时代，码出未来

1024程序员节- AI智能时代，码出未来

在 1024 程序员节这个特殊的日子里&#xff0c;探讨了 AI 技术在不同领域的应用与发展。上海和深圳作为科技创新的前沿阵地&#xff0c;相关活动中的演讲内容更是聚焦了 AI 技术的核心要点&#xff0c;为我们展示了 AI 时代的新趋势和新机遇。 一、AI 技术的发展历程与背景 AI…
阅读更多...
python支付宝支付和回调

python支付宝支付和回调

创建支付订单 logging.basicConfig(levellogging.INFO,format%(asctime)s %(levelname)s %(message)s,filemodea,) logger logging.getLogger()if __name__ __main__:"""设置配置&#xff0c;包括支付宝网关地址、app_id、应用私钥、支付宝公钥等&#xff0c…
阅读更多...
【优选算法篇】在分割中追寻秩序：二分查找的智慧轨迹

【优选算法篇】在分割中追寻秩序：二分查找的智慧轨迹

文章目录 C 二分查找详解&#xff1a;基础题解与思维分析前言第一章&#xff1a;热身练习1.1 二分查找基本实现解题思路图解分析C代码实现易错点提示代码解读 1.2 在排序数组中查找元素的第一个和最后一个位置解题思路1.2.1 查找左边界算法步骤&#xff1a;图解分析C代码实现 1…
阅读更多...
3.1.1ReactOS系统中搜索给定长度的空间地址区间函数的实现

3.1.1ReactOS系统中搜索给定长度的空间地址区间函数的实现

系列文章目录 //搜索给定长度的空间地址区间 MmFindGap&#xff08;&#xff09;&#xff1b; PMADDRESS_SPACE AddressSpace,//该进程用户空间 ULONG_PTR Length,//寻找的空间间隔大小 ULONG_PTR Granularity,//粒度位&#xff0c;表明空间起点的对齐要求&#xff0c;注意是起…
阅读更多...
时序数据库 TDengine 支持集成开源的物联网平台 ThingsBoard

时序数据库 TDengine 支持集成开源的物联网平台 ThingsBoard

Thingsboard 中“设备配置”和“设备”的关系是一对多的关系&#xff0c;通过设备配置为每个设备设置不同的配置&#xff0c;每个设备都会有一个与其关联的设备配置文件。等等&#xff0c;这不就是TDengine 中超级表的概念&#xff1a; 超级表是一种特殊的表结构&#xff0c;用…
阅读更多...
针对 el-date picker pickerOptions 快捷选项的超级方法

针对 el-date picker pickerOptions 快捷选项的超级方法

提供快捷的配置&#xff0c;支持原子组合&#xff0c;高级用法支持用户自定义配置项 demo import { generateShortCuts } from ./date-shortcuts.js ... pickerOptions: {shortcuts: generateShortCuts({type: day}) } ...date-shortcuts 文件 import moment from moment // …
阅读更多...
最新文章

Copyright @ 2022~2023