该容器从c11才有,内部是一个单向链表。

需要头文件<forward_list>

在std中定义如下:

template <class Type,

    class Allocator = allocator<Type>>

class forward_list

forward_list是一个受限制的list,优点是内存用量较少,行动也比较快。比起list有一些约束:

不提供双向迭代器,不支持反向迭代器。

不提供成员函数size()

没有指向最后一个元素的anchor,所以没有back() push_back() pop_back()

对于所有插入操作的函数都有特殊版本。例如insert()变为insert_back(),必须传递第一个被处理元素的前一个位置,将新元素插入到第一个实参所表示的元素后。同样,begin()会变成before_begin(),会返回头指针(指向头结点的指针,即单链表的anchor)

不提供size()函数的原因是设计者要求forward_list()与手写的单向链表相比不造成额外的时间或者空间开销。

其余事项与list基本相同。

如果必须计算元素个数,可以使用distance,定义于头文件 <iterator>,返回从 first 到 last 的路程。

forward_list<int> list = { 1, 2, 3 };

cout << distance(list.begin(),list.end());

输出结果是3

元素访问

唯一能够直接访问的元素是第一个元素

c.front(),不检查是否存在第一个元素

迭代器相关

只能以前行方向遍历元素,没有反向迭代器,无法调用双向或者随机迭代器的算法。排序只能用自己的成员函数。

注意,before_begin()和cbefore_begin()作为第一个参数使用任何STL函数都会导致运行时出错。

所有以after结尾的插入函数,会将元素插入到指定位置之后,因为forwardlist没有指向前一个元素的指针。如果后缀after的元素传入了end()作为参数,会产生不明确的行为,如果要在尾部插入一个元素,需要传入终端元素的位置。

和list一样forwardlist可以在常量时间内删除和插入元素。forwardlist提供和list几乎一致的成员函数splice_after()

异常处理

对于和list相同的函数,异常处理方式完全相同。

成员函数

创建、复制、删除

操作 结果
forward_list<Elem> c 默认构造
forward_list<Elem> c(c2) 复制构造
forward_list<Elem> c = c2 复制构造
forward_list<Elem> c(rvalue) move构造
forward_list<Elem> c=crvalue move构造
forward_list<Elem> c(n) 默认构造一个大小为n的forward_list
forward_list<Elem> c(n,elem) 生成一个有n个元素的forward_list,每个元素都是elem
forward_list<Elem> c(begin,end) 以begin和end的左闭右开区间构造一个forward_list
forward_list<Elem> c(initforward_list) 以初值列表构造forward_list
forward_list<Elem> c = initforward_list 同上
c.~forward_list() 销毁所有元素,释放内存

非变动性操作

操作 效果
c.empty() 返回容器是否为空
c.size() 返回目前容器内元素个数
c.max_size() 返回元素个数的最大可能值
c1 == c2  
!=  
<  
>  
<=  
>=  

赋值操作

操作 效果
c = c2 赋值
c = rv 将右值move给c
c = initlist 初始化表赋给c
c.assign(n,elem) n个elem赋给c
c.assign(begin,end) 左闭右开赋给c
c.assign(initlist) 初始化表赋给c
c1.swap(c2) 交换c1,c2
swap(c1,c2) 比上面那个慢,全局函数

迭代器操作

操作 效果
c.begin() 返回一个双向迭代器指向第一个元素
c.end() 返回指向最后一个元素的双向迭代器
c.cbegin() 第一个的const,c11
c.cend() 第二的const,c11
c.before_begin() 返回一个forward迭代器指向第一个元素的前一个位置
c.cbefore_begin() 返回一个const forward迭代器指向第一元素的前一位置

插入删除

操作 效果 异常处理
c.push_front() 头插 成功或者没有任何效果
c.pop_front() 头删,不返回 不抛出异常
c.insert_after(pos,elem) 指定位置后插入 成功或者没有任何效果
c.insert_after(pos,n,elem) 指定位置后插入n个elem,返回第一个新元素的位置 成功或者没有任何效果
c.insert_after(pos,begin,end) 指定位置后插入左闭右开的所有元素,返回第一个新元素位置 成功或者没有任何效果
c.insert_after(pos,initlist) 指定位置后插入初始化列的所有元素并返回第一个新元素的位置 成功或者没有任何效果
c.emplace_after(pos,args…) 在pos后插入以args为初值的元素,并返回新元素位置,c11  
c.emplace_front(args…) 上面的函数的头插实现,不返回,c11  
c.erase_after(pos) 删除指定位之后的元素,不返回任何 不抛出异常
c.erase_after(begin,end) 删除区间,不返回任何 不抛出异常
c.remove(val) 删除所有值为val的元素 元素比较不抛出异常,这个函数就不抛出异常
c.remove_if(op) 上文讲过了 如上
c.resize(num) 元素数量改为num,如果变多,多出来的默认构造 成功或者没有任何效果
c.resize(num,elem) 如果变多,多出来的为elem 成功或者没有任何效果
c.clear() 删除所有元素 不抛出异常

