110.STL中的list

1.list的介绍

1.list是序列容器，允许在序列中的任何位置执行固定O(1)时间复杂度的插入和删除操作，并在两个方向进行迭代。
2.list容器使用双链表实现；双链表将每个元素存储在不同的位置，每个节点通过next，prev指针链接成顺序表。
3.list与其他标准序列容器（array，vector和deque）相比，list通常可以在容器内的任何位置插入、提取和移动元素。
4.list与其他标准序列容器（array，vector和deque）相比，list和forward_list（单链表实现）的主要缺点是他们不能通过位置直接访问元素；例如，要访问列表中的第五个元素，必须从已知位置（开始或结束）迭代到该位置，需要线性时间开销。
5.存储密度低，list要使用一些额外的内容空间（next，prev）来保持与每个元素相关联（前后续的线性）的链接信息，从而导致存储小元素类型（如char，short，int等）的列表的存储密度低。

2.list函数说明

2.1成员类型

2.2构造函数

例子：

#include <iostream>
#include <list>

using namespace std;

template<class T>
void Print(const list<T>& my)
{
	class list<T>::const_iterator it = my.begin();
	for (; it != my.end(); it++)
	{
		cout << *it << "\t";
	}

	cout << endl;
}

int main()
{
	list<int> list1 = { 12,23,34 };
	list<int> list2(3, 11);
	list<int> list3(list2);

	list<string> list4 = { "This","is","windows" };
	list<string> list5;
	list<string> list6;

	list5 = list4;

	list6.assign(3, "This");

	Print(list1);
	Print(list2);
	Print(list3);
	Print(list4);
	Print(list5);
	Print(list6);

	return 0;
}

输出：

12      23      34
11      11      11
11      11      11
This    is      windows
This    is      windows
This    This    This

2.3元素访问

例子：

#include <iostream>
#include <list>

using namespace std;

int main()
{
	list<int> list1 = { 12,23,34 };

	cout << "list1.front()：" << list1.front() << endl;
	cout << "list1.back()：" << list1.back() << endl;

	return 0;
}

输出：

list1.front()：12
list1.back()：34

2.4迭代器

例子：

#include <iostream>
#include <list>

using namespace std;

int main()
{
	list<int> list1 = { 12,23,34 };

	list<int>::const_iterator it1 = list1.begin();
	for (; it1 != list1.end(); it1++)
	{
		cout << *it1 << "\t";
	}

	cout << endl;

	list<int>::reverse_iterator it2 = list1.rbegin() ;
	for (; it2 != list1.rend(); it2++)
	{
		cout << *it2 << "\t";
	}

	cout << endl;
	
	return 0;
}

输出：

12      23      34
34      23      12

2.5容量

例子：

#include <iostream>
#include <list>

using namespace std;

int main()
{
	list<int> list1 = { 12,23,34 };

	cout << "list1.empty():" << list1.empty() << endl;
	cout << "list1.size():" << list1.size() << endl;
	cout << "list1.max_size():" << list1.max_size() << endl;

	return 0;
}

输出：

list1.empty():0
list1.size():3
list1.max_size():768614336404564650

2.6修改器

例子：

#include <iostream>
#include <list>

using namespace std;

template<class T>
void Print(const list<T>& my)
{
	typename list<T>::const_iterator it = my.begin();
	for (; it != my.end(); it++)
	{
		cout << *it << "\t";
	}

	cout << endl;
}

int main()
{
	list<int> list1 = { 12,23,34 };
	list<int> list2 = { 1,2,3,4,5 };
	
	Print(list1);
	Print(list2);
	auto it = list1.begin();
	list1.insert(it, 55);
	Print(list1);
	it++;
	list1.insert(it, 3, 55);
	Print(list1);

	list1.erase(it);
	Print(list1);

	list1.swap(list2);
	Print(list1);
	Print(list2);


	return 0;
}

输出：

12      23      34
1       2       3       4       5
55      12      23      34
55      12      55      55      55      23      34
55      12      55      55      55      34
1       2       3       4       5
55      12      55      55      55      34

2.7操作

例子：

#include <iostream>
#include <list>

using namespace std;

template<class T>
void Print(const list<T>& my)
{
	typename list<T>::const_iterator it = my.begin();
	for (; it != my.end(); it++)
	{
		cout << *it << "\t";
	}

	cout << endl;
}

int main()
{
	list<int> list1 = { 2,1,9,5,3,7 };
	list<int> list2 = { 1,8,3,6,0,1,5 };
	
	Print(list1);
	Print(list2);

	list1.sort();
	list2.sort();

	Print(list1);
	Print(list2);

	list2.unique();
	Print(list2);

	list1.merge(list2);
	Print(list1);
	Print(list2);

	return 0;
}

输出：

2       1       9       5       3       7
1       8       3       6       0       1       5
1       2       3       5       7       9
0       1       1       3       5       6       8
0       1       3       5       6       8
0       1       1       2       3       3       5       5       6       7       8       9

2.8vector和list区别

总结

1.vector底层实现是数组；list是双向链表。
2.vector支持随机访问，list不支持。
3.vector是顺序内存，list不是。
4.vector在中间节点进行插入删除会导致内存拷贝，list不会。
5.vector一次性分配好内存，不够时才进行扩容；list每次插入新节点都会进行内存申请。
6.vector随机访问性能好，插入删除性能差；list随机访问性能差，插入删除性能好。

vector和list的使用场景

vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随机存取，而不在乎插入和删除的效率（很少使用插入和删除操作），选用vector
list 拥有一段不连续的内存空间，如果需要大量的插入和删除的操作，随机存取很少使用，选用list。

参考: C++中list详解_c++ list_愚蠢的土拨鼠。的博客-CSDN博客

本栏目推荐文章
• python经典有序序列的list列表推导式
• String 类和 STL (Standard Template Library)
• Arrays.asList生成不可变list
• C#中的List<T>和Dictionary<TKey, TValue>的底层原理
• mybatis向xml文件传递list参数
• python基础之list、tuple、dict、set
• 获取直播间的最新评论 - python 取两个list的差集
• R语言用LOESS(局部加权回归)季节趋势分解（STL）进行时间序列异常检测
• C# 将string转list，将list转string
• 常用容器：动态数组array、列表list、队列 queue、map或字典、 集合、栈等等

list 110 STLlist 110 stl 容器2023 list stl 之间queue list stl list stl 容器vector list stl 110 v110 f110 110f 1268 110 spi hc