本文已收录至《C++语言和高级数据结构》专栏！
作者：ARMCSKGT

前言

vector是一片连续的空间，在数据访问上性能较好，但是任意位置插入删除性能较低，头插头删性能亦是如此；此时在这种需要频繁插入的场景下，显然链表是一种更好的选择，STL中实现了带头双选循环链表，本次我们来介绍该如何使用STL中的链表list！

正文

本文理论依据来自于官方文档：STL容器list文档！
首先在使用list前，需要声明头文件 < list > 且声明命名空间std！
list是通过模板实例的泛型容器，需要指定类型进行实例化！

默认成员函数

---

构造函数类

• 默认构造
  –构造一个空对象，里面没有任何数据(底层上只有一个头节点)
• 构造n个值为val的链表对象
  –插入n个值实例类型的val值，构造一个对象
• 迭代器区间构造
  – 通过其他容器迭代器或指针构造一个list对象
• 列表初始化(C++11)
  – 对于支持C++11的编译器支持像数组一样使用列表{ }初始化
• 拷贝构造
  – 拷贝另一个list，从而构造一个一模一样的list对象

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

void Print(const list<int>& obj) //打印函数
{
	for (const auto& x : obj)
	{
		cout << x << " ";
	}
	cout << endl;
}

int main()
{
	list<int> l1; //默认构造

	list<int> l2(5, 1); //构造5个值为1(int类型)的链表对象
	Print(l2);

	int arr[] = { 5,4,3,2,1 };
	list<int> l3(arr, arr + 5); //指针作为迭代器区间构造
	Print(l3);

	vector<int> v = { 6,7,8,9,10 };
	list<int> l4(v.begin(),v.end()); //容器迭代器区间构造
	Print(l4);

	list<int> l5 = {11,12,13,14,15}; //列表初始化构造(C++11)
	Print(l5);

	list<int> l6(l5); //拷贝构造
	Print(l6);

	return 0;
}

---

---

赋值重载

赋值重载与拷贝构造类似，只不过赋值的前提是对象已存在，拷贝构造是初始化对象！

void Print(const list<int>& obj)
{
	for (const auto& x : obj)
	{
		cout << x << " ";
	}
	cout << endl;
}

int main()
{
	vector<int> v = { 5,4,3,2,1 };
	list<int> l1(v.begin(),v.end()); //容器迭代器构造

	list<int> l2(5, 1);
	Print(l2);
	l2 = l1;
	Print(l2);
	return 0;
}

---

---

析构函数

析构函数在list对象声明周期结束时调用，释放所有节点(包括头节点)！

迭代器

---

list迭代器比较特殊，知道链表的小伙伴应该都懂链表不是一片连续的空间，所以不能像顺序表那样支持迭代器随机访问！(即it+1，it+2…)

同样的，链表的迭代器也分三种(理论上四种)：

• 正向迭代器
• 反向迭代器
• const迭代器(正向和反向)
  
  const迭代器不支持修改当前指向的值，每一种迭代器不能混用，各自使用各自的迭代器类型！

int main()
{
	vector<int> v = { 5,4,3,2,1 };
	list<int> l1(v.begin(),v.end());
	list<int>::iterator it = l1.begin();
	list<int>::reverse_iterator rit = l1.rbegin();
	while (it != l1.end())
	{
		cout << *it << endl;
		++it;		
	}
	cout << endl;
	while (rit != l1.rend())
	{
		cout << *rit << endl;
		++rit;		
	}
	return 0;
}

虽然list迭代器不支持随机访问，但是也支持通过++和- -遍历链表，甚至可以反向遍历，可见迭代器的强大之处！

迭代器在链表中的位置：

容量操作类

---

数据查询类

链表没有提前开空间这样的说法，对于数据只能查询以及对现有数据操作！

• empty：查询链表是否为空，为空返回真
• size：返回当前节点的个数
• max_size：返回当前实例对象可容纳最大节点数(这个函数常用来检查申请空间的合法性即配合resize使用，查看申请的空间是否合法)
  

int main()
{
	list<int> obj(10,5); //初始化10个值为5的节点
	cout << "empty：" << obj.empty() << endl;
	cout << "size：" << obj.size() << endl;
	cout << "max_size：" << obj.max_size() << endl;

	return 0;
}

