list(1)

news/2024/10/21 2:31:38/

list_0">list

在这里插入图片描述

大体上与之前学的string,vector类似，list不支持[]访问，擅长头插，头删，尾插，尾删，中间元素插入删除，因为list底层是双向循环带头链表

一段代码演示：

#include <iostream>
#include <list>
using namespace std;int main()
{//尾插list<int> lt1;lt1.push_back(1);lt1.push_back(1);lt1.push_back(1);lt1.push_back(1);list<int> lt2 = { 1,2,3,4,5 };//迭代器list<int>::iterator it1 = lt1.begin();//迭代器进行访问while (it1 != lt1.end()){cout << *it1 << " ";++it1;}cout << endl;//支持迭代器也就支持范围forfor (auto e : lt2){cout << e << " ";}cout << endl;
}

代码结果如下：

在这里插入图片描述

这里list的迭代器会有所不同

在这里插入图片描述

用原生指针解决不了

push_back和emplace_back

先来看一段代码：

class Pos
{int _row;int _col;public:Pos(int row, int col):_row(row),_col(col){cout << "Pos(int row, int col)" << endl;}//拷贝构造Pos(const Pos& p):_row(p._row), _col(p._col){cout << "Pos(const Pos&p)" << endl;}
};int main()
{//构造+拷贝构造//push_backlist<Pos> lt;//有名对象Pos p1(1, 1);lt.push_back(p1);//匿名对象lt.push_back(Pos(2, 2));//隐式类型转换lt.push_back({ 3,3 });//emplace_back，可以看作模板lt.emplace_back(p1);lt.emplace_back(Pos(2, 2));//lt.emplace_back({3,3});不可以，因为形参类型未知//可以传递多个参数，相当于直接构造了Pos//直接构造lt.emplace_back(3, 3);return 0;
}

splice

一个应用的地方在于可以提高修改元素内容的效率：

int main()
{list<int> lt1 = { 1,2,3,4,5 };//LRU//这里可以理解为转移链表里面的元素int x;while (cin >> x){auto pos = find(lt1.begin(), lt1.end(), x);if (pos != lt1.end()){//这里的含义是把lt1里的pos转移到开头位置lt1.splice(lt1.begin(), lt1, pos);}}return 0;
}

sort–排序

示例代码如下：

int main()
{list<int> lt1 = { 1,20,3,-4,5 };for (auto e : lt1){cout << e << " ";}cout << endl;//默认是升序lt1.sort();for (auto e : lt1){cout << e << " ";}cout << endl;//如果需要降序，要用到仿函数greater//有名对象的写法//greater<int> gt;//lt1.sort(gt);//匿名对象的写法,更推荐lt1.sort(greater<int>());//vector的方式也可以写vector<int> v1 = { 1,20,3,-4,5 };for (auto e : v1){cout << e << " ";}cout << endl;//这里同样也是默认升序sort(v1.begin(), v1.end());for (auto e : v1){cout << e << " ";}cout << endl;//降序也要用到仿函数sort(v1.begin(), v1.end(), greater<int>());for (auto e : v1){cout << e << " ";}cout << endl;
}

运行结果如下：

在这里插入图片描述

迭代器的分类

在这里插入图片描述

不能随便乱用迭代器，因为底层是不一样的，可以理解为随机单向迭代器包含于双向迭代器，双向迭代器包含于随机迭代器

上面的排序,sort的底层是特殊处理过的，vector的底层是快排

效率对比测试：
测试的代码：

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_269">list的模拟实现

尾插的操作与前面学习的双向循环链表类似：

在这里插入图片描述

迭代器这里需要注意，与前面学习的string和vector不一样：

在这里插入图片描述

这里需要注意的是迭代器不可以通过下标的方式进行访问，像我们前面学过的string和vector底层结构是数组，物理结构是连续的，但是list的底层是双向循环链表，物理空间不连续，需要借助类封装节点指针，重载运算符，模拟指针的行为

operator->访问

代码如下：
list.h

T* operator->()//访问里面元素
{return &_node->_data;//取里面地址
}

Test.cpp

soobin::list<Pos> lt2;
Pos p1(1, 1);
lt2.push_back(p1);
lt2.push_back(Pos(2, 2));
lt2.push_back({ 3,3 });soobin::list<Pos>::iterator it2 = lt2.begin();
while (it2 != lt2.end())
{cout << (*it2)._row << ":" << (*it2)._col << endl;//为了可读性，特殊处理，省略了一个->cout << it2->_row << ":" << it2->_col << endl;//显示写法，第一个->是运算符重载，第二个->是结构体元素访问cout << it2.operator->()->_row << ":" << it2.operator->()->_col << endl;++it2;
}
cout << endl;

