就像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常用成员函数:
函数 | 参数 | 功能描述 |
---|---|---|
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) | first , last : 迭代器范围 | 删除(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仅仅只有正向迭代器,没有back()、size()等成员函数,在进行“增”操作的时候要留意是在位置迭代器后添加元素,同时erase_after(first,last)的删除区间是(first,last),感受这种“after(后)”的思想。
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程