---

---

节点数量修改

list支持resize控制节点个数，resize支持增多节点和减少节点，对于增多的节点设置为val值，val有缺省参数，根据需要可进行设置初始化！

int main()
{
	list<int> obj = { 1,2,3,4,5 };
	cout << "size：" << obj.size() << endl;
	obj.resize(10);
	cout << "size：" << obj.size() << endl;
	obj.resize(3);
	cout << "size：" << obj.size() << endl;
	return 0;
}

数据访问

---

链表不支持下标访问，提供了额外对头尾节点访问的函数front和back，并且拥有引用和const引用重载函数应对不同的场景！

int main()
{
	list<int> obj = { 668,778,888,998,1080 };
	cout << "front：" << obj.front() << endl;
	cout << "back：" << obj.back() << endl;
	return 0;
}

不过list常用的遍历方式还是通过迭代器遍历，而且list因为迭代器所以支持范围for遍历！

增删类

---

因为链表插入删除效率非常高，所以增删类接口比较多，在这里介绍几种常用的接口！

---

---

头插头删

头插push_front() 和 头删pop_front() 只需要对头节点next(后继节点)指针操作即可！

int main()
{
	list<int> obj = { 1,2,3,4,5 };
	Print(obj);
	obj.pop_front();
	Print(obj);
	obj.push_front(668);
	Print(obj);

	return 0;
}

---

---

尾插尾删

头插push_back() 和 头删pop_back() 也只需要对头节点prev(前驱节点)指针操作即可！

int main()
{
	list<int> obj = { 1,2,3,4,5 };
	Print(obj);
	obj.pop_back();
	Print(obj);
	obj.push_back(668);
	Print(obj);

	return 0;
}

---

---

重新分配

assign函数有点类似于 = 赋值重载，区别于赋值的是该函数可以跨容器达到赋值的效果(利用迭代器区间)，assign函数会先将list对象清空再重新插入值！

assign函数有两个版本：

• 分配n个值为val的节点(类似于带参构造函数)
• 迭代器区间分配

int main()
{
	list<int> obj = { 1,2,3,4,5 };
	Print(obj);
	obj.assign(10, 5); //分配5个值为10的节点
	Print(obj);

	int arr[] = { 668 ,778,888,998,1080 };
	obj.assign(arr,arr+5); //分配arr数组区间
	Print(obj);

	return 0;
}

---

---

任意位置插入

insert函数支持在迭代器位置插入节点，有三个版本：

• 在position迭代器位置下插入值为val的节点(返回新插入节点的迭代器)
• 在position迭代器位置下插入n个值为val的节点
• 在position迭代器位置下插入一段区间

int main()
{
	list<int> obj = { 1,2,3,4,5 };
	auto it = ++obj.begin(); //记录2位置迭代器
	Print(obj);

	it = obj.insert(it, 668); //在2位置插入668更新迭代器为668节点
	Print(obj);

	obj.insert(it, 888); //在668位置插入888
	Print(obj);

	int arr[] = { 6,7,8,9,10 };
	obj.insert(obj.begin(), arr, arr + 5); //在头节点1位置插入arr数组区间
	Print(obj);

	return 0;
}

虽然insert函数不会导致迭代器失效，但是insert在插入单节点的函数上支持更新迭代器，必要时建议及时更新迭代器！

---

---

任意位置删除

erase函数有两种版本，删除函数需要注意迭代器失效问题，因为删除当前迭代器位置的节点后该位置节点内存已经被释放，所以两个版本的删除函数都会返回删除后的下一个节点迭代器！

int main()
{
	list<int> l1 = { 1,2,3 };
	list<int> l2 = { 1,2,3,4,5,6,7,8,9,10 };
	Print(l1);
	Print(l2);

	auto it1 = l1.begin();
	auto it2 = l2.begin();
	++it2; ++it2; ++it2;//迭代器挪动到4位置下

	it1 = l1.erase(it1); //删除手节点 - 更新迭代器
	it2 = l2.erase(l2.begin(),it2); //删除1-3区间节点(左闭右开) - 更新迭代器

	Print(l1);
	Print(l2);

	return 0;
}