总体代码如下：
List.h

#include <assert.h>
namespace soobin
{// 惯例// 全部都是公有，一般用structtemplate<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T())//模板的缺省值，匿名对象:_data(x), _next(nullptr), _prev(nullptr){}};template<class T>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node):_node(node){}//引用返回的好处是既可以读也可以写T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef list_iterator<T> iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;}list(){empty_init();}void push_back(const T& x){Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;}private:Node* _head;};
}

Test.h

#include <iostream>
#include <list>
#include <vector>
#include <algorithm>
using namespace std;//int main()
//{//尾插//list<int> lt1;//lt1.push_back(1);//lt1.push_back(1);//lt1.push_back(1);//lt1.push_back(1);//list<int> lt2 = { 1,2,3,4,5 };//迭代器//list<int>::iterator it1 = lt1.begin();//迭代器进行访问//while (it1 != lt1.end())//{//	cout << *it1 << " ";//	++it1;//}//cout << endl;//支持迭代器也就支持范围for//for (auto e : lt2)//{//	cout << e << " ";//}//cout << endl;
//}class Pos
{
public:int _row;int _col;Pos(int row, int col):_row(row),_col(col){cout << "Pos(int row, int col)" << endl;}//拷贝构造Pos(const Pos& p):_row(p._row), _col(p._col){cout << "Pos(const Pos&p)" << endl;}
};//int main()
//{//构造+拷贝构造//push_back
//	list<Pos> lt;//有名对象
//	Pos p1(1, 1);
//	lt.push_back(p1);
//	//匿名对象
//	lt.push_back(Pos(2, 2));//隐式类型转换
//	lt.push_back({ 3,3 });//emplace_back，可以看作模板
//	lt.emplace_back(p1);
//	lt.emplace_back(Pos(2, 2));//lt.emplace_back({3,3});不可以，因为形参类型未知//可以传递多个参数，相当于直接构造了Pos//直接构造
//	lt.emplace_back(3, 3);
//	return 0;
//}//int main()
//{//for (auto e : lt1)//{//	cout << e << " ";//}//cout << endl;//int x;//cin >> x;//auto it = find(lt1.begin(), lt1.end(), x);//if (it != lt1.end())//{//	it.erase(it);//}
//	return 0;
//}//int main()//{//	list<int> lt1 = { 1,2,3,4,5 };//LRU//这里可以理解为转移链表里面的元素//	int x;//	while (cin >> x)//	{//		auto pos = find(lt1.begin(), lt1.end(), x);//		if (pos != lt1.end())//		{//这里的含义是把lt1里的pos转移到开头位置//			lt1.splice(lt1.begin(), lt1, pos);//		}//	}//	return 0;//}//int main()
//{
//	list<int> lt1 = { 1,20,3,-4,5 };
//	for (auto e : lt1)
//	{
//		cout << e << " ";
//	}
//	cout << endl;//默认是升序
//	lt1.sort();
//	for (auto e : lt1)
//	{
//		cout << e << " ";
//	}
//cout<<endl;
//	//如果需要降序，要用到仿函数greater//有名对象的写法//greater<int> gt;//lt1.sort(gt);//匿名对象的写法,更推荐//lt1.sort(greater<int>());//vector的方式也可以写//vector<int> v1 = { 1,20,3,-4,5 };//for (auto e : v1)//{//	cout << e << " ";//}//cout << endl;//这里同样也是默认升序//sort(v1.begin(), v1.end());//for (auto e : v1)//{//	cout << e << " ";//}//cout << endl;//降序也要用到仿函数//sort(v1.begin(), v1.end(), greater<int>());//for (auto e : v1)//{//	cout << e << " ";
//	}//cout << endl;
//}
//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()
//{
//	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();// 拷贝vector//	vector<int> v(lt2.begin(), lt2.end());// 排序
//	sort(v.begin(), v.end());// 拷贝回lt2
//	lt2.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);
//}#include "List.h"int main()
{soobin::list<int> lt1;lt1.push_back(1);lt1.push_back(1);lt1.push_back(1);lt1.push_back(1);//不直接在it1上进行改动是因为会造成没有指针指向哨兵位等问题//迭代器soobin::list<int>::iterator it1 = lt1.begin();//迭代器进行访问while (it1 != lt1.end()){//也可以写*it1 = 2;cout << *it1 << " ";++it1;}cout << endl;//支持迭代器也就支持范围forfor (auto e : lt1){cout << e << " ";}cout << endl;soobin::list<Pos> lt2;Pos p1(1, 1);lt2.push_back(p1);lt2.push_back(Pos(2, 2));lt2.push_back({ 3,3 });soobin::list<Pos>::iterator it2 = lt2.begin();while (it2 != lt2.end()){cout << (*it2)._row << ":" << (*it2)._col << endl;//为了可读性，特殊处理，省略了一个->cout << it2->_row << ":" << it2->_col << endl;//显示写法，第一个->是运算符重载，第二个->是结构体元素访问cout << it2.operator->()->_row << ":" << it2.operator->()->_col << endl;++it2;}cout << endl;return 0;
}

