【C++】第十二节——详解list（上）—（list的介绍和使用、模拟实现）

发布于：2025-06-24 ⋅ 阅读:(15) ⋅ 点赞:(0)

Hi，我是云边有个稻草人，一个偶尔中二的C++方向在学博主^(*￣(oo)￣)^，与你分享所学知识

C++—本节课所属专栏—持续更新中—欢迎订阅！

目录

一、list的介绍和使用

1.1 list的介绍—带头双向循环链表

1.2 list的使用

（1）list的构造

（2）list iterator的使用

（3）list capacity

（4）list element access

（5）list modifiers

【补充1】——push_back类和emplace_back类的区别

【补充2】vector和list使用sort的区别

【vector下和list下sort性能的区别—Release】

1.3 关于上面list的使用所写的全部代码

二、list模拟实现

2.1 模拟实现list

list.h 

list.cpp

正文开始——

一、list的介绍和使用

1.1 list的介绍—带头双向循环链表

list - C++ Reference—list文档介绍

1.2 list的使用

list中的接口比较多，此处类似，只需要掌握如何正确的使用，然后再去深入研究背后的原理，已达到可扩展的能力。以下为list中一些常见的重要接口。

（1）list的构造
构造函数 接口说明
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
（2）list iterator的使用

此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。

函数声明

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

【注意】

  1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
  2. rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动
（3）list capacity
函数说明 接口说明
empty 检测list是否为空，是返回true，否则返回false
size 返回list中有效节点的个数
（4）list element access
函数说明 接口说明
front 返回list的第一个节点中值的引用
back 返回list的最后一个节点中值的引用

（5）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中的有效元素
【补充1】——push_back类和emplace_back类的区别

（这里涉及到前面几节所讲的拷贝构造，隐式类型转换，直接构造啥的，要是忘记了就，反正我是痛苦。复习回来啦，我爱C++）

​
int main()
{
	list<Pos> lt;
	Pos p1(1, 1);

	//构造+拷贝构造
	lt.push_back(p1);//有名对象，先创建一个对象，再将对象进行push_back
	lt.push_back(Pos(2, 2));//匿名对象
	lt.push_back({ 2,2 });//隐式类型转换

	lt.emplace_back(p1);//那是一个模版，传一个Pos类型的对象，模版参数推出形参的类型为Pos
	lt.emplace_back(Pos(2,2));//对于匿名对象，emplace_back的模版参数也可以推导出为Pos类型
	//lt.emplace_back({ 2,2 });

	//直接构造
	lt.emplace_back(3, 3);//但是可以支持这样玩，直接将初始化pos的值给它传过去

	return 0;
}
  • 下面的拷贝构造，是将形参的pos拷贝构造到链表中的节点里面
  • lt.push_back({1,1});//本质是隐式类型转换—>这里也是构造+拷贝构造（隐式类型转换，实参传给形参，先用(1,1)构造一个临时对象，形参引用的是临时对象，这种场景下就解释了为什么形参的部分要加上const，因为它引用的临时对象具有常性！）
  • lt.emplace_back(1, 1);//不仅仅可以传pos类型的对象，也可以传构造链表里面pos的参数直接最后去构造pos，所以形参也叫可变模版参数

所以相比于push_back，emplace_back的高效之处仅在于直接构造的那种情况！

【补充2】vector和list使用sort的区别
int main()
{
		list<int> lt1 = { -1,90,100,-8,34 };

		for (auto e : lt1)
		{
			cout << e << " ";
		}
	
		cout << endl;

		//排序sort，默认是升序，less
		lt1.sort();
		for (auto e : lt1)
		{
			cout << e << " ";
		}

		cout << endl;

		//排降序 >
		greater<int> gt;//有名对象做实参，干脆直接用匿名对象:lt1.sort(greater<int>());
		lt1.sort(gt);
		for (auto e : lt1)
		{
			cout << e << " ";
		}

		cout << endl;


		//对于vector，算法库里面有现成的sort，现在试用一下
		vector<int> v1 = { 1,3,-2,90,9 };
		for (auto e : v1)
		{
			cout << e << " ";
		}

		cout << endl;

		//默认是升序
		//sort(v1.begin(), v1.end());
		sort(v1.begin(), v1.end(), greater<int>());//现在加入仿函数，> 是降序
		for (auto e : v1)
		{
			cout << e << " ";
		}

		cout << endl;

		//但是list就不可以使用算法库里面的sort，只能用STL里面的sort
		//sort(lt1.begin(), lt2.end(), greater<int>());

		return 0;
}

运行结果见下： 

