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)

重载的非成员函数模板

编辑
  • 比较两个前向链表的关系运算符函数模板
    • 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没有内容。

  1. 见 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).