一、list

1.1、list的介绍

1. list 是一种序列容器，允许在序列中的任何位置进行插入和删除操作，且插入 / 删除时只需修改节点的指针指向，无需移动其他元素，效率极高；同时支持双向迭代，能正向、反向遍历容器。

2. list 是专门为频繁插入删除设计的序列容器，和 vector 的 “动态数组” 结构不同，list 的底层是带头双向循环链表—— 这一结构直接决定了它的核心特性：任意位置插入删除高效，但不支持随机访问。

3. 核心优势：任意位置插入 / 删除高效、迭代器稳定性强（除被删除节点的迭代器外，其他迭代器不失效）；

4. 核心劣势：不支持随机访问（不能用[]或at()访问元素）、遍历效率低于 vector（需逐个节点跳转）、额外空间开销大（每个节点需存储两个指针）。

5. list (size_type n, const value_type& val = value_type())：构造的list中包含n个值为val的元素

list<int> lst2(5, 3);

6. list()：构造空的list

list<int> lst1; 

7. list (const list& x) ：拷贝构造函数

list<int> lst1; 

8. list (InputIterator first, InputIterator last)：用[first, last)区间中的元素构造list

vector<int> vec = {1,2,3,4};
list<int> lst4(vec.begin(), vec.end());

1.2、list iterator的使用

list 的迭代器是双向迭代器，支持++（向后移动）、- -（向前移动），但不支持+n、-n（随机访问）—— 这是链表结构的必然结果（无法直接跳转到第 n 个元素）。

1. begin()：返回正向迭代器，指向第一个有效元素（哨兵节点的下一个节点）
2. end()：返回正向迭代器，指向最后一个有效元素的下一个位置（即哨兵节点）
3. rbegin()：返回反向迭代器，指向最后一个有效元素（等价于–end()）
4. rend()：返回反向迭代器，指向第一个有效元素的前一个位置（即哨兵节点）
   正向迭代器

list<int> lst = { 1,2,3,4,5 };

list<int>::iterator it = lst.begin();
while(it != lst.end()) {
	*it *= 2; 	
	cout << *it << " ";
	it++;
}
cout << endl;

反向迭代器

list<int> lst = { 1,2,3,4,5 };

list<int>::reverse_iterator rit = lst.rbegin();
while (rit!= lst.rbegin()) {
	cout << *rit << " "; 
}
cout << endl;

不能用[]或at()访问元素：lst[2]、lst.at(2)都是错误的！因为链表没有连续内存，无法直接定位到第 n 个元素；

迭代器失效场景：仅当节点被删除时，指向该节点的迭代器失效，其他迭代器（包括前后节点的迭代器）依然有效

1.3、 list 的容量操作

1. size()：返回当前 list 中有效元素的个数
2. empty()：判断 list 是否为空（元素个数为 0）
3. max_size()：返回 list 理论上能存储的最大元素个数（受系统内存限制，实际意义不大）

list<int> lst = {1,2,3};

cout << "元素个数：" << lst.size() << endl; // 输出：3
cout << "是否为空：" << (lst.empty() ? "是" : "否") << endl; // 输出：否

lst.clear(); // 清空容器
cout << "清空后元素个数：" << lst.size() << endl; // 输出：0
cout << "清空后是否为空：" << (lst.empty() ? "是" : "否") << endl; // 输出：是

1.4 、list 的元素访问

1. front()：返回第一个有效元素的引用
2. back()：返回最后一个有效元素的引用
3. cfront() ：返回第一个有效元素的 const 引用
4. cback()：返回最后一个有效元素的 const 引用

list<int> lst = {10,20,30,40};

// 修改首尾元素
lst.front() += 5; // 第一个元素变为15
lst.back() -= 5;  // 最后一个元素变为35

cout << "第一个元素：" << lst.front() << endl; // 输出：15
cout << "最后一个元素：" << lst.back() << endl; // 输出：35

// 只读访问（const容器只能用cfront/cback）
const list<int> const_lst = {1,2,3};
cout << "const容器第一个元素：" << const_lst.cfront() << endl; // 输出：1

如果容器为空，调用front()/back()会导致未定义行为（程序崩溃或乱码），建议先用电empty()判断

1.5 、list 的修改操作

1. push_back(const T& val)：在容器尾部插入元素 val（时间复杂度 O (1)）
2. push_front(const T& val)：在容器头部插入元素 val（时间复杂度 O (1)）
3. insert(iterator pos, const T& val)：在迭代器 pos 指向的位置之前插入元素 val，返回指向新插入元素的迭代器
4. insert(iterator pos, size_type n, const T& val)：在 pos 前插入 n 个 val
5. insert(iterator pos, InputIterator first, InputIterator last)：在 pos 前插入 [first, last) 区间的元素

list<int> lst = {2,3};

// 1. 尾部插入
lst.push_back(4); // 结果：[2,3,4]

// 2. 头部插入
lst.push_front(1); // 结果：[1,2,3,4]

// 3. 中间插入（在2和3之间插入2.5）
auto it = lst.begin();
++it; // it指向2
it = lst.insert(it, 2.5); // 插入后it指向2.5，结果：[1,2.5,2,3,4]

// 4. 插入n个相同元素（在3前插入2个3）
++it; ++it; ++it; // it指向3
lst.insert(it, 2, 3); // 结果：[1,2.5,2,3,3,3,4]

// 5. 插入其他容器的区间元素
vector<int> vec = {5,6};
lst.insert(lst.end(), vec.begin(), vec.end()); // 结果：[1,2.5,2,3,3,3,4,5,6]

