C++ 之 【list的简介、list 的构造函数、iterator、容量操作、元素访问、增删查改与迭代器失效】
目录
1.list的介绍
2.list的使用
2.1 构造函数
2.2 iterator 的使用
2.3 容量操作
2.4 元素访问
2.5 增删查改
2.5.1头插头删与尾插尾删
2.5.2 insert 、erase 函数
2.5.3 clear、swap函数
2.5.4 关于find函数
3.迭代器失效
1.list的介绍
(1)list的底层通常实现为带头双向循环链表，支持在任意位置插入、删除
(2)链表中，每个节点包含：一个存储数据的变量和指向前后两个节点的指针
假设节点存储的是int型的数据，则结构如下:
2.list的使用
详细了解请参考文档list - C++ Reference
下面只介绍一些常见接口：
2.1 构造函数
std::list() | 默认构造函数，创建一个空链表。 | std::list<int> l1; |
|
| 创建一个包含 n 个元素的链表，所有元素初始化为 val。 | std::list<int> l3(3, 10); → {10, 10, 10} |
| template<class InputIt>
| 使用迭代器范围 [first, last) 初始化链表（拷贝范围内的元素）。 | std::list<int> l4(v.begin(), v.end());（假设 v 是 {1, 2, 3}） |
std::list(const list& other) | 拷贝构造函数，创建一个与 other 内容相同的链表（深拷贝）。 | std::list<int> l5(l4);（l5 内容与 l4 相同） |
2.2 iterator 的使用
begin() | 返回指向链表第一个元素的迭代器（若链表为空，返回 end()）。 | 正向遍历链表、插入/删除头部元素、作为范围循环的起点。 | ||
end() | 返回指向链表尾后位置的迭代器（不指向任何有效元素，仅用于比较）。 | 标记遍历结束位置、作为范围循环的终点、检查链表是否为空（l.begin() == l.end()）。 | ||
rbegin() | 返回指向链表最后一个元素的反向迭代器（逻辑上为链表的“反向开头”）。 | 反向遍历链表、从末尾开始处理元素。 | ||
rend() | 返回指向链表“反向尾后”位置的迭代器（逻辑上为链表的“反向末尾”）。 | 标记反向遍历结束位置、作为反向范围循环的终点。 |
假设链表被实现为 带头双向循环链表，则迭代器示意如下
总结：
1. begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
2. rbegin与rend为反向迭代器，对迭代器执行++操作，迭代器向前移动
2.3 容量操作
empty() | bool | 检查链表是否为空（无元素） | if (l.empty()) { std::cout << "链表为空！"; } | ||
size() | size_type | 返回链表中元素的数量（类型为 std::size_t） | std::cout << "链表大小: " << l.size(); |
2.4 元素访问
front() | 返回链表第一个元素的引用 （可修改或读取）。 |
或 | ||||
back() | 返回链表最后一个元素的引用 （可修改或读取）。 |
或 |
2.5 增删查改
2.5.1头插头删与尾插尾删
void push_front(const T& value); | 在链表头部插入元素 | lt.push_front(1); | ||||||
void pop_front(); | 删除链表头部元素。 | lt.pop_front(); | ||||||
void push_back(const T& value); | 在链表尾部插入元素 | lt.push_back(1); | ||||||
void pop_back(); | 删除链表尾部元素。 | lt.pop_back(); |
pop_front使begin()迭代器失效，pop_back使end()迭代器失效
其余的不失效
2.5.2 insert 、erase 函数
insert | 在指定位置 pos 前插入元素（支持单元素、重复元素、范围插入） | 返回指向新插入元素的迭代器（对单元素插入） | 原有迭代器不失效 | |||||
erase | 删除指定位置或范围的元素（支持单元素删除、范围删除） | 返回指向被删除元素后一个位置的迭代器。 | 使被删除元素的迭代器失效 |
void test1(){std::list<int> lst = {1, 2, 3, 4, 5};// 1. 单元素插入（在第二个位置插入 99）auto it = lst.begin();// 手动移动迭代器到第二个位置++it;auto insert_it = lst.insert(it, 99); // 在 it 前插入 99std::cout << "After single insert: ";for (int x : lst) {std::cout << x << " "; // 输出: 1 99 2 3 4 5}std::cout << "\nInserted element: " << *insert_it << std::endl; // 输出: 99// 2. 范围插入（在第三个位置插入数组 {5, 6, 7}）int arr[3] = {5, 6, 7};auto range_it = lst.begin();// 手动移动迭代器到第三个位置for(int i = 0; i < 3; ++i){++range_it;}lst.insert(range_it, arr, arr + 3); // 插入数组std::cout << "After range insert: ";for (int x : lst) {std::cout << x << " "; // 输出: 1 99 2 5 6 7 3 4 5}// 3. 填充插入（在末尾插入 3 个 0）lst.insert(lst.end(), 3, 0); // 末尾插入 3 个 0std::cout << "\nAfter fill insert: ";for (int x : lst) {std::cout << x << " ";// 输出: 1 99 2 5 6 7 3 4 5 0 0 0}// 1. 单元素删除（删除值为 99 的元素）auto delete_it = std::find(lst.begin(), lst.end(), 99); // 查找元素if (delete_it != lst.end()) {auto next_it = lst.erase(delete_it); // 删除并返回下一个元素的迭代器std::cout << "After single erase: ";for (int x : lst) {std::cout << x << " "; // 输出: 1 2 5 6 7 3 4 5 0 0 0}std::cout << "\nNext element after erase: " << *next_it << std::endl; // 输出: 2}// 2. 范围删除（删除从第二个到第四个元素）auto start_it = lst.begin();// 手动移动迭代器到第二个位置for (int i = 0; i < 1 && start_it != lst.end(); ++i, ++start_it);auto end_it = lst.begin();// 手动移动迭代器到第五个位置for (int i = 0; i < 4 && end_it != lst.end(); ++i, ++end_it);lst.erase(start_it, end_it); // 删除 [start_it, end_it) 范围内的元素std::cout << "After range erase: ";for (int x : lst) std::cout << x << " "; // 输出: 1 3 4 5 0 0 0// 3. 边界条件：删除 end() 会导致未定义行为// lst.erase(lst.end()); // 错误：不能删除 end()
}2.5.3 clear、swap函数
void swap(list& other); | 交换当前链表与 other 链表的所有元素（包括大小、节点和迭代器有效性） | other：待交换的另一个 std::list 对象 | 交换后，原链表的迭代器指向 other 的元素，反之亦然； | |||||
void clear(); | 删除链表中的所有元素，释放所有节点内存 | 所有迭代器/引用失效 （链表变为空） |
虽然使用swap函数后,原链表的迭代器指向
other的元素，反之亦然，但是开发者不要依赖交换后的迭代器/引用（除非明确知道它们指向另一个链表）
以避免潜在的逻辑错误和未定义行为
2.5.4 关于find函数
std::list 无find成员函数，调用标准库中的find函数即可
3.迭代器失效
| 操作 | 失效的 迭代器/指针/引用类型 | 失效原因 | 避免失效的方法 | |
|---|---|---|---|---|
insert | 不失效（插入位置及之前的迭代器、指针、引用 均有效) | std::list 是双向链表，插入操作仅修改相邻节点的指针，不移动现有节点,所以不失效 | 无需特殊处理，直接使用插入后的迭代器继续操作。 | |
erase | 仅失效被删除节点的迭代器、指针、引用 | erase 会释放被删除节点的内存，导致指向该节点的迭代器/指针/引用失效。 | 删除前保存下一个节点的迭代器（如 （ | |
clear | 所有迭代器、指针、引用均失效 | clear 会释放链表中所有节点的内存，导致所有迭代器/指针/引用失效。 | 清空后通过 begin()/end() 重新获取迭代器，避免使用旧迭代器。 | |
swap | 所有迭代器、指针、引用失效（除非交换同一链表） | 交换后，原链表的迭代器指向 other 的元素，反之亦然。逻辑上所有迭代器失效（内容所属链表已改变）。 | 交换后通过 begin()/end() 重新获取迭代器，避免依赖交换后的迭代器。 |