1. std::list
基本概念
- 定义:
std::list
是 C++ 标准库提供的带头(哨兵位)双向循环链表容器,支持高效的元素插入和删除。 - 头文件:
#include <list>
2. 构造函数
(1) 默认构造函数
list<int> list1; // 创建一个空list,size=0
(2) 指定初始大小和默认值
list<int> list2(5); // 5个元素,默认初始化(int为0)
list<double> list3(5, 3.14); // 5个元素,每个值为3.14
(3) 通过迭代器范围构造
int arr[] = {1, 2, 3};
list<int> list4(arr, arr + 3); // 复制数组的[arr, arr+3)范围元素
(4) 拷贝构造函数
list<int> list5(list4); // 深拷贝list4的内容
3. 修改元素的成员函数
(1) push_back()
和 push_front()
在末尾或头部添加元素:
list<int> lst;
lst.push_back(10); // 末尾添加10 → {10}
lst.push_front(5); // 头部添加5 → {5, 10}
(2) insert()
插入元素到指定位置,支持以下重载:
- 插入单个值:
list<int> lst = {1, 3}; list<int>::iterator it = lst.begin(); ++it; lst.insert(it, 2); // 在位置1插入2 → {1, 2, 3}
- 插入多个相同值:
lst.insert(lst.end(), 2, 4); // 在末尾插入2个4 → {1, 2, 3, 4, 4}
- 通过迭代器范围插入:
int arr[] = {5, 6}; lst.insert(lst.end(), arr, arr + 2); // 插入数组内容 → {1, 2, 3, 4, 4, 5, 6}
(3) erase()
删除指定位置或范围的元素:
- 删除单个元素:
list<int>::iterator it = lst.begin(); ++it; lst.erase(it); // 删除位置1的元素 → {1, 3, 4, 4, 5, 6}
- 删除范围元素:
list<int>::iterator first = lst.begin(); advance(first, 3); // 移动到位置3 lst.erase(first, lst.end()); // 删除位置3到末尾 → {1, 3, 4}
(4) clear()
清空所有元素:
lst.clear(); // size=0
(5) assign()
重新分配元素(覆盖原有内容):
- 指定数量和值:
lst.assign(3, 10); // 3个10 → {10, 10, 10}
- 通过迭代器范围:
int arr[] = {20, 30, 40}; lst.assign(arr, arr + 2); // 复制前2个元素 → {20, 30}
4. 访问元素的成员函数
(1) front()
和 back()
访问首尾元素:
int first = lst.front(); // 第一个元素
int last = lst.back(); // 最后一个元素
5. 容量管理的成员函数
(1) size()
获取元素数量:
size_t s = lst.size(); // 当前元素数量
(2) resize()
调整元素数量:
lst.resize(5); // 调整size=5,多出的元素默认初始化(int为0)
lst.resize(3, 100); // 调整size=3,若需要新增元素则初始化为100
6. 链表特有操作
(1) splice()
将另一个链表的元素移动(拼接)到当前链表,支持以下重载:
- 移动整个链表:
list<int> lst1 = {1, 2}; list<int> lst2 = {3, 4}; lst1.splice(lst1.end(), lst2); // lst1 → {1, 2, 3, 4}, lst2变为空
- 移动单个元素:
list<int> lst3 = {5, 6}; list<int>::iterator it = lst3.begin(); lst1.splice(lst1.begin(), lst3, it); // lst1 → {5, 1, 2, 3, 4}, lst3 → {6}
- 移动范围元素:
list<int> lst4 = {7, 8, 9}; list<int>::iterator first = lst4.begin(); list<int>::iterator last = lst4.end(); --last; lst1.splice(lst1.end(), lst4, first, last); // lst1 → {5, 1, 2, 3, 4, 7, 8}, lst4 → {9}
(2) remove()
删除特定元素:
-
remove()
:list<int> lst = {1, 2, 3, 2, 4}; lst.remove(2); // 删除所有值为2的元素 → {1, 3, 4}
(3) sort()
和 merge()
排序和合并链表:
-
sort()
:list<int> lst = {3, 1, 4, 2}; lst.sort(); // 默认升序 → {1, 2, 3, 4}
-
merge()
(要求两个链表已排序):list<int> lst1 = {1, 3}; list<int> lst2 = {2, 4}; lst1.merge(lst2); // lst1 → {1, 2, 3, 4}, lst2变为空
(4) unique()
删除连续重复元素(需先排序):
list<int> lst = {1, 1, 2, 3, 3};
lst.unique(); // 删除连续重复 → {1, 2, 3}
(5) reverse()
反转链表元素顺序:
list<int> lst = {1, 2, 3};
lst.reverse(); // → {3, 2, 1}
7. 迭代器操作
-
begin()
和end()
:for (list<int>::iterator it = lst.begin(); it != lst.end(); ++it) { cout << *it << " "; }
-
rbegin()
和rend()
(反向迭代器):for (list<int>::reverse_iterator rit = lst.rbegin(); rit != lst.rend(); ++rit) { cout << *rit << " "; }
8. 注意事项
- 迭代器失效:删除操作仅使被删除元素的迭代器失效,其他迭代器仍然有效(后面我会专门整理这个问题)。
- 性能特点:插入和删除操作高效,但随机访问效率低(需遍历链表)。
- 排序与合并:
sort()
和merge()
是成员函数,不同于<algorithm>
中的全局函数。