迭代器失效情况：

对于单节点删除，如果不更新迭代器，肯定会造成野指针访问，但对于区间删除，因为是左避右开，所以删不到闭区间的迭代器，所以不更新迭代器影响不大，但是如果删除的区间是全部，则还是需要更新迭代器！
这里可以发现it1如果更新迭代器则指向下一个节点迭代器！

其他操作

---

清空函数

clear可以将链表清空，也就是逐个释放节点，只留下头节点(区别于析构函数，clear不会释放对象)！

int main()
{
	list<int> obj = { 1,2,3 };
	cout << "size:" << obj.size() << endl;
	obj.clear();
	cout << "size:" << obj.size() << endl;
	return 0;
}

---

---

交换函数

list有属于自己的交换函数，同时库中的函数也支持对list进行交换！

int main()
{
	list<int> l1 = { 1,2,3 };
	list<int> l2 = { 4,5,6 };
	cout << "l1:"; Print(l1);
	cout << "l2:"; Print(l2);
	cout << endl;

	l1.swap(l2); //list对象swap函数交换
	cout << "l1:"; Print(l1);
	cout << "l2:"; Print(l2);
	cout << endl;

	std::swap(l1, l2); //库函数交换
	cout << "l1:"; Print(l1);
	cout << "l2:"; Print(l2);
	cout << endl;

	return 0;
}

list自带的swap和库中的swap都支持容器的交换！

---

---

拼接

splice支持将一个list对象中的一个节点或者一段节点从原list对象上截取下来链接在调用对象上！
splice有三个版本：

• 将一个list截取插入到另一个list中的position迭代器位置
• 将一个list的一个迭代器节点截取插入另一个list中的position迭代器位置
• 将一个list的迭代器区间截取插入到另一个list中的position迭代器位置
  
  

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

	l1.splice(l1.begin(), l2); //将l2插入l1中
	cout << "l1:"; Print(l1);
	cout << "l2:"; Print(l2);
	cout << endl;

	list<int> l3 = { 1,2,3 };
	list<int> l4 = { 7,8,9 };
	l3.splice(l3.begin(),l4,l4.begin()); //将l4中的头节点插入l3中
	cout << "l3:"; Print(l3);
	cout << "l4:"; Print(l4);
	cout << endl;

	list<int> l5 = { 1,2,3 };
	list<int> l6 = { 448,558,668,778,888 };
	l5.splice(l5.begin(), l6, ++l6.begin(), l6.end()); //将l5的558-888插入l6中
	cout << "l5:"; Print(l5);
	cout << "l6:"; Print(l6);
	cout << endl;

	return 0;
}

splice函数每次执行都需要另一个list对象的引用，哪怕只截取一个节点，说明在函数内部需要对节点进行剥离和缝合！

splice函数原理：

---

---

移除指定值元素

remove类似于find+erase，find先找到这个值返回其迭代器供erase删除，该函数会根据给定的val值找到此值并删除，如果该值不存在，则什么也不做！

int main()
{
	list<int> l1 = { 1,2,3 };
	l1.remove(2); //删除2
	l1.remove(5); //删除非list中的元素则执行无效
	Print(l1);

	return 0;
}

---

---

排序

list自带排序算法，但效率非常低！

一般如果要对list排序，可以先将数据拷贝到vector，然后使用库函数sort快速排序后再拷贝会list，虽然有两次拷贝，但是排序性能仍然超过直接对list排序！

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

int main()
{
	list<int> l1;
	list<int> l2;
	for (int i = 1; i < 10000000; ++i) //一千万降序数
	{
		l1.push_back(i);
		l2.push_back(i);
	}
	//排升序	
	time_t t = clock(); //记录开始时间
	l1.sort(); //list排序
	cout << "list sort:" << clock() - t << endl;

	t = clock();
	vector<int> v(l2.begin(),l2.end());
	std::sort(v.begin(), v.end()); //库函数排序
	l2.assign(v.begin(), v.end()); //将排完序的元素分配回list
	cout << "lib sort:" << clock() - t << endl;

	return 0;
}