6. pop_back()：删除容器尾部元素
7. pop_front()：删除容器头部元素
8. erase(iterator pos)：删除 pos 指向的元素，返回指向下一个有效元素的迭代器
9. erase(iterator first, iterator last)：删除 [first, last) 区间的元素，返回下一个有效元素的迭代器
10. clear()：删除容器中所有元素

list<int> lst = {1,2,3,4,5,6};

// 1. 删除尾部元素
lst.pop_back(); // 结果：[1,2,3,4,5]

// 2. 删除头部元素
lst.pop_front(); // 结果：[2,3,4,5]

// 3. 删除中间元素（删除3）
auto it = lst.begin();
++it; // it指向3
it = lst.erase(it); // 删除后it指向4（避免迭代器失效）
cout << "删除后当前元素：" << *it << endl; // 输出：4

// 4. 删除区间元素（删除4和5）
lst.erase(it, lst.end()); // 结果：[2]

// 5. 清空容器
lst.clear(); // 结果：空容器

迭代器失效处理
list 的erase(pos)会使指向被删除节点的迭代器失效，但其他迭代器依然有效。因此删除后需用返回值更新迭代器，避免访问失效迭代器：

// 错误写法（迭代器失效）
for (auto it = lst.begin(); it != lst.end(); ++it) {
    if (*it % 2 == 0) {
        lst.erase(it); // it失效，后续++it会出错
    }
}

// 正确写法（用返回值更新迭代器）
for (auto it = lst.begin(); it != lst.end(); ) { // 不在这里++it
    if (*it % 2 == 0) {
        it = lst.erase(it); // 删除后it自动指向 next 元素
    } else {
        ++it; // 不删除则手动移动迭代器
    }
}

11. void swap(list& x)：交换两个 list 的内容（O (1)），仅需交换链表的头指针和大小，无需拷贝元素 —— 效率极高！

list<int> lst1 = {1,2,3};
list<int> lst2 = {4,5,6};

lst1.swap(lst2); // 交换后：lst1=[4,5,6], lst2=[1,2,3]

1.6 、list 的特有操作

合并链表

1. void splice(iterator pos, list& x)：将链表 x 的所有元素 “移动” 到当前链表的 pos 位置前，x 变为空
2. splice(iterator pos, list& x, iterator i)：仅移动 x 中 i 指向的元素到 pos 前；
3. splice(iterator pos, list& x, iterator first, iterator last)：移动 x 中 [first, last) 区间的元素到 pos 前。

list<int> lst1 = {1,2,3};
list<int> lst2 = {4,5,6};

// 1. 移动lst2的所有元素到lst1的末尾
lst1.splice(lst1.end(), lst2); 
// 结果：lst1=[1,2,3,4,5,6], lst2为空

// 2. 重新构造lst2，移动单个元素
list<int> lst3 = {7,8,9};
auto it = lst3.begin();
++it; // 指向8
lst1.splice(lst1.begin(), lst3, it); // 把8移到lst1开头
// 结果：lst1=[8,1,2,3,4,5,6], lst3=[7,9]

// 3. 移动区间元素
lst1.splice(lst1.end(), lst3, lst3.begin(), lst3.end()); // 把lst3的7、9移到lst1末尾
// 结果：lst1=[8,1,2,3,4,5,6,7,9], lst3为空

删除特定元素

1. void remove(const T& val)：删除容器中所有值等于 val的元素
2. template < class Predicate >
   void remove_if(Predicate pred)：删除所有使 pred 返回 true 的元素

list<int> lst = {1,2,2,3,4,2,5};

// 1. 删除所有值为2的元素
lst.remove(2); // 结果：[1,3,4,5]

// 2. 自定义条件：删除所有偶数
lst.remove_if([](int x) { return x % 2 == 0; }); // 结果：[1,3,5]

去重

1. void unique()：删除相邻且相等的重复元素（仅保留第一个），需注意：去重前需先排序，否则不相邻的重复元素无法删除

list<int> lst = {2,1,2,3,1,3,3};

// 错误：未排序，仅删除相邻重复元素（无效果）
lst.unique(); // 结果还是[2,1,2,3,1,3,3]

// 正确：先排序再去重
lst.sort(); // 排序后：[1,1,2,2,3,3,3]
lst.unique(); // 去重后：[1,2,3]

排序

1. void sort()：对 list 中的元素进行升序排序

list<int> lst = {5,3,1,4,2};

// 1. 升序排序
lst.sort(); // 结果：[1,2,3,4,5]

反转

1. void reverse()：反转容器中元素的顺序

list<int> lst = {1,2,3,4,5};
lst.reverse(); // 结果：[5,4,3,2,1]

1.7、list与vector的对比

底层结构 非连续内存，节点 + 指针（list） 连续内存（动态扩容）（vector）
访问效率 O (n)（需遍历）（list） O (1)（随机访问，支持 []/at ()）（vector）
插入删除效率 任意位置 O (1)（仅改指针）（list） 尾部 O (1)，中间 / 头部 O (n)（需移动元素）（vector）
空间利用率 低（每个节点有指针开销）（list） 高（连续内存，仅预留少量空闲空间）（vector）
迭代器类型 双向迭代器（不支持 +/-n）（list） 随机访问迭代器（支持 +/-n、[]）（vector）
迭代器失效 仅删除节点的迭代器失效（list） 插入可能导致全部失效，删除导致后续失效（vector）
动态扩容 无（插入节点直接分配内存，无需扩容）（list） 有（容量不足时重新分配内存 + 拷贝元素）（vector）
特有操作 splice、remove、unique、sort、reverse（list） 无（需用算法库函数，效率低）（vector）

用 vector 的情况：频繁随机访问元素、少量尾部插入 / 删除、追求空间高效；
用 list 的情况：频繁在任意位置插入 / 删除、不需要随机访问、迭代器稳定性要求高；