C++的“链”珠妙笔：list的编程艺术-EW帮帮网

前言

在 C++ 标准模板库（STL）中， list 是一个非常强大且灵活的容器。它基于双向链表实现，提供了高效的插入和删除操作，非常适合需要频繁修改数据的场景。小编将详细介绍 list 的特性、操作方法以及一些使用示例，帮助你更好地理解和掌握这个容器

一、 list的介绍

list的结构：

list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素，每个元素都保留有关如何定位下一个和上一个元素的信息，允许在特定元素 (甚至整个范围) 之前或之后进行恒定时间的插入和擦除操作，但没有直接随机访问。

list的性质：

t是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代，list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效，与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好，与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问

list 的基本特性:

动态大小： list 的大小可以动态变化，可以根据需要插入或删除元素
高效插入和删除：由于基于双向链表实现， list 在任意位置插入或删除元素的时间复杂度为 O(1)，非常高效
无连续内存存储： list 的元素不存储在连续的内存块中，因此不支持随机访问。访问元素需要通过迭代器逐个遍历
支持双向遍历： list 提供了正向和反向迭代器，可以方便地从头到尾或从尾到头遍历容器

二、list的使用

2.1 list的构造函数

(迭代器==指针)

构造函数用n个val值进行初始化构造对象
构造函数用迭代器进行初始化构造对象代器，(这里的迭代器实际上是模拟的指针行为)，也就是说我们也可以传数组的指针进行初始化一个对象

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

using namespace std;

int main()
{
	list<int> lt1;
	list<int> lt2(6, 6);//(用n个val值进行初始化构造对象) It2 : 6,6,6,6,6,6
	list<int> lt1(lt2.begin(), lt2.end());//(用区间迭代器构造对象）It1 : 6,6,6,6,6,6
	int arr[] = { 1,2,3,4 };
	list<int> lt3(arr, arr + 4);//It3 : 1,2,3,4
}

2.2 list 拷贝构造函数

拷贝构造函数传list类型的对象进行拷贝

list<int> lt1(6, 6);
list<int> lt2(lt1);// It2 : 6,6,6,6,6,6

2.3 list 析构函数

析构函数在对象生命周期结束的时候会自动进行调用完成对象中资源清理工作，释放空间

2.4 list 赋值运算符重载 operator=

赋值运算符重载 operator= 可以使用类对象的数据覆盖掉其它类对象的数据的原本内容，如果其它类对象为空，那么将会被调用拷贝构造函数

list<int> lt1(3, 3);
list<int> lt2(3, 4);

lt1= lt2;// It1 : 4,4,4
list<int> It3;
It3=It1;// 调用拷贝构造函数 It3 = 4，4，4

2.5 list Iterators

迭代器类型从方向可以分为正向迭代器和反向迭代器,从属性分为不限定和const限定
begin(),end(),rbegin(),rend()用于获取开头或结尾位置的地址

int arr[] = { 1,2,3,4,5 };
list<int> lt(arr, arr + 7);

list<int>::iterator it = lt.begin();//*it== 1
	
list<int>::reverse_iterator rit = lt.rbegin();//*rit=5

迭代器正向遍历反向遍历

while (it != lt.end())
{
	cout << *it << ' '; // 1，2，3，4，5
	it++;
}

迭代器反向遍历

while (rit != lt.rend())
{
	cout << *rit << ' ';// 5，4，3，2，1
	rit++;
}

2.6 list - Capacity

判断数据是否为空，为空返回true，不为空false

size返回对象中的有效数据个数

返回元素的最大数量列表容器可以容纳元素的最大数量

2.7 list - Element access

front返回第一个位置的数据的引用

back返回最后一个位置的数据的引用

引用可以对该位置进行访问或修改

int arr[] = { 1,2,3,4,5};
list<int> lt(arr, arr + 5);
cout << lt.front() << endl;//front : 1
cout << lt.back() << endl;//back : 5

2.8 list - Modifiers

assign会将要传入数据的对象的原有的数据全部清空，再使用一段迭代器区间对应的数据或者使用n个z值val去分派，替代list实例化的对象的数据，并且会相应调整有效数据的个数

    int arr[] = { 1,2,3,4,5 };
	list<int> lt(arr, arr + 5);

	list<int> lt1;
	lt1.assign(lt.begin(), lt.end());//It1 : 1,2,3,4,5

	list<int> lt2;
	lt2.assign(6, 6);//6,6,6,6,6,6

头插

头删

后插

后删

    list<int> lt;
	lt.push_front(1);
	lt.push_front(2);
	lt.push_front(3);
	lt.push_front(4);

	lt.pop_front();//It : 2,3,4

	lt.push_back(5);
	lt.push_back(6);
	lt.push_back(7);//It : 2,3,4,5,6,7

	lt.pop_back();//It : 2,3,4,5,6