使用库函数sort需要声明头文件algorithm和std命名空间，此结果是在release模式下运行！
库函数对容器操作一般都是使用迭代器！

---

---

逆置

list对象自带reverse逆置函数，库中也有reverse函数，作用是将当前序列反过来！
list自带的reverse直接调用即可，库中的reverse则是通过容器迭代器作为参数进行逆置！

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

int main()
{
	list<int> obj = { 1,2,3,4,5,6,7,8,9,10 };
	Print(obj);
	obj.reverse(); //list自带逆置
	Print(obj);
	std::reverse(obj.begin(), obj.end()); //库函数逆置
	Print(obj);

	return 0;
}

同样的，使用库函数reverse需要声明头文件algorithm和命名空间std！

---

---

去掉重复元素

unique函数支持对元素，但是在去重之前需要进行排序，因为其底层原理是两个相邻的重复元素会删除一个，而需要将所有相同的元素相邻就需要sort排序！

同样的，如果数据量小我们可以直接使用list的排序和去重，如果数据量较大建议拷贝到vector排序然后拷贝会list再去重！

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

	obj.unique(); //不排序直接去重没有任何效果
	Print(obj);

	obj.sort(); //排序再去重才会有效果
	obj.unique();
	Print(obj);

	return 0;
}

算法库algorithm中也有unique，同样的适用于所有容器，因为使用迭代器操作！

---

---

合并

merge函数支持将一个list合并(移动)到另一个list中(而并非复制)，与splice函数类似，只不过merge是将list中的全部节点按升序或降序的方式链入被插入对象中，该函数有两种形式：

• 第一种是合并一个list，并按升序插入其中
• 第二种支持控制升序和降序，我们可以选择将list按升序插入其中，也可以按降序插入其中(使用greater和less控制)

int main()
{
	list<int> l1 = {6,10};
	list<int> l2 = { 1,2,5 };
	Print(l1);

	l1.merge(l2); //将l2按默认规则链入l1中
	Print(l1);

	list<int> l3 = {3,4,9,8,7};
	l1.merge(l3, less<int>()); //将l3按升序规则链入l1中
	Print(l1);

	return 0;
}

---

---

关于查找

• list没有提供查找函数，因为对于链表的查找只能用迭代遍历的方式进行，所以用库中的find足以！
• 库中的find也是基于迭代器的遍历查找，也适用于所有支持迭代器的容器，find如果查找到了就会返回该元素的迭代器，如果没找到则返回传入的开区间(end())迭代器，如果有多个重复的值则返回正向序列上第一个符号条件的值！

//find的使用
find(迭代器开区间(起始区间)，迭代器闭区间(结束区间)，查找元素);

find底层原理：

template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
 	while (first!=last) {
    if (*first==val) return first;
    	++first;
	}
 return last;
}

使用展示：

int main()
{
	list<int> obj = { 1,2,5,3,7,1,6,5,9,8,7,2 };
	list<int>::iterator it = std::find(obj.begin(), obj.end(), 2); //找到了就返回迭代器
	cout << *it << endl;
	it = std::find(obj.begin(), obj.end(), 10);
	cout << (it == obj.end()) << endl; //没找到返回开区间
	return 0;
}

find属于库函数，需要algorithm算法头文件和是他的命名空间！

最后

list的使用介绍到这里就结束了，相信学会了list在需要频繁增删数据的场景下我们那个轻松应对，对于vector和list两者各有优劣，应对不同的场景我们需要合理应用甚至结合使用；list的底层实现非常值得我们去研究，C++下一节将为大家介绍list模拟实现，揭开迭代器的背后秘密！

本次 <C++ list的使用> 就先介绍到这里啦，希望能够尽可能帮助到大家。

如果文章中有瑕疵，还请各位大佬细心点评和留言，我将立即修补错误，谢谢！

?其他文章阅读推荐?
C++ <STL之vector模拟实现> -CSDN博客
C++ <STL之vector的使用> -CSDN博客
C++ <STL之string的使用> -CSDN博客
C++ <STL之string模拟实现> -CSDN博客
?欢迎读者多多浏览多多支持!?

​​

​​

​
​