- C++
C++ `forward_list`
- 2025-6-9 22:46:00 @
C++ forward_list
教程
forward_list
是 C++ 标准库中的单链表容器,它支持从容器的任何位置快速插入和删除元素,但只能单向遍历。以下是关于 forward_list
的详细教程:
1. 头文件与基本概念
使用 forward_list
前需要包含头文件:
#include <forward_list>
forward_list
的特点:
- 单向链表,每个节点只指向下一个节点
- 不支持随机访问(无法通过下标直接访问元素)
- 插入和删除操作效率高(O(1) 时间复杂度)
- 相比
list
(双向链表)节省空间,因为每个节点只需维护一个指针
2. 创建与初始化
#include <iostream>
#include <forward_list>
int main() {
// 1. 默认构造函数 - 创建空链表
std::forward_list<int> flist1;
// 2. 初始化列表构造函数
std::forward_list<int> flist2 = {10, 20, 30, 40};
// 3. 指定大小和初始值
std::forward_list<int> flist3(5, 100); // 5个元素,每个都是100
// 4. 从另一个容器复制
std::forward_list<int> flist4(flist2);
// 5. 使用迭代器范围初始化
std::forward_list<int> flist5(++flist2.begin(), flist2.end()); // 从第二个元素到末尾
}
3. 基本操作
插入元素
#include <iostream>
#include <forward_list>
int main() {
std::forward_list<int> flist = {10, 20, 30};
// 在链表前插入元素
flist.push_front(5); // 链表现在是: 5 -> 10 -> 20 -> 30
// 在指定位置后插入元素
auto it = flist.begin(); // 指向5
flist.insert_after(it, 7); // 在5后插入7,链表变为: 5 -> 7 -> 10 -> 20 -> 30
// 插入多个元素
flist.insert_after(++it, {8, 9}); // 在7后插入8和9
// emplace系列函数更高效
flist.emplace_front(3); // 在头部构造元素3
flist.emplace_after(it, 6); // 在迭代器it后构造元素6
}
删除元素
#include <iostream>
#include <forward_list>
int main() {
std::forward_list<int> flist = {3, 5, 7, 8, 9, 10, 20, 30};
// 删除头部元素
flist.pop_front(); // 移除3,链表现在是: 5 -> 7 -> 8 -> 9 -> 10 -> 20 -> 30
// 删除指定位置后的元素
auto it = flist.begin(); // 指向5
flist.erase_after(it); // 删除7,链表变为: 5 -> 8 -> 9 -> 10 -> 20 -> 30
// 删除范围内的元素
auto start = ++flist.begin(); // 指向8
auto end = flist.end();
flist.erase_after(start, end); // 删除从8到末尾的所有元素,链表现在是: 5
// 删除所有值为特定值的元素
flist.remove(5); // 链表现在为空
}
访问元素
#include <iostream>
#include <forward_list>
int main() {
std::forward_list<int> flist = {10, 20, 30, 40};
// 访问第一个元素
std::cout << "第一个元素: " << flist.front() << std::endl; // 输出10
// 遍历链表 - 使用迭代器
for (auto it = flist.begin(); it != flist.end(); ++it) {
std::cout << *it << " "; // 输出: 10 20 30 40
}
// C++11 范围for循环更简洁
for (int num : flist) {
std::cout << num << " ";
}
}
4. 常用方法
方法名 | 描述 |
---|---|
empty() |
判断链表是否为空 |
size() |
不支持(单链表无法高效获取大小,需遍历整个链表) |
max_size() |
返回链表可能容纳的最大元素数 |
front() |
返回第一个元素的引用 |
assign() |
分配新内容替换链表中的元素 |
push_front() |
在链表头部插入元素 |
pop_front() |
删除链表头部元素 |
insert_after() |
在指定位置后插入元素 |
erase_after() |
删除指定位置后的元素 |
remove() |
删除所有值等于给定值的元素 |
remove_if() |
删除满足特定条件的元素 |
reverse() |
反转链表中元素的顺序 |
sort() |
对链表中的元素进行排序(升序) |
merge() |
合并两个已排序的链表 |
unique() |
删除连续重复的元素,只保留一个 |
splice_after() |
将另一个链表的元素插入到当前链表的指定位置后 |
5. 示例:使用 forward_list
实现简单的学生管理系统
#include <iostream>
#include <forward_list>
#include <string>
struct Student {
std::string name;
int age;
double score;
// 构造函数
Student(const std::string& n, int a, double s)
: name(n), age(a), score(s) {}
};
int main() {
std::forward_list<Student> students;
// 添加学生
students.emplace_front("Alice", 20, 95.5);
students.emplace_front("Bob", 21, 88.0);
students.emplace_front("Charlie", 19, 92.3);
// 打印所有学生信息
std::cout << "学生列表:" << std::endl;
for (const auto& student : students) {
std::cout << "姓名: " << student.name
<< ", 年龄: " << student.age
<< ", 分数: " << student.score << std::endl;
}
// 查找并修改学生信息
for (auto& student : students) {
if (student.name == "Bob") {
student.score = 90.0; // 更新Bob的分数
std::cout << "Bob的新分数: " << student.score << std::endl;
break;
}
}
// 删除年龄小于20的学生
students.remove_if([](const Student& s) {
return s.age < 20;
});
std::cout << "更新后的学生列表:" << std::endl;
for (const auto& student : students) {
std::cout << "姓名: " << student.name
<< ", 年龄: " << student.age
<< ", 分数: " << student.score << std::endl;
}
}
6. 注意事项
-
迭代器失效:在插入或删除元素后,指向被修改节点的迭代器会失效。
-
性能考虑:
- 插入/删除操作在已知位置时是 O(1)
- 查找操作是 O(n)
- 不支持随机访问(如
[]
或at()
)
-
适用场景:
- 需要频繁在中间插入/删除元素
- 不需要双向遍历
- 内存使用效率很重要
通过本教程,你应该能够理解 forward_list
的基本概念、操作和适用场景。在实际编程中,根据需求选择合适的容器类型非常重要。
2 条评论
-
admin SU @ 2025-6-9 22:47:48
C++
forward_list
链表🌟 什么是
forward_list
?在 C++ 中,
forward_list
是 单向链表(Singly Linked List)的实现。它属于标准模板库(STL)的一部分,定义在头文件<forward_list>
中。✅ 特点:
- 每个节点只包含一个指向下一个节点的指针。
- 不支持随机访问(不能用下标操作)。
- 插入和删除效率高,适合频繁修改的场景。
- 相比
list
(双向链表),占用内存更少。
📦 包含头文件
#include <iostream> #include <forward_list> // 使用 forward_list 所需头文件 using namespace std;
🧱 基本使用示例
1. 定义并初始化
forward_list
int main() { // 创建一个整型 forward_list 并初始化 forward_list<int> flist = {1, 2, 3, 4}; // 或者创建空链表再添加元素 forward_list<int> emptyList; return 0; }
2. 遍历
forward_list
由于
forward_list
不支持[]
下标访问,我们需要使用迭代器来遍历:cout << "Forward list elements: "; for (auto it = flist.begin(); it != flist.end(); ++it) { cout << *it << " "; // 输出当前节点值 } cout << endl;
或者使用范围 for 循环(C++11 及以上):
for (int val : flist) { cout << val << " "; } cout << endl;
✨ 插入元素
forward_list
提供了多种插入方式,常见的是在头部或某个位置之后插入。在开头插入(push_front)
flist.push_front(0); // 在最前面插入 0
在某个节点后插入(insert_after)
auto it = flist.insert_after(flist.before_begin(), 5); // 在链表最前面插入 5,并返回插入后的迭代器
也可以连续插入:
it = flist.insert_after(it, 6); // 在刚刚插入的 5 后面插入 6 it = flist.insert_after(it, 7);
此时链表为:
5 6 7 0 1 2 3 4
❌ 删除元素
删除开头元素(pop_front)
flist.pop_front(); // 删除第一个元素
删除某个位置后的元素(erase_after)
flist.erase_after(flist.before_begin()); // 删除第一个元素
也可以传入一个迭代器来删除指定位置后面的元素:
auto it = flist.begin(); ++it; // 移动到第二个元素 flist.erase_after(it); // 删除第三个元素
🔍 查找与修改元素
虽然
forward_list
没有直接提供查找函数,但我们可以手动查找:bool found = false; for (auto it = flist.begin(); it != flist.end(); ++it) { if (*it == 3) { cout << "Found value 3" << endl; found = true; break; } } if (!found) { cout << "Value 3 not found" << endl; }
🔄 修改元素值
for (auto it = flist.begin(); it != flist.end(); ++it) { if (*it == 2) { *it = 20; // 将值为 2 的元素改为 20 } }
📐 其他常用操作
判断是否为空
if (flist.empty()) { cout << "List is empty!" << endl; } else { cout << "List is not empty!" << endl; }
获取链表长度(线性时间 O(n))
int size = distance(flist.begin(), flist.end()); cout << "Size of forward_list: " << size << endl;
⚠️ 注意:不像
vector
,forward_list
没有.size()
方法,获取长度是线性复杂度。
📝 综合示例代码
#include <iostream> #include <forward_list> using namespace std; int main() { // 创建 forward_list forward_list<int> flist = {1, 2, 3, 4}; // 插入元素 flist.push_front(0); // 头部插入 flist.insert_after(flist.before_begin(), 5); // 最前面插入 // 遍历输出 cout << "Current list: "; for (int val : flist) { cout << val << " "; } cout << endl; // 查找并修改 for (auto it = flist.begin(); it != flist.end(); ++it) { if (*it == 3) { *it = 30; } } // 删除元素 flist.pop_front(); // 删除头部 flist.erase_after(flist.begin()); // 删除第二个元素 // 再次输出 cout << "After modifications: "; for (int val : flist) { cout << val << " "; } cout << endl; return 0; }
🧠 总结
操作 方法 创建链表 forward_list<int> flist = {1,2,3};
插入头部 flist.push_front(0);
插入任意位置后 flist.insert_after(it, value);
删除头部 flist.pop_front();
删除某位置后 flist.erase_after(it);
遍历 使用 begin()
和end()
迭代器是否为空 flist.empty()
📘 适用场景
- 需要频繁插入/删除中间节点时;
- 对内存要求严格(比
list
轻量); - 不需要随机访问的场合。
如果你想要一个 双向链表,可以使用
std::list
,功能更强大但也更占内存。如需进一步讲解
splice_after
、合并排序等高级操作,也可以继续问我 😄 -
2025-6-9 22:47:17@
C++
forward_list
教程forward_list
是 C++ 标准库中的单链表容器,它支持从容器的任何位置快速插入和删除元素,但只能单向遍历。以下是关于forward_list
的详细教程:1. 头文件与基本概念
使用
forward_list
前需要包含头文件:#include <forward_list>
forward_list
的特点:- 单向链表,每个节点只指向下一个节点
- 不支持随机访问(无法通过下标直接访问元素)
- 插入和删除操作效率高(O(1) 时间复杂度)
- 相比
list
(双向链表)节省空间,因为每个节点只需维护一个指针
2. 创建与初始化
#include <iostream> #include <forward_list> int main() { // 1. 默认构造函数 - 创建空链表 std::forward_list<int> flist1; // 2. 初始化列表构造函数 std::forward_list<int> flist2 = {10, 20, 30, 40}; // 3. 指定大小和初始值 std::forward_list<int> flist3(5, 100); // 5个元素,每个都是100 // 4. 从另一个容器复制 std::forward_list<int> flist4(flist2); // 5. 使用迭代器范围初始化 std::forward_list<int> flist5(++flist2.begin(), flist2.end()); // 从第二个元素到末尾 }
3. 基本操作
插入元素
#include <iostream> #include <forward_list> int main() { std::forward_list<int> flist = {10, 20, 30}; // 在链表前插入元素 flist.push_front(5); // 链表现在是: 5 -> 10 -> 20 -> 30 // 在指定位置后插入元素 auto it = flist.begin(); // 指向5 flist.insert_after(it, 7); // 在5后插入7,链表变为: 5 -> 7 -> 10 -> 20 -> 30 // 插入多个元素 flist.insert_after(++it, {8, 9}); // 在7后插入8和9 // emplace系列函数更高效 flist.emplace_front(3); // 在头部构造元素3 flist.emplace_after(it, 6); // 在迭代器it后构造元素6 }
删除元素
#include <iostream> #include <forward_list> int main() { std::forward_list<int> flist = {3, 5, 7, 8, 9, 10, 20, 30}; // 删除头部元素 flist.pop_front(); // 移除3,链表现在是: 5 -> 7 -> 8 -> 9 -> 10 -> 20 -> 30 // 删除指定位置后的元素 auto it = flist.begin(); // 指向5 flist.erase_after(it); // 删除7,链表变为: 5 -> 8 -> 9 -> 10 -> 20 -> 30 // 删除范围内的元素 auto start = ++flist.begin(); // 指向8 auto end = flist.end(); flist.erase_after(start, end); // 删除从8到末尾的所有元素,链表现在是: 5 // 删除所有值为特定值的元素 flist.remove(5); // 链表现在为空 }
访问元素
#include <iostream> #include <forward_list> int main() { std::forward_list<int> flist = {10, 20, 30, 40}; // 访问第一个元素 std::cout << "第一个元素: " << flist.front() << std::endl; // 输出10 // 遍历链表 - 使用迭代器 for (auto it = flist.begin(); it != flist.end(); ++it) { std::cout << *it << " "; // 输出: 10 20 30 40 } // C++11 范围for循环更简洁 for (int num : flist) { std::cout << num << " "; } }
4. 常用方法
方法名 描述 empty()
判断链表是否为空 size()
不支持(单链表无法高效获取大小,需遍历整个链表) max_size()
返回链表可能容纳的最大元素数 front()
返回第一个元素的引用 assign()
分配新内容替换链表中的元素 push_front()
在链表头部插入元素 pop_front()
删除链表头部元素 insert_after()
在指定位置后插入元素 erase_after()
删除指定位置后的元素 remove()
删除所有值等于给定值的元素 remove_if()
删除满足特定条件的元素 reverse()
反转链表中元素的顺序 sort()
对链表中的元素进行排序(升序) merge()
合并两个已排序的链表 unique()
删除连续重复的元素,只保留一个 splice_after()
将另一个链表的元素插入到当前链表的指定位置后 5. 示例:使用
forward_list
实现简单的学生管理系统#include <iostream> #include <forward_list> #include <string> struct Student { std::string name; int age; double score; // 构造函数 Student(const std::string& n, int a, double s) : name(n), age(a), score(s) {} }; int main() { std::forward_list<Student> students; // 添加学生 students.emplace_front("Alice", 20, 95.5); students.emplace_front("Bob", 21, 88.0); students.emplace_front("Charlie", 19, 92.3); // 打印所有学生信息 std::cout << "学生列表:" << std::endl; for (const auto& student : students) { std::cout << "姓名: " << student.name << ", 年龄: " << student.age << ", 分数: " << student.score << std::endl; } // 查找并修改学生信息 for (auto& student : students) { if (student.name == "Bob") { student.score = 90.0; // 更新Bob的分数 std::cout << "Bob的新分数: " << student.score << std::endl; break; } } // 删除年龄小于20的学生 students.remove_if([](const Student& s) { return s.age < 20; }); std::cout << "更新后的学生列表:" << std::endl; for (const auto& student : students) { std::cout << "姓名: " << student.name << ", 年龄: " << student.age << ", 分数: " << student.score << std::endl; } }
6. 注意事项
-
迭代器失效:在插入或删除元素后,指向被修改节点的迭代器会失效。
-
性能考虑:
- 插入/删除操作在已知位置时是 O(1)
- 查找操作是 O(n)
- 不支持随机访问(如
[]
或at()
)
-
适用场景:
- 需要频繁在中间插入/删除元素
- 不需要双向遍历
- 内存使用效率很重要
通过本教程,你应该能够理解
forward_list
的基本概念、操作和适用场景。在实际编程中,根据需求选择合适的容器类型非常重要。
- 1