在vector中，vector 的insert涉及到迭代器的失效的问题，而在list中的insert不会涉及到迭代器的失效，因为插入是在节点之间的插入，改变的是节点之间的链接关系，不会进行类似于vector中的异地扩容空指针问题
insert在pos位置之前插入一个值，其返回值是新插入元素的地址
insert可以在迭代器位置之前插入n个相同的值
insert可以在迭代器位置之前插入一段迭代器区间

    int arr[] = { 1,2,3,4,5 };
	list<int> lt(arr, arr + 5);

	list<int>::iterator pos = lt.begin();

	lt.insert(pos, 0);// It : 0,1,2,3,4,5
	pos++;//pos==1
	lt.insert(pos, 2, 2);//0,2,2,1,2,3,4,5
	
	list<int> lt1(3, 3);
	lt.insert(pos, lt1.begin(), lt1.end()); // It1 : 0,2,2,3,3,3,1,2,3,4,5

（迭代器 == 地址)

在list中的erase会涉及迭代器的失效问题，erase进行删除是释放迭代器指向的节点，并且改变节点之间的链接关系，既然迭代器指向的节点被释放了，这时候迭代器就失效了，再使用迭代器去访问这个节点就会报错
erase会返回一个迭代器，这个迭代器是被删除节点的下一个位置的迭代器，如果我们还想继续进行操作，应该使用一个迭代器去接收erase的返回值，不应该再使用那个已经失效的迭代器
erase可以删除某一个迭代器位置或者一个迭代器区间

    int arr[] = { 1,2,3,4,5 };
	list<int> lt(arr, arr+5);


	lt.erase(--lt.end());//It : 1,2,3,4
	
	lt.erase(lt.begin(), lt.end());// It : 空

用来交换两个list对象的数据

resize是用于改变list有效数据的大小，如果n小于当前size，那么会将多余的部分删除销毁，如果n大于当前大小，那么会尾插入val，如果用户没有显示的给出val值，那么会使用缺省值，即默认构造生成的值

用于清空 list 对象的数据

2.9 list - Operations

splice将对象 x 中的节点和调用splice中的节点进行拼接，拼接后对象 x 中用于拼接的节点将会被链接到splice节点前，对象x中用于拼接的节点就不在对象x中了
可以将一个list对象x中的全部节点拼接到pos位置之前

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

	list<int> lt1;

	lt1.push_back(4);
	lt1.push_back(5);
	lt1.push_back(6);

	lt.splice(lt.begin(), lt1);// 把It1 全拼接到It.begin()前面,It : 4,5,6,1,2,3

将一个list对象x中i迭代器对应位置的单个节点拼接到pos位置之前

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

	list<int> lt1;

	lt1.push_back(4);
	lt1.push_back(5);
	lt1.push_back(6);

	lt.splice(lt.begin(), lt1,lt1.begin());// 把lt1 全拼接到lt.begin()前面,lt : 4,1,2,3

将一个list对象x中的一段迭代器区间内包含的所有节点拼接到pos位置之前

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

	list<int> lt1;

	lt1.push_back(4);
	lt1.push_back(5);
	lt1.push_back(6);

	lt.splice(lt.begin(), lt1,lt1.begin(),lt1.end());// 把lt1 全拼接到lt.begin()前面,lt : 4,5,6,1,2,3

移除list中的节点的数据为val的所有节点

    list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(2);
    lt.remove(2);//lt : 1

将list中的重复数据的节点进行删除释放，只保留这些重复数据节点中的一个数据节点

    list<int> lt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(2);
    lt.unique();//lt : 1

叫拼接更好，将一个list对象x的数据拼接到另一个list对象的最后面去(调用完之后对象x的有效数据个数为0)
两个对象都应该提前调用sort确保数据是有序的，进行merge的前提是两个对象的数据是有序的

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

	list<int> lt1;

	lt1.push_back(4);
	lt1.push_back(5);
	lt1.push_back(6);

	lt.merge(lt1);//lt1 : 空, lt : 1,2,3,4,5,6

用于对list对象的数据进行排序,算法库中也有sort，但不能用，list中的sort的底层是使用的归并排序的非递归方式，库中的sort的底层是快速排序，由于list的物理空间是不连续的，不支持三数取中，库中的sort不支持对list这种双向迭代器进行排序

对list的数据进行逆置，而在stl的算法中同样也有传入迭代器区间进行逆置的reverse，两者的功效都是相同的

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
reverse(lt.begin(),lt.end());// 库里的
lt.reverse()// 与库里的效果一样

总结

list 的使用场景 ：

频繁修改数据：如果需要频繁地在容器的任意位置插入或删除元素， list 是一个很好的选择
需要双向遍历：如果需要从头到尾或从尾到头遍历容器， list 的双向迭代器可以方便地实现
不关心随机访问：如果不需要随机访问元素， list 的性能优势会更加明显

感谢您耐心阅读本文！希望通过以上内容，您对 list 有了更深入的理解。技术的世界总是充满挑战与机遇，而每一次探索都可能带来新的突破。如果您在阅读过程中有任何疑问、建议或想法，欢迎在评论区留言，让我们共同交流、共同进步。同时，如果您觉得这篇文章对您有所帮助，也别忘了给小编点赞和分享哦！我们下期再见！

C++的“链”珠妙笔：list的编程艺术

前言