C++/STL/forward list
外观
< C++
<forward_list> 是自b:C++11标准开始,b:C++標準程式庫中的一個b:头文件,定义了b:C++标准中单链表序列容器的类模板前向链表(forward_list)。
单链表(singly linked list)存储所包含的每个成员在不同、不相关的位置;顺序保持是通过关联每个成员与其在序列中的下一个成员。由于只有指向下一个表项的链接,因此具有插入、删除表项速度快、消耗内存空间少的特点。但只能向前遍历。
与之不同,std::list
是双向链表,每个成员保持指向下一项与前一项的两个指针,因此可以双向遍历,但消耗内存空间更多,插入或删除成员时的速度稍慢。
与其他b:C++標準程式庫中的序列容器(array、vector、deque)相比,forward_list在容器内任意位置的成员的插入、提取(extracting)、移动、删除操作的速度更快,因此被广泛用于排序算法。
前向链表(以及std::list
)的主要缺点是不能在常量时间内随机访问任意成员,对成员的访问需要线性时间代价;以及存储链接信息需要消耗内存,特别是当包含大量的小规模成员时。std::forward_list
处于效率考虑,有意不提供size()
成员函数。获取std::forward_list
所包含的成员个数需要用std::distance(_begin,_end)
算法。
模板类
[编辑]template < class T, class Alloc = allocator<T> > class forward_list;
成员类型
[编辑]成员类型 | 定义 | 注释 |
---|---|---|
value_type | 第一个模板参数(T) | |
allocator_type | 第二个模板参数(Alloc) | 缺省allocator<value_type> |
reference | value_type& | |
const_reference | const value_type& | |
pointer | allocator_traits<allocator_type>::pointer | 对于缺省分配器为value_type* |
const_pointer | allocator_traits<allocator_type>::const_pointer | 对于缺省分配器为const value_type* |
iterator | 指向value_type的前向迭代器 | 可转换为const_iterator |
const_iterator | 指向const value_type的前向迭代器 | |
difference_typ | 有符号的整形,即iterator_traits<iterator>::difference_type | 通常为 ptrdiff_t |
size_type | 可表示difference_type的任何非负值的无符号整形 | 通常为size_t |
成员函数
[编辑]- (constructor) 构造函数
- (destructor) 析构函数
- operator= 拷贝赋值运算符、移动赋值运算符、初始化器运算符
- 迭代器
- before_begin 返回开始位置之前的迭代器
- begin 返回指向开始位置的迭代器
- end 返回指向结束位置的迭代器
- cbefore_begin 返回开始位置之前的const迭代器
- cbegin 返回指向开始位置的const迭代器
- cend 返回指向结束位置的const迭代器
- 容量Capacity
- empty 测试容器是否为空
- max_size 返回容器的可能允许的最大容量
- 成员访问(Element access)
- front 返回第一个成员的引用
- 修改器(Modifier)
- assign 赋值替换全部内容
- emplace_front 在链表头部原位构造新的成员并插入到链表最开始处
- push_front 在链表头部插入元素,使用拷贝语义或移动语义
- pop_front 删除链表头部元素
- emplace_after 在当前位置的尾方向原位插入元素
- insert_after 在当前位置的尾方向插入成员,可译为拷贝语义、移动语义、值被插入多次、插入一个序列、插入初始化器的内容
- erase_after 在当前位置的尾方向的下一个成员或子序列被删除
- swap 交换两个链表的内容
- resize 改变链表的容量
- clear 清空链表的内容
- 操作(Operation)
- splice_after 把另一个链表的单个成员、或子序列、或整个序列,移动插入到当前链表指定位置之后
- remove 删除(析构)具有特定内容的成员
- remove_if 删除使谓词为真的成员
- unique 删除与序列中前一个成员相等(或者二元谓词为真)的成员。特别适用于排序后链表
- merge 两个已经有序的链表做有序合并
- sort 对一个链表的成员做稳定排序,要求是strict weak ordering谓词[1]
- reverse 把一个链表所有成员逆序
- 观察器(Observer)
- get_allocator 获取当前的分配器
重载的非成员函数模板
[编辑]- 比较两个前向链表的关系运算符函数模板
- bool operator==(lhs, rhs),两个链表的对应成员两两比较
- bool operator!=(lhs, rhs)
- bool operator<(lhs, rhs),两个链表的对应成员做词典(lexicographical)比较
- bool operator>(lhs, rhs)
- bool operator<=(lhs, rhs)
- bool operator>=(lhs, rhs)
- swap (lhs, rhs)
参考文献
[编辑]页面Template:ReflistH/styles.css没有内容。
- ↑ 见
Effective STL 条款21:
- Strict: pred (X, X) is always false.
- Weak: If ! pred (X, Y) && !pred (Y, X), X==Y.
- Ordering: If pred (X, Y) && pred (Y, Z), then pred (X, Z).