List容器

简介

List是双向链表的序列容器，list 通过节点链接存储元素，每个节点独立分配内存，内存不连续。
目的:高效的插入和删除操作，避免频繁的内存重新分配和元素复制开销。
由于每个元素独立分配内存，list 不支持随机访问，只能通过迭代器顺序访问元素。
list 不支持像 vector 那样的预分配内存和容量管理函数，因为其内存分配是按需进行的。

1、非连续存储2、只能通过迭代器访问元素，3、不支持指向元素的常规指针进行偏移访问。

list的迭代器失效

list(双向链表)和forward_list(单向链表)采用节点链表存储，每个元素独立分配，内存不连续：
插入操作​​：
​​不会​​使任何已有迭代器失效。
​​删除操作​​：
仅​​指向被删除元素本身的迭代器​​会失效。
其他元素的迭代器不受影响。

使用例程:

#include<iostream>#include<list>#include<string>#include<algorithm>usingnamespacestd;voidcout_List(constlist<int>&lst){if(!lst.empty()){for(constint&n:lst)std::cout<<n<<' ';std::cout<<std::endl;}else{std::cout<<"空链表"<<std::endl;}}intmain(){list<int>L1={10,20,30,40};//输出list元素std::cout<<"L1元素: ";cout_List(L1);cout<<"访问首元素: "<<L1.front()<<",访问尾元素: "<<L1.back()<<endl;//在尾部插入元素L1.emplace_back(50);//在头部插入元素L1.emplace_front(5);std::cout<<"头插入5,尾插入50,L1元素: ";cout_List(L1);//叠代器位置插入autoit=L1.begin();advance(it,2);//移动到索引2位置L1.insert(it,15);//在索引2位置插入15std::cout<<"叠代器位置插入15 L1元素: ";cout_List(L1);//叠代器位置删除元素it=L1.begin();advance(it,3);//移动到索引3位置L1.erase(it);std::cout<<"叠代器3位置删除元素后 L1元素: ";cout_List(L1);//拼接链表list<int>L2={100,200,300};L1.splice(L1.end(),L2);//将L2拼接到L1末尾std::cout<<"拼接L2后 L1元素: ";cout_List(L1);//在15后面插入25it=std::find(L1.begin(),L1.end(),15);it++;L1.insert(it,25);std::cout<<"在15后面插入25后 L1元素: ";cout_List(L1);//删除25后面的元素it=std::find(L1.begin(),L1.end(),25);it++;L1.erase(it);std::cout<<"删除25后面的元素后 L1元素: ";cout_List(L1);//按谓词删除元素L1.remove_if([](intn){returnn%2==0;});//删除所有偶数元素std::cout<<"删除所有偶数元素后 L1元素: ";cout_List(L1);std::cout<<"*****************************************"<<std::endl;return0;}

底层原理:

List底层设计目的是任务位置高效增删和迭代器稳定。

一、核心数据结构体:双向循环链表+哨兵节点

list 的底层是双向循环链表，且通过「哨兵节点（Sentinel Node）」优化边界处理，这是其所有特性的基础。

1、节点结构

每个元素对应一个节点，每个节点包含数据域和两个指针域(前继和后继)，用于连接前后节点。

template<typenameT>structListNode{T data;// 数据域：存储元素值ListNode*prev;// 前驱指针：指向前一个节点ListNode*next;// 后继指针：指向后一个节点// 1. 普通构造（拷贝数据）ListNode(constT&val):data(val),prev(nullptr),next(nullptr){}// 2. C++11 移动构造（转移数据，减少拷贝）ListNode(T&&val):data(std::move(val)),prev(nullptr),next(nullptr){}};

指针域 prev 和 next 是双向链表的核心：支持向前 / 向后遍历，任意位置增删时仅需修改指针，无需移动元素。
移动构造：C++11 新增，用于转移右值数据（如临时对象），提升性能。

2、哨兵节点

list不直接存储元素节点的首尾，而是通过一个哨兵节点串联所有元素节点，形成循环结构。
①哨兵节点不存储有效数据，仅用于简化边界判断（如空容器、首尾操作）。
②循环结构：哨兵节点的 prev 指向最后一个元素节点，next 指向第一个元素节点；最后一个元素节点的 next 指向哨兵，第一个元素节点的 prev 指向哨兵。

二、核心操作的底层实现逻辑

list 的所有操作（增删查改）本质都是「指针修改」，无需移动元素，这是其「任意位置增删 O (1)」的核心原因。

1、插入操作

找到插入位置的前驱节点 pos，创建新节点，修改 pos、新节点、pos->next 的指针关系，最终 _size++。
①插入位置可以是任意迭代器指向的节点（前插）。
②emplace 与 insert 的区别：emplace 直接在插入位置构造节点（避免临时对象拷贝），insert 插入已构造的元素（可能拷贝 / 移动）。

// 在迭代器 pos 指向的节点前插入元素 valiteratorinsert(iterator pos,constT&val){ListNode<T>*curr_node=pos._node;// 迭代器封装的节点指针ListNode<T>*new_node=new ListNode<T>(val);// 创建新节点// 1. 新节点的前驱 = curr_node 的前驱new_node->prev=curr_node->prev;// 2. 新节点的后继 = curr_nodenew_node->next=curr_node;// 3. curr_node 前驱的后继 = 新节点curr_node->prev->next=new_node;// 4. curr_node 的前驱 = 新节点curr_node->prev=new_node;_size++;returniterator(new_node);// 返回指向新节点的迭代器}// C++11 emplace：直接构造节点（完美转发参数）template<typename...Args>iteratoremplace(iterator pos,Args&&...args){ListNode<T>*curr_node=pos._node;// 直接在内存中构造节点，避免临时对象ListNode<T>*new_node=new ListNode<T>(std::forward<Args>(args)...);// 指针修改逻辑与 insert 一致new_node->prev=curr_node->prev;new_node->next=curr_node;curr_node->prev->next=new_node;curr_node->prev=new_node;_size++;returniterator(new_node);}

2、删除操作（erase/clear/remove）

找到待删除节点 del_node，修改其前驱节点 prev_node 和后继节点 next_node 的指针（跳过 del_node），释放 del_node 的内存，最终 _size–。
①仅待删除节点的迭代器失效，其他迭代器仍有效（迭代器稳定的核心）。

// 删除迭代器 pos 指向的节点，返回下一个节点的迭代器iteratorerase(iterator pos){ListNode<T>*del_node=pos._node;ListNode<T>*prev_node=del_node->prev;ListNode<T>*next_node=del_node->next;// 1. 前驱节点的后继 = 后继节点prev_node->next=next_node;// 2. 后继节点的前驱 = 前驱节点next_node->prev=prev_node;deletedel_node;// 释放被删节点内存_size--;returniterator(next_node);// 返回下一个节点的迭代器}// 清空所有元素（保留哨兵节点）voidclear(){ListNode<T>*curr=_head->next;// 从第一个元素节点开始while(curr!=_head){// 循环到哨兵节点结束ListNode<T>*next=curr->next;deletecurr;curr=next;}// 重置哨兵节点的指针（恢复空容器状态）_head->prev=_head;_head->next=_head;_size=0;}