文章目录一、从链表认识 list二、不同构造方式2.1 比较一些容易混淆的构造方式2.2 打印构造结果验证复制是否独立三、访问与遍历迭代器是位置不是下标3.1 front() / back() 返回元素引用3.2 begin() / end() 表示半开区间3.3 遍历方式四、增删改查先找位置再执行操作4.1 修改元素与修改序列4.2 自定义类型插入push_back 与 emplace_back五、迭代器有效性与遍历删除5.1 list 的稳定性来自节点而不是元素数值5.2 删除当前元素后让返回值接管遍历位置六、排序、去重、合并与节点转移6.1 为什么 list 有成员 sort6.2 reverse 保持位置不等于保持遍历顺序6.3 unique 相邻去重完全去重前提是有序6.4 merge 的前提是两个序列按相同规则有序6.5 splice 转移节点单个节点或是一整段七、list 的相关功能成本下篇list迭代器与资源管理实现的综合叙述下代码仓库《list类测试与实现》一、从链表认识 liststd::listT是标准库的双向序列容器包含头文件listT表示元素类型。带哨兵位双向循环链表的每个节点保存一个元素并通过连接找到前后节点。各元素在物理空间存储时不要求位于连续地址所以不能通过“起始地址加偏移”找到第几个元素也不能用[]或at()按下标访问。创建局部list对象后容器负责创建和销毁元素、管理节点存储对象离开作用域时自动清理。二、不同构造方式2.1 比较一些容易混淆的构造方式和string与vector一样list也有着丰富的构造方式写法初始元素要留意的地方std::listint l;空对象存在但没有元素std::listint l(5);五个 0创建五个元素不是预留五个位置std::listint l(5, 2);五个 2圆括号数量与初值std::listint l{5, 2};5、2花括号这里选中元素列表构造std::listint b(a);复制 a 的元素节点独立管理std::listint b a;同样复制 a新对象的初始化不是已有对象赋值std::listint l(first, last);复制[first,last)不包含 last 位置整数的数量构造得到 0自定义类型则按对应构造规则创建元素。区间构造必须提供有效范围不能跨两个无关容器取起点和终点。2.2 打印构造结果验证复制是否独立#includeiostream#includelistintmain(){//使用循环给l1初始化std::listintl1;for(inti0;i5;i)l1.push_back(1);//初始化l2 5个2再拷贝构造给l3std::listintl2(5,2);std::listintl3(l2);//使用已有容器构造inta[]{3,4,5};std::listintl4(a,a3);//使用列表初始化std::listintl5{5,2};std::listintl6(5);std::coutl6.size() l6.front()std::endl;//依次打印查看l3、l4、l5for(intx:l3)std::coutx ;std::coutstd::endl;for(intx:l4)std::coutx ;std::coutstd::endl;for(intx:l5)std::coutx ;std::coutstd::endl;l3.front()9;std::coutl2.front() l3.front()std::endl;return0;}运行示例std::listint l6(5);→ 创建5 个元素值初始化为 0输出5 0l2(5,2)5 个 2l3(l2)拷贝构造l3为独立链表元素与l2相同l4(a, a3)区间[a,a3)数组{3,4,5}-3 4 5l5{5,2}花括号初始化列表两个元素5、2l3.front() 9;修改 l3 第一个节点l2.front()仍然是2l3.front()变成9三、访问与遍历迭代器是位置不是下标3.1 front() / back() 返回元素引用非const容器的front()、back()返回的是可修改引用因此l.front() 10会改变元素。const容器则返回只读引用。std::listintl;if(!l.empty())l.back()10;empty()判断是否为空size()返回当前元素数量。list没有capacity()和reserve()节点随着元素增删来管理。3.2 begin() / end() 表示半开区间begin()指向首元素end()是尾后位置。空链表中二者相等。list 的迭代器是双向迭代器支持*it、it-成员、it、--it、相等比较。但它不支持随机跳转和大小关系比较因此it 2、it1 - it2、it end()都不是正确写法。3.3 遍历方式与vector不同的是list迭代器并不支持下标访问或者加减一个数值来得到元素位置。#includeiostream#includelistintmain(){std::listintl1;l1.push_back(1);l1.push_back(1);l1.push_back(1);l1.push_back(1);l1.push_back(1);for(auton:l1){std::coutn ;}std::coutstd::endl;std::listintl2(5,2);std::listintl3(l2);std::listint::iterator itl3.begin();while(it!l3.end()){std::cout*it ;it;}std::coutstd::endl;return0;}运行示例范围 forfor(auto n : l1)迭代器while (it ! l3.end ())list迭代器双向迭代器只支持it/--it不支持it 2这种随机访问。判断条件it ! l3.end()不能用list迭代器不支持大小比较只能相等 / 不等判断。容器迭代器类型支持运算vector随机访问迭代器it end()、it nlist双向迭代器只能it--it禁止 比较四、增删改查先找位置再执行操作4.1 修改元素与修改序列操作效果与返回值边界push_front(x)/push_back(x)头插 / 尾插返回void空链表也可使用pop_front()/pop_back()删除首 / 尾元素返回void必须非空insert(pos,x)在 pos 前插入返回新元素迭代器pos可为endinsert(pos,n,x)在 pos 前插入 n 个 x注意 n 是数量insert(pos,first,last)插入指定来源范围的副本来源范围有效不能来自同一个目标listerase(pos)删除pos返回后继pos必须指向本容器元素不能是enderase(first,last)删除[first,last)返回后续位置空范围可删除范围必须有效clear()删除全部元素空容器也可调用resize(n,x)缩小时删尾部增大时追加 x无 x 时按默认规则初始化新元素assign(n,x)/assign(first,last)用新内容替换全部旧内容区间版本不使用本容器自身迭代器作为来源swap(other)交换两个容器的内容不是逐个复制元素4.2 自定义类型插入push_back 与 emplace_back#includeiostream#includeliststructA{int_a1;int_a2;A(inta10,inta21):_a1(a1),_a2(a2){}};intmain(){std::listAl;Aa(1,10);l.push_back(a);l.push_back(A(2,20));l.emplace_back(3,30);for(autoitl.begin();it!l.end();it)std::coutit-_a1 it-_a2std::endl;}push_back只接收一个元素对象而emplace_back(3,30)会把参数用于在节点中构造 A。这里只需掌握调用层面的差别不展开底层参数转发。五、迭代器有效性与遍历删除5.1 list 的稳定性来自节点而不是元素数值插入一个节点原节点无需整体搬移已有元素的迭代器和引用也保持有效。删除一个节点只让指向被删元素的迭代器、引用和指针失效。但即使后来在相同地址新建节点也不能据此继续使用旧迭代器。操作指向元素的迭代器 / 引用 / 指针插入、头尾插、emplace原有元素的位置保持有效erase、pop、remove、unique指向被删除元素的失效其余保留clear所有元素位置失效resize增大保留原有位置缩小使被删尾部位置失效成员sort、成员reverse元素位置保持有效遍历顺序可改变splice、merge被转移元素的位置仍有效但归属变为目标容器swap元素位置仍有效但元素归属交换assign、复制赋值不依赖操作前的元素位置完成后重新获取5.2 删除当前元素后让返回值接管遍历位置#includeiostream#includelistintmain(){std::listintl{1,2,3,4,5,6};//取list开头位置迭代器autosavedl.begin();//取开头迭代器地址int*address*saved;//观察插入删除开头元素后迭代器地址是否变化l.insert(saved,0);std::cout(*saved1) (*savedaddress)std::endl;l.erase(l.begin());std::cout(*saved1) (*savedaddress)std::endl;autoitl.begin();while(it!l.end()){//删除list中的偶数if(*it%20){itl.erase(it);}elseit;}//遍历打印此时list元素for(intx:l)std::coutx ;std::coutstd::endl;//再次观察此时开头元素迭代器地址变化std::cout*saved (*savedaddress)std::endl;return0;}运行示例saved l.begin()指向元素1address保存1的内存地址。l.insert(saved, 0);在 1 前面插入 0list 插入不失效原有迭代器saved依旧指向节点1节点内存地址没变所以*saved1、*saved address输出1 1。l.erase(l.begin());删除链表最前面的0。删除的是另一个节点 0不是 saved 指向的节点 1。saved迭代器依旧有效节点内存没有动输出1 1。erase只会让被删掉的那个迭代器失效别的迭代器完好。这里 erase 的是begin()节点 0不是saved节点 1。while循环删除偶数原链表1,2,3,4,5,6→ 删除偶数后剩下1 3 5。最后打印saved它依旧指向节点 1地址不变输出1 1。六、排序、去重、合并与节点转移6.1 为什么 list 有成员 sort算法标准库中的std::sort要求随机访问迭代器不能用于list。需要对list元素排序时应使用l.sort()默认按升序排列需要降序可写l.sort(std::greaterint())包含functional。std::greaterint()生成一个比较对象判断左边是否大于右边。暂时把它理解成排序规则即可。成员sort是稳定排序比较意义下相等的元素保持原相对顺序比较次数为 O(N log N)。6.2 reverse 保持位置不等于保持遍历顺序l.reverse()反转序列。已有元素迭代器继续关联原元素。std::reverse(l.begin(),l.end())也可用于list因为这个算法只要求双向迭代器但它通过交换元素值工作。因此一个有效迭代器仍指向原来的元素对象读到的值却可能改变。写法做什么迭代器有效性*it 的值l.reverse()调换链表指针节点不动迭代器有效指向原元素*it不变std::reverse(l.begin(),l.end())交换元素的值迭代器有效*it被改写两种写法迭代器都有效但语义不一样。6.3 unique 相邻去重完全去重前提是有序对1 1 2 1 1 3执行unique得到1 2 1 3两段连续的 1 各保留一个分隔开的 1 不会合并。这样可以尽量可能保证原链表中的元素顺序不被打乱。如果需求是不关心原顺序、相同值全局只留一个可以先使用sort再unique把相同值聚到一起之后再去重。6.4 merge 的前提是两个序列按相同规则有序first.merge(second)是把second的节点并入first然后得到有序序列执行完后second变空这不是简单把second接到尾部而是把两个有序链表合并成一个有序链表。合并保持元素迭代器有效被转移的元素现在属于first。默认合并不会把重复值自动去掉。#includealgorithm#includefunctional#includeiostream#includelistvoidprint(conststd::listintl){for(intx:l)std::coutx ;std::coutstd::endl;}intmain(){//初始化liststd::listintl{1,1,2,1,1,3};//未排序去重l.unique();print(l);//排序后去重l.sort();l.unique();print(l);//成员sort默认升序使用仿函数改为降序l.sort(std::greaterint());print(l);autoitl.begin();int*address*it;//反转链表后观察开头元素迭代器地址变化l.reverse();std::cout*it (*itaddress)std::endl;std::reverse(l.begin(),l.end());std::cout*it (*itaddress)std::endl;//初始化两个相同规则的有序链表合并后打印情况std::listintfirst{1,3,5};std::listintsecond{2,4,6};first.merge(second);print(first);std::coutsecond.empty()std::endl;}运行结果使用list::unique()原序列1 1 2 1 1 3只消除相邻的重复输出1 2 1 3。全局去重先sort() 再unique()排序后变成1 1 2 3去重后输出1 2 3使用list::merge()合并两个有序链表1 3 52 4 6-1 2 3 4 5 6。原始 {1,1,2,1,1,3} l.unique(); → 1 2 1 3 l.sort();l.unique() → 1 2 3 l.sort(greaterint()) → 3 2 1 l.reverse() → 1 2 3 std::reverse(...) → 3 2 1 merge之后 first → 1 2 3 4 5 6 second.empty() → 1(true)6.5 splice 转移节点单个节点或是一整段写法转移内容a.splice(pos,b)b的全部元素b变空a.splice(pos,b,it)b中it指向的一个元素a.splice(pos,b,first,last)b的[first,last)范围它们都插到pos前不复制元素也不要求序列是否有序。#includealgorithm#includeiostream#includelistvoidprint(conststd::listintl){for(intx:l)std::coutx ;std::coutstd::endl;}intmain(){//初始化两个有序链表std::listintfirst{1,2,3};std::listintsecond{10,20};//取second开头元素迭代器与其地址automovedsecond.begin();int*address*moved;autoposfirst.begin();pos;//将second合并到first的pos前first.splice(pos,second);print(first);//输出观察此时second是否为空以及迭代器变化std::coutsecond.empty() (*movedaddress)std::endl;//对自身进行合并元素位置调换autoitstd::find(first.begin(),first.end(),3);if(it!first.end()){first.splice(first.begin(),first,it);}print(first);// moved 现已属于 first应该用 first 的范围边界操作它。autonextfirst.erase(moved);print(first);}运行示例first.splice(pos,second)把second全部节点转移到first的pos迭代器前面转移完成后second变成空。节点不拷贝只是改指针原来second上的迭代器moved依旧有效只是现在归属first容器。splice允许源容器与目标容器是同一个list直接把本list内部某个节点剪切挪到别的位置不需要拷贝效率极高。虽然moved原本来自second但节点已经转移到first因此可以传给first.erase(moved)七、list 的相关功能成本list的成本有许多和vector不同的地方实际还需要根据具体场景选择使用。工作list 的成本与条件已知有效位置插入 / 删除一个元素常数复杂度不搬移其余元素仍有构造析构和分配释放的实际成本查找某值再删除它查找 O(N)删除本身 O(1)访问第 k 个元素逐步遍历不能随机访问单节点splice/ 整表splice常数复杂度跨容器区间splice对转移数量线性同容器区间转移可为常数复杂度与vector的有价值区别集中在这里后者连续存储、支持随机访问物理空间连续高速缓存利用率高list提供稳定节点位置和节点转移按需申请和释放空间但每个节点额外保存链接也常需要独立分配。下篇list迭代器与资源管理实现的综合叙述下std::list 标准库参考