http://www.ppmy.cn/news/1540669.html

相关文章

tftpd.exe开启调试

tftpd.exe开启调试

tftpd.exe开启调试 debugFlags设置为0xf开启debug 设置为0xf000f则开启debug和trace 第一部分&#xff1a; 位置 net/tcpip/services/tftpd/service.c if (RegOpenKeyEx(HKEY_LOCAL_MACHINE, "System\\CurrentControlSet\\Services\\Tftpd\\Paramet…
阅读更多...
【推导过程】常用离散分布的数学期望、方差、特征函数

【推导过程】常用离散分布的数学期望、方差、特征函数

文章目录 相关教程相关文献常用离散分布的数学期望&方差&特征函数二项分布数学期望方差 泊松分布泊松定理数学期望方差 超几何分布超几何分布的二项近似数学期望方差 几何分布几何分布的无记忆性数学期望方差 负二项分布 作者&#xff1a;小猪快跑 基础数学&计算数…
阅读更多...
笔试练习day7

笔试练习day7

目录 OR59 字符串中找出连续最长的数字串题目解析解法(双指针遍历)代码 NC109 岛屿数量题目解析解法代码(dfs)dfs的实现 拼三角题目解析解法(枚举)代码 感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接 &#x1f412;&#x1f412;&#x1f412; 个人主页 &…
阅读更多...
DBSwitch和Seatunel

DBSwitch和Seatunel

一、DBSwitch 什么是DBSwitch?它主要用在什么场景&#xff1f; 通过步骤分析可以看到这个是通过配置数据源&#xff0c;采用一次性或定时方案&#xff0c;同步到数据仓库的指定表&#xff0c;并且指定映射关系的工具。有点类似于flinkcdc的增量同步。 参考&#xff1a; dbs…
阅读更多...
webAPI中的排他思想、自定义属性操作、节点操作（配大量案例练习）

webAPI中的排他思想、自定义属性操作、节点操作（配大量案例练习）

一、排他操作 1.排他思想 如果有同一组元素&#xff0c;我们想要某一个元素实现某种样式&#xff0c;需要用到循环的排他思想算法&#xff1a; 1.所有的元素全部清除样式 2.给当前的元素设置样式 注意顺序能不能颠倒&#xff0c;首先清除全部样式&#xff0c;再设置自己当前的…
阅读更多...
Debian12离线部署docker详细教程

Debian12离线部署docker详细教程

1、转至 https://download.docker.com/linux/debian/dists/ 2、在列表中选择您的 Debian 版本。 cat /etc/os-release # 我的版本号是bookworm3、转到pool/stable/并选择适用的架构&#xff08;amd64、 armhf、arm64或s390x&#xff09; 4、在deb网址下&#xff0c;下载Doc…
阅读更多...
知识点：代理设计模式

知识点：代理设计模式

1.场景设定和问题复现 1 准备项目 pom.xml <dependency> <groupId>org.junit.jupiter</groupId> <artifactId>junit-jupiter-api</artifactId> <version>5.3.1</version> <scope>test</scope></dependen…
阅读更多...
兰迪·舍克曼担任生命银行链（LBC）顾问，赋能基因数据区块链技术发展

兰迪·舍克曼担任生命银行链（LBC）顾问，赋能基因数据区块链技术发展

兰迪舍克曼&#xff08;Randy Schekman&#xff09;作为生命银行链&#xff08;Life Bank Chain, LBC&#xff09;的顾问参与其中&#xff0c;这无疑是个令人兴奋的消息&#xff01;他在生理医学和基因研究方面拥有深厚的专业知识&#xff0c;必将对LBC的使命&#xff0c;即安全…
阅读更多...
最新文章

Copyright @ 2022~2023