就像array是vector的“轻量型”一样,list也有自己的“轻量型”——forward_list。什么是forward_list,简单来说,forward_list就是单链表,每个节点只包含一个后驱指针,如果读者忘记单链表的相关知识,可跳转《链表》补充相关知识。在C++11后,为了追求轻便高效的容器,STL大师将list“优化”为forward_list,forward_list仅支持头增头删,读者可联想vector的尾增尾删,它两是反过来的。此外,forward_list迭代器有且仅有前向迭代器(没有rbegin()、rend()),只能进行向前++操作,无法进行+4或--操作。在forward_list里,没有back()、size()函数,插入和删除只能通过erase_after()、insert_after(),具体指的是在参数位置迭代器后插入一个元素,不同于erase()、insert()这些概念了。

forward_list的结构长这样:

forward_list

下表展示了forward_list常用成员函数:

函数参数功能描述
empty()无参数检查链表是否为空
front()返回第一个元素的引用
begin()返回指向第一个元素的迭代器
end()返回尾后迭代器
clear()删除所有元素
insert_after(pos, const T& value)pos: 位置迭代器, value: 要插入的值在pos后插入一个元素
insert_after(pos, size_type n, const T& value)pos: 位置, n: 数量, value: 元素值在pos后插入n个相同元素
insert_after(pos, InputIt first, InputIt last)pos: 位置, first,last: 迭代器范围在pos后插入范围内的元素
emplace_after(pos, Args&&... args)pos: 位置, args: 构造参数在pos后直接构造元素
erase_after(pos)pos: 位置迭代器删除pos后面的元素
erase_after(first, last)firstlast: 迭代器范围删除(first,last)范围内的元素
push_front(const T& value)value: 要插入的值在链表开头插入元素
emplace_front(Args&&... args)args: 构造参数在链表开头直接构造元素
pop_front()无参数删除链表第一个元素
remove(const T& value)value: 要删除的值删除所有值等于value的元素
remove_if(Predicate p)p: 一元谓词函数删除所有满足条件的元素
reverse()无参数
反转链表的元素顺序
unique()删除连续重复的元素
sort()对元素进行升序排序
merge(forward_list& other)other: 要合并的链表合并两个已排序的链表
splice_after(pos, forward_list& other)pos: 位置, other: 源链表将other的所有元素移到pos后
splice_after(pos, forward_list& other, it)pos: 位置, other: 源链表, it: 源位置将other中it后的元素移到pos后
swap(forward_list& other)other: 另一个链表交换两个链表的内容

对于forward_list的学习,我们可以对比list来进行归纳总结,这里就不赘述了。

下面展示如何操作forward_list进行简单的增删查改操作:

#include<bits/stdc++.h>
#include<forward_list>
/*操作forward_list进行简单的增删查改 */
using namespace std;
void test()
{
forward_list<int> fl;//直接创建
for(int i=0;i<5;++i)
{
fl.push_front(i+1);//链表只有push_front()头增元素 
}
cout << "遍历forward_list:";
for(forward_list<int>::iterator it = fl.begin();it!=fl.end();++it)cout << *it << " ";//仅仅有前向迭代器 
cout << '\n';
/*在第二个元素前面插入9*/
fl.emplace_after(++fl.begin(),9) ;
cout << "在第二个元素后面插入9后遍历forward_list: ";
for(forward_list<int>::iterator it = fl.begin();it!=fl.end();++it)cout << *it << " ";//仅仅有前向迭代器 
cout << '\n';
/*{5,4,9,3,2,1}删除区间(1,4)内所有元素*/
auto pos3=++fl.begin() ;
auto pos5=fl.begin();
for(int i=0;i<4;++i)++pos5;
fl.erase_after(pos3,pos5) ;
cout << "{5,4,9,3,2,1}删除区间(1,4)内所有元素";
for(forward_list<int>::iterator it = fl.begin();it!=fl.end();++it)cout << *it << " ";//仅仅有前向迭代器 
cout << '\n';
}
  
int main(){
    test();
    return 0;
}

编译结果为:

实现forward_list基本操作

对于forward_list的学习,读者一定要归纳总结,比如forward_list仅仅只有正向迭代器,没有back()、size()等成员函数,在进行“增”操作的时候要留意是在位置迭代器后添加元素,同时erase_after(first,last)的删除区间是(first,last),感受这种“after(后)”的思想。

点赞(0)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

Dotcpp在线编译      (登录可减少运行等待时间)