（vector的sort底层是递归，算法库里面的sort底层是归并） 

【vector下和list下sort性能的区别—Release】

下面是在Release下，对vector使用算法库里面的sort和list使用自己实现的sort各自效率的测试

void test_op1()
{
	srand((unsigned int)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给vector排序
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt1.sort();//默认排升序
	int end2 = clock();

	cout << "vector sort:" << end1 - begin1 << endl;
	cout << "list sort:" << end2 - begin2 << endl;

}

void test_op2()
{
	srand((unsigned int)time(0));
	const int N = 1000000;

	list<int> lt1;
	list<int> lt2;

	for (size_t 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();

	cout << "vector sort(copy):" << end1 - begin1 << endl;
	cout << "list sort:" << end2 - begin2 << endl;
}

int main()
{
	test_op1();
	test_op2();
	return 0;
}

运行结果如下：显而易，要排序的话最好使用vector，vector排序的效率更高！ 

 list中还有一些操作，需要用到时大家可参阅list的文档说明。

1.3 关于上面list的使用所写的全部代码

#include<iostream>
#include<list>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);
	lt1.push_back(5);

	list<int>::iterator it1 = lt1.begin();
	while (it1 != lt1.end())
	{
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;

	list<int> lt2 = { 1,2,3,4,5,6 };
	for (auto e : lt2)
	{
		cout << e << " ";
	}

	cout << endl;

	return 0;
}

class Pos
{
	int _row;
	int _col;

public:
	Pos(int row, int col)
		:_row(row)
		, _col(col)
	{ }
};

int main()
{
	list<Pos> lt;
	Pos p1(1, 1);

	//构造+拷贝构造
	lt.push_back(p1);//有名对象，先创建一个对象，再将对象进行push_back
	lt.push_back(Pos(2, 2));//匿名对象
	lt.push_back({ 2,2 });//隐式类型转换

	lt.emplace_back(p1);//那是一个模版，传一个Pos类型的对象，模版参数推出形参的类型为Pos
	lt.emplace_back(Pos(2,2));//对于匿名对象，emplace_back的模版参数也可以推导出为Pos类型
	//lt.emplace_back({ 2,2 });

	//直接构造
	lt.emplace_back(3, 3);

	return 0;
}

int main()
{
	list<int> lt1 = { 1,2,3,4,5 };
	for (auto e : lt1)
	{
		cout << e << " ";
	}

	cout << endl;

	int x;
	cin >> x;
	auto it = find(lt1.begin(), lt1.end(), x);

	if (it != lt1.end())
	{
		lt1.erase(it);
	}

	for (auto e : lt1)
	{
		cout << e << " ";
	}

	cout << endl;

	//逆置
	lt1.reverse();
	for (auto e : lt1)
	{
		cout << e << " ";
	}

	cout << endl;

	return 0;
}


int main()
{
	list<int> lt1 = { 1,2,3,4,5,6 };

	//LRU最近最少用,将最近最少使用的调到前面去
	int x;

	while (cin >> x)
	{
		auto pos = find(lt1.begin(), lt1.end(), x);//直接调用算法库里面的find
		lt1.splice(lt1.begin(), lt1, pos);//学会查看文档学习这些接口的用法

		for (auto e : lt1)
		{
			cout << e << " ";
		}

		cout << endl;

	}
	return 0;
}


int main()
{
		list<int> lt1 = { -1,90,100,-8,34 };

		for (auto e : lt1)
		{
			cout << e << " ";
		}
	
		cout << endl;

		//排序sort，默认是升序，less
		lt1.sort();
		for (auto e : lt1)
		{
			cout << e << " ";
		}

		cout << endl;

		//排降序 >
		greater<int> gt;//有名对象做实参，干脆直接用匿名对象:lt1.sort(greater<int>());
		lt1.sort(gt);
		for (auto e : lt1)
		{
			cout << e << " ";
		}

		cout << endl;


		//对于vector，算法库里面有现成的sort，现在试用一下
		vector<int> v1 = { 1,3,-2,90,9 };
		for (auto e : v1)
		{
			cout << e << " ";
		}

		cout << endl;

		//默认是升序
		//sort(v1.begin(), v1.end());
		sort(v1.begin(), v1.end(), greater<int>());//现在加入仿函数，> 是降序
		for (auto e : v1)
		{
			cout << e << " ";
		}

		cout << endl;

		//但是list就不可以使用算法库里面的sort，只能用STL里面的sort
		//sort(lt1.begin(), lt2.end(), greater<int>());

		return 0;
}


void test_op1()
{
	srand((unsigned int)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给vector排序
	sort(v.begin(), v.end());
	int end1 = clock();

	int begin2 = clock();
	lt1.sort();//默认排升序
	int end2 = clock();

	cout << "vector sort:" << end1 - begin1 << endl;
	cout << "list sort:" << end2 - begin2 << endl;

}

void test_op2()
{
	srand((unsigned int)time(0));
	const int N = 1000000;

	list<int> lt1;
	list<int> lt2;

	for (size_t 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();

	cout << "vector sort(copy):" << end1 - begin1 << endl;
	cout << "list sort:" << end2 - begin2 << endl;
}

int main()
{
	test_op1();
	test_op2();
	return 0;
}

二、list模拟实现

2.1 模拟实现list

要模拟实现list，必须要熟悉list的底层结构以及其接口的含义，通过上面的学习，这些内容已基本掌握，现在我们来模拟实现list。

list.h 
#pragma once

namespace lrq
{
	//模版
	//定义list里面结点的结构
	//虽然struct是全公开的，但是我们在使用list这个容器的接口的时候感受不到这些底层，
	//也不知道这些变量的命名，这其实也算一种隐形的封装
	template<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 Node;
		typedef list_iterator<T> Self;

		Node* _node;

		//类封装结点指针，重载运算符，模拟指针的行为
		list_iterator<T>(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();
		}


	};

	//class和struct的区别是什么？没有用访问限定符修饰的，struct是共有的，class是私有的
	//惯例：如果一个类既有公有也有私有就用class，全部是公有默认用struct
	template<class T>
	class list
	{
		typedef list_node<T> Node;//定义成类里面的typedef，和全局的typedef的区别是，
									//类里面的typedef中Node受访问限定符的限制，外部不能随意访问Node
	public:
		typedef list_iterator<T> iterator;
		void empty_init()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}

		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_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;//哨兵位头结点
	};

}

运算符重载-> ,第一个->的结果是Pos*，第二个是找Pos这个结构体里面的_row。

list.cpp
#include<iostream>
#include"list.h"

using namespace std;

//class Pos
//{
//	int _row;
//	int _col;
//
//public:
//	Pos(int row, int col)
//	{
//		_row = row;
//		_col = col;
//	}
//};

//int main()
//{
//	list<int> lt1;
//
//	lt1.push_back(1);
//	lt1.push_back(2);
//	lt1.push_back(3);
//	lt1.push_back(4);
//
//	list<int>::iterator it1 = lt1.begin();
//	//迭代器
//	while (it1 != lt1.end())
//	{
//		cout << *it1 << " ";
//		it1++;
//	}
//
//	//范围for
//	for (auto e : lt1)
//	{
//		cout << e << " ";
//	}
//
//	cout << endl;
//
//	Pos pos(1, 1);//调用有参的构造函数
//	list<Pos> lt;
//	lt.push_back(pos);//有名对象
//	lt.push_back(Pos(1,1));//匿名对象
//	lt.push_back({1,1});//本质是隐式类型转换
//
//	lt.emplace_back(pos);
//	lt.emplace_back(Pos(1, 1));
//	lt.emplace_back(1, 1);//用两个形参直接构造节点里面的pos

//	return 0;
//}

//int main()
//{
//	list<int> lt1 = { 1,2,3,4,5 };
//
//	int x;
//
//	while (cin >> x)
//	{
//
//		auto e = find(lt1.begin(), lt1.end(), x);
//		lt1.splice(lt1.begin(), lt1, e);
//
//		for (auto e : lt1)
//		{
//			cout << e << " ";
//		}
//		cout << endl;
//	}
//
//
//	return 0;
//}


//int main()
//{
//	list<int> lt = { 90,199,3,4,78 ,-9};
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//
//	cout << endl;
//
//	greater<int> gt;
//	//lt.sort(gt);
//	lt.sort(greater<int>());//传匿名对象，类型名+（）
//
//	lt.sort();//默认排升序 < 
//
//	for (auto e : lt)
//	{
//		cout << e << " ";
//	}
//
//	cout << endl;
//
//	return 0;
//}



int main()
{
	lrq::list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);
	lt1.push_back(5);

	lrq::list<int>::literator it1 = lt1.begin();

	while (it1 != lt1.end())
	{
		//*it1 = 2;也可以写数据
		cout << *it1 << " ";
		++it1;
	}
	cout << endl;

	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl;

	return 0;
}

完——

今天就到这里，剩下的list明天继续，我猜我明天还会更新list博客

This Is Who I Am

—— Jackal  

至此结束——

我是云边有个稻草人

期待与你的下一次相遇。。。。。。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布