在C++标准模板库(STL)中,forward_list 是一种单链表容器,提供高效的插入和移除操作。forward_list 是以单向链表的方式存储元素,每个节点包含一个元素和指向下一个节点的指针。由于只有前向指针,所以它只支持从列表的开始进行顺序遍历,不支持随机访问。 forward_list 定义在 <forward_list> 头文件中,它不是像 std::vector 或 std::deque 那样的序列容器,因为它不提供对元素的随机访问能力。
主要特点- 单链表:以单向链表的形式存储元素,每个元素包含对下一个元素的引用。
- 插入和移除操作:在列表头部或任何迭代器指定的位置进行插入和移除操作非常高效。
- 不支持随机访问:不支持通过索引访问元素,也不支持
operator[] 。 - 轻量级:由于只存储单个指针,
forward_list 相比其他容器更节省内存。
主要操作- 构造和赋值:默认构造函数复制构造函数移动构造函数赋值运算符移动赋值运算符
- 大小操作:empty:检查列表是否为空。size:返回列表中元素的数量(注意,这个操作是线性时间的)。
- 添加元素:insert_after:在指定迭代器之后插入一个或多个元素。push_front:在列表头部插入一个元素。
- 移除元素:erase_after:删除指定迭代器之后的元素。pop_front:移除列表头部的元素。
- 遍历:使用迭代器从前到后遍历列表。
使用 std::forward_list 的步骤- 包含头文件:使用 forward_list 之前需要包含 <forward_list> 头文件。
- 声明 forward_list 实例:指定元素类型来声明 std::forward_list 的实例。
- 初始化:可以默认构造一个空的 std::forward_list,或者使用花括号 {} 初始化。
- 执行操作:使用 insert_after、push_front、erase_after 等方法操作单链表。
示例代码#include <iostream>
#include <forward_list>
int main() {
std::forward_list<int> myList; // 创建一个空的单链表
// 在列表头部添加元素
myList.push_front(10);
myList.push_front(20);
myList.push_front(30);
// 从列表尾部添加元素
auto it = myList.before_begin(); // 获取到开始之前的迭代器
while (++it != myList.end()) {
myList.insert_after(it, *it * 2); // 将当前元素乘以2后插入到其后
++it; // 移动迭代器
}
// 遍历单链表
for (int num : myList) {
std::cout << num << ' ';
}
std::cout << std::endl;
return 0;
}
在这个示例中,我们创建了一个 std::forward_list 的实例,并向其中添加了一些整数。然后,我们使用 insert_after 方法在每个元素之后插入了一个新的元素。最后,我们使用迭代器从前到后遍历了单链表中的所有元素。 注意事项std::forward_list 的迭代器是单向迭代器,不支持反向遍历。- 由于不支持随机访问,
std::forward_list 不适用于需要快速随机访问的场景。 std::forward_list 的 size 方法的时间复杂度是 O(n),因为它需要遍历整个列表来计算大小。std::forward_list 适合于插入和移除操作频繁且不需要随机访问的场景。
std::forward_list 是一种特殊类型的容器,适用于对内存使用有严格要求和需要快速插入和移除的场景。
(责任编辑:admin) |