C++中的forward_list容器详解

C++中的forward_list容器详解

1.forward_list概述

forward_list是C++11引入的单向链表容器，相比list更加节省空间，但只支持单向遍历。它是最简单的链表结构，每个元素只包含指向下一个元素的指针。

2. 基本特性

• 单向链表：每个元素只包含指向下一个元素的指针
• 高效插入/删除：在已知位置插入/删除是O(1)O(1)O(1)时间复杂度
• 无随机访问：不支持下标操作和反向遍历
• 最小内存开销：相比list节省一个指针的空间
• 无size()操作：为节省空间不维护大小信息

3. 头文件与声明

#include<forward_list>usingnamespacestd;forward_list<int>flst1;// 空forward_listforward_list<string>flst2(10);// 包含10个默认构造的stringforward_list<double>flst3(5,3.14);// 包含5个3.14forward_list<char>flst4={'a','b','c'};// 初始化列表

4. 构造函数与初始化

4.1 默认构造

forward_list<int>flst;

4.2 填充构造

forward_list<int>flst(10);// 10个默认初始化的int(0)forward_list<int>flst(5,100);// 5个100

4.3 范围构造

intarr[]={1,2,3};forward_list<int>flst(arr,arr+3);

4.4 拷贝构造

forward_list<int>flst2(flst1);

5. 容量操作

5.1empty()

if(flst.empty()){cout<<"Forward_list is empty";}

5.2max_size()

cout<<flst.max_size();// 返回forward_list可容纳的最大元素数

6. 元素访问

6.1front()

flst.front()=5;// 修改第一个元素intfirst=flst.front();// 访问第一个元素

7. 修改操作

7.1push_front()

flst.push_front(5);// 在头部插入5

7.2pop_front()

flst.pop_front();// 删除头部元素

7.3insert_after()

autoit=flst.insert_after(flst.before_begin(),15);// 在头部插入15flst.insert_after(it,{1,2,3});// 在指定位置后插入多个元素

7.4erase_after()

flst.erase_after(flst.before_begin());// 删除第一个元素flst.erase_after(it,flst.end());// 删除从it到end的所有元素

7.5clear()

flst.clear();// 清空所有元素

7.6swap()

forward_list<int>flst2;flst.swap(flst2);// 交换两个forward_list的内容

8. 特殊操作

8.1splice_after()

forward_list<int>flst2={4,5,6};flst.splice_after(flst.before_begin(),flst2);// 将flst2所有元素移动到flst头部

8.2remove()

flst.remove(5);// 删除所有值为5的元素

8.3remove_if()

flst.remove_if([](intn){returnn%2==0;});// 删除所有偶数

8.4unique()

flst.unique();// 删除连续重复元素

8.5merge()

forward_list<int>flst2={4,5,6};flst.sort();flst2.sort();flst.merge(flst2);// 合并两个已排序forward_list

8.6sort()

flst.sort();// 升序排序flst.sort(greater<int>());// 降序排序

8.7reverse()

flst.reverse();// 反转forward_list

9. 迭代器

9.1before_begin()

autoit=flst.before_begin();// 获取第一个元素前的位置

9.2begin()&end()

for(autoit=flst.begin();it!=flst.end();++it){cout<<*it<<" ";}

10. 完整示例

#include<iostream>#include<forward_list>#include<algorithm>usingnamespacestd;intmain(){// 创建并初始化forward_listforward_list<int>flst={2,3,4};// 头部操作flst.push_front(1);// 头部插入1// 访问元素cout<<"First element: "<<flst.front()<<endl;// 插入元素autoit=flst.insert_after(flst.begin(),5);// 在第二个位置插入5flst.insert_after(it,{7,8,9});// 在5后面插入7,8,9// 删除元素flst.pop_front();// 删除头部元素flst.remove(8);// 删除所有8// 特殊操作forward_list<int>flst2={10,11,12};flst.splice_after(flst.before_begin(),flst2);// 合并flst2到flstflst.sort();// 排序flst.unique();// 去重// 遍历forward_listcout<<"All elements: ";for(intnum:flst){cout<<num<<" ";}cout<<endl;// 容量信息cout<<"Is empty: "<<(flst.empty()?"Yes":"No")<<endl;return0;}

11. 性能提示

1. 在已知位置插入/删除元素性能很好(O(1)O(1)O(1))
2. 查找元素需要遍历(O(n)O(n)O(n))
3. 迭代器在插入/删除操作后仍然有效(除非删除的是迭代器指向的元素)
4. 比list更节省内存(每个节点少一个指针)
5. 适合只需要单向遍历且对内存敏感的场合