特殊变动性操作

操作 效果 异常处理
c.unique() 如果存在临近且数值相同的元素,只保留一个 元素比较不抛出异常,这个函数就不抛出异常
c.unique(op) 如果存在相邻元素满足op,就只保留一个 元素比较不抛出异常,这个函数就不抛出异常
c.splice_after(pos,c2) 把c2的所有元素搬到c的pos后 不抛出异常
c.splice_after(pos,c2,c2pos) 把c2的c2pos的元素搬到c的pos后 同上
c.splice_after(pos,c2,c2begin,c2end) 把c2的c2begin和c2end之间的元素左闭右开搬到c的pos后 同上
c.sort() 从小到大对c进行排序  
c.sort(op) 以op准则进行排序  
c.merge(c2) 假设c和c2的容器都包含符合op()的已经排序的元素,将c2的元素搬到c,并保证合并后的list依然是已排序的 元素比较不抛出异常,这个函数就不抛出异常
c.merge(c2,op) 假设c和c2的容器都包含符合op()的已经排序的元素,将c2的元素搬到c,并保证合并后的list依然是符合op的已排序的 元素比较不抛出异常,这个函数就不抛出异常
c.reserve() 将所有元素反序 不抛出

实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <string>
#include <forward_list>
#include <algorithm>
#include <iterator>
 
using namespace std;
 
void printLists(const string& s, const forward_list<int>& l1, const forward_list<int>& l2)
{
	cout << s << endl;
	cout << "list1:";
	copy(l1.cbegin(), l1.cend(), ostream_iterator<int>(cout, " "));
	cout << endl;
	cout << "list2:";
	copy(l2.cbegin(), l2.cend(), ostream_iterator<int>(cout, " "));
	cout << endl;
 
}
 
int main()
{
	//创建两个空forwardlist
	forward_list<int> list1 = { 1,2,3,4 };
	forward_list<int> list2 = { 77,88,99 };
	printLists("初始化:", list1, list2);
 
	//在list2的第一个元素前插入6个新元素
	list2.insert_after(list2.before_begin(), 99);
	list2.push_front(10);
	list2.insert_after(list2.before_begin(), { 10,11,12,13 });
	printLists("6个新元素:", list1, list2);
 
	//把list2的所有元素插入到list1的开头
	list1.insert_after(list1.before_begin(), list2.begin(), list2.end());
	printLists("插入结果:", list1, list2);
 
	//删除第二个元素和在99后面的元素
	list2.erase_after(list2.begin());
	list2.erase_after(find(list2.begin(), list2.end(), 99), list2.end());
	printLists("删除第二个和99之后的", list1, list2);
 
	//将list1排序并赋值给list2,去除重复元素
	list1.sort();
	list2 = list1;
	list2.unique();
	printLists("排序并去重", list1, list2);
 
	//合并并排序两个lists到list1
	list1.merge(list2);
	printLists("合并:", list1, list2);
 
 
}
`刀始 
list1:1 2 3 
list2:77 88 
6수新元素= 
list1:1 2 3 
list2:10 11 
入錯果= 
listl:10 11 
list2:10 11 
list1:1 2 3 
list2:1 23 
4 
99 
4 
12 
12 
12 
13 
13 
13 
10 99 77 88 99 
10 99 77 88 99 
10 99 77 88 99 
!]除第二수和99之后的 
1 2 3 4 
1 2 3 4 
listl:10 11 
list2:10 12 
*序幷去重 
12 13 10 99 77 88 99 
13 10 99 
口升= 
list1: 
list2: 
1 2 
4 10 10 11 12 13 77 88 99 99 
4 10 11 12 13 77 88 99 
2 3 3 4 4 10 10 10 11 11 12 12 
13 
13 77 77 88 88 99 99 99