[数据结构与算法]【C++】STL——list的使用

🌈欢迎来到C++专栏~~list的使用

---

• (???(??? )🐣,我是Scort
• 目前状态：大三非科班啃C++中
• 🌍博客主页：张小姐的猫~江湖背景
• 快上车🚘，握好方向盘跟我有一起打天下嘞！
• 送给自己的一句鸡汤🤔：
• 🔥真正的大师永远怀着一颗学徒的心
• 作者水平很有限，如果发现错误，可在评论区指正，感谢🙏
• 🎉🎉欢迎持续关注！
  

一. list的介绍

list即带头双向循环链表，支持在任意位置O(1)的插入和删除

二. list的构造函数

方法一：无参构造

list<int> lt1; //构造int类型的空容器

方法二：n个val值构造

list<int> lt2(10,2)//构造10个值为2的int容器

方法三：拷贝构造

list<int> lt3(lt2)//lt2拷贝构造给lt3

方法四：迭代器区间构造

string s ("hello world")
list<int> lt4(s.begin(), s.end());

三. list的插入 & 删除

🎨push_front和pop_front

头插 头删

int main()
{
	list<int> lt;
	lt.push_front(0);
	lt.push_front(1);
	lt.push_front(2);

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

	lt.pop_front();

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

🎨push_back和pop_back

尾插尾删

int main()
{
	list<int> lt;
	lt.push_back(0);
	lt.push_back(1);
	lt.push_back(2);

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

	lt.pop_back();
	lt.pop_back();

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

🎨insert

list当中的insert函数支持三种插入方式：

• 指定位置插入一个数
• 指定位置插入n个val值的数
• 指定迭代器位置插入一段迭代器区间（左闭右开）

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	list<int>::iterator pos = find(lt.begin(), lt.end(), 3);
	if(pos != lt.end())
	{
		lt.insert(pos, 20);
	}

	for (auto e : lt)
	{
		cout << endl;
	}
	cout << endl;//20 1 2 3

	pos = find(lt.begin(), lt.end(), 3);
	if(pos != lt.end())
	{
		lt.insert(pos, 5, 30);//在三的位置插入5个30
	}

	for (auto e : lt)
	{
		cout << endl;
	}
	cout << endl;//20 1 2 30 30 30 30 30 3

	vector<int> v(2, 7);
	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
	if(pos != lt.end())
	{
	    lt.insert(pos, v.begin(), v.end()); //在1的位置插入2个7
	}
	
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //7 7 20 1 2 30 30 30 30 30 3
	return 0;
}

💢问：这里的pos会失效吗？

不会，在pos位置前增加一个节点，并改变链接关系，但pos还是指向原本的位置，也不存在野指针

ps：由于find是stl各个容器都需要的，所以实现在了头文件algorithm.h中

🎨erase

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);

	list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
	if (pos != lt.end())
	{
		lt.erase(pos); //删除2
	}

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 3 4 5
	pos = find(lt.begin(), lt.end(), 4);
	if (pos != lt.end())
	{
		lt.erase(pos, lt.end()); //删除4及其之后的元素
	}

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 3
	return 0;
}

💢灵魂发问：此处的pos会失效吗？

打印崩溃了，显而易见，删除后，再访问就是野指针了

四. list的迭代器的使用

🌊正向迭代器

话不多说，上代码

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

int main()
{
	list<int> lt(10, 2);
	//正向遍历
	list<int>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	return 0;
}

🌊反向迭代器

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

int main()
{
	list<int> lt(10, 5);
	//反向迭代器遍历容器
	list<int>::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
	return 0;
}

五. list元素的获取

🌍fornt & back

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	
	cout << lt.front() << endl; 
	cout << lt.back() << endl; 
	return 0;
}

六. list的操作函数

?splice 转移

int main()
{
	list<int> lt1(4, 2);
	list<int> lt2(4, 6);
	lt1.splice(lt1.begin(), lt2); //将容器lt2拼接到容器lt1的开头
	for (auto e : lt1)
	{
		cout << e << " ";
	}
	cout << endl; //6 6 6 6 2 2 2 2 

	list<int> lt3(4, 2);
	list<int> lt4(4, 6);
	lt3.splice(lt3.begin(), lt4, lt4.begin()); //将容器lt4的第一个数据拼接到容器lt3的开头
	for (auto e : lt3)
	{
		cout << e << " ";
	}
	cout << endl; //6 2 2 2 2 

	list<int> lt5(4, 2);
	list<int> lt6(4, 6);
	lt5.splice(lt5.begin(), lt6, lt6.begin(), lt6.end()); //将容器lt6的指定迭代器区间内的数据拼接到容器lt5的开头
	for (auto e : lt5)
	{
		cout << e << " ";
	}
	cout << endl; //6 6 6 6 2 2 2 2
	return 0;
}

ps： 容器当中被拼接到另一个容器的数据在原容器当中就不存在了。（移植技术）

?remove

remove函数用于删除容器当中特定元素

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(1);
	lt.push_back(1);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(1);
	lt.push_back(3);
	
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 1 1 3 2 2 1 3
	lt.remove(1); //删除容器当中值为1的元素
	
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; 
	return 0;
}

?remove_if

remove_if函数用于删除容器当中满足条件的元素

bool single_digit(const int& val)
{
	return val < 10;
}
int main()
{
	list<int> lt;
	lt.push_back(10);
	lt.push_back(4);
	lt.push_back(7);
	lt.push_back(18);
	lt.push_back(2);
	lt.push_back(5);
	lt.push_back(9);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //10 4 7 18 2 5 9
	lt.remove_if(single_digit); //删除容器当中值小于10的元素
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //10 18
	return 0;
}

?unique

unique函数用于删除容器当中连续的重复元素（前提是先排序）

int main()
{
	list<int> lt;
	lt.push_back(1);
	lt.push_back(4);
	lt.push_back(3);
	lt.push_back(3);
	lt.push_back(2);
	lt.push_back(2);
	lt.push_back(3);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //1 4 3 3 2 2 3
	lt.sort(); //升序
	lt.unique(); 
	for (auto e : lt)
	{
	 cout << e << " ";
	}
	cout << endl;
	return 0;
}

?sort

算法库里面已经有一个sort 了，为什么list里也实现了一个sort？

list的空间不是连续的，算法库中的sort要求物理空间要是连续的，所以vector和string才用，快排实现的参数取中，在链表实现不了

链表的sort是归并排序实现的

int main()
{
	list<int> lt;
	lt.push_back(4);
	lt.push_back(7);
	lt.push_back(5);
	lt.push_back(9);
	lt.push_back(6);
	lt.push_back(0);
	lt.push_back(3);
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //4 7 5 9 6 0 3
	lt.sort(); //默认升序
	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl; //0 3 4 5 6 7 9
	return 0;
}

📢写在最后

最近想玩植物大战僵尸了