前向列表
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此条目需要补充更多来源。 (2024年3月22日) |
前向列表(英语:forward list)[1]是于标准模板函数库中的序列容器(sequence containers),以单向链表实现,自C++11标准开始被定义于C++标准函数库里的 <forward_list>
头文件[2]。
与 std::list
相比,原本 std::list
是一个双向链表,每个节点都有指向上一个节点与下一个节点的指针,所以可以双向遍历,但这样会使得内存空间消耗得更多,速度会相对地变慢。但 std::forward_list
提供了不需要双向迭代时,更节省存储空间的容器。
std::forward_list
的优点是能够支持在容器中的任何位置更快速地插入、移除、提取与移动元素。但因为它是以单向链表实现,因此不支持随机存取,须以线性时间来走访。
模板
自C++11
template<
class T,
class Allocator = std::allocator<T>
> class forward_list
自C++17
namespace pmr {
template< class T >
using forward_list = std::forward_list<T, std::pmr::polymorphic_allocator<T>>;
}
成员类型
属性 | 类型 | 解释 |
---|---|---|
value_type | T | 容器中存储的元素类型 |
allocator_type | Allocator | 用于分配内存的分配器类型 |
size_type | Unsigned integer type (usually std::size_t) | 表示容器大小的无符号整数类型,通常是 std::size_t |
difference_type | Signed integer type (usually std::ptrdiff_t) | 表示迭代器之间距离的有符号整数类型,通常是 std::ptrdiff_t |
reference | value_type& | 元素的引用类型 |
const_reference | const value_type& | 元素的常量引用类型 |
pointer | std::allocator_traits<Allocator>::pointer | 指向元素的指针类型 |
const_pointer | std::allocator_traits<Allocator>::const_pointer | 指向常量元素的指针类型 |
iterator | LegacyForwardIterator to value_type | 迭代器类型,可用于遍历容器中的元素 |
const_iterator | LegacyForwardIterator to const value_type | 常量迭代器类型,用于以只读方式遍历容器中的元素 |
成员函数
成员函数 | 解释 |
---|---|
(constructor) | 构造函数,用于建构 forward_list
|
(destructor) | 析构函数,用于销毁 forward_list
|
operator= | 将值赋予容器 |
assign | 将值赋予容器 |
assign_range(C++23) | 将一个值范围赋予容器 |
get_allocator | 返回相关系的分配器 |
成员访问
成员函数 | 解释 |
---|---|
front | 访问第一个元素 |
迭代器
成员函数 | 解释 |
---|---|
before_begin cbefore_begin |
返回指向起始之前的元素的迭代器 |
begin cbegin |
返回指向起始的迭代器 |
end cend |
返回指向尾端的迭代器 |
容量
成员函数 | 解释 |
---|---|
empty | 检查容器是否为空 |
max_size | 返回可能存储的最大元素数量 |
修饰语
成员函数 | 解释 |
---|---|
clear | 清空内容 |
insert_after | 在一个元素之后插入元素 |
emplace_after | 在一个元素之后原地构造元素 |
insert_range_after(C++23) | 在一个元素之后插入一个值范围的元素 |
erase_after | 在一个元素之后删除一个元素 |
push_front | 在开始处插入一个元素 |
emplace_front | 在开始处原地构造一个元素 |
prepend_range(C++23) | 在开始处添加一个值范围的元素 |
pop_front | 删除第一个元素 |
resize | 改变存储的元素数量 |
swap | 交换内容 |
操作
成员函数 | 解释 |
---|---|
merge | 合并两个排序的列表 |
splice_after | 从另一个 forward_list 移动元素
|
remove remove_if |
删除满足特定条件的元素 |
reverse | 反转元素的顺序 |
unique | 删除连续重复的元素 |
sort | 对元素进行排序 |
C++ 代码实例
建构
# include <iostream>
# include <forward_list> // 導入前向串列標頭檔
int main(){
std::forward_list<int> list1 = {1, 2, 3, 4};
}
插入元素
# include <iostream>
# include <forward_list>
int main(){
std::forward_list<int> list1 = {1, 2, 3, 4};
auto it = list1.begin();
std::advance(it, 2);
list1.insert_after(it, 5);
// list1 = {1, 2, 3, 5, 4}
}
删除所有指定值
# include <iostream>
# include <forward_list>
int main(){
std::forward_list<int> list1 = {1, 2, 3, 3, 4};
list1.remove(3);
// list1 = {1, 2, 4}
}
反转串列
# include <iostream>
# include <forward_list>
int main(){
std::forward_list<int> list1 = {1, 2, 3, 4};
list1.reverse();
// list1 = {4, 3, 2, 1}
}
获取长度
基于效率考量,std::forward_list
不提供 size()
的方法。取而代之,得到成员个数需使用std::distance(_begin, _end)
。
# include <iostream>
# include <forward_list>
int main(){
std::forward_list<int> list1 = {1, 2, 3, 4};
std::cout << "Size of list1: " << std::distance(list1.begin(), list1.end()) << std::endl;
}
指定范围(C++23)
# include <iostream>
# include <forward_list>
int main(){
std::forward_list<int> list1 = {1, 2, 3, 4};
std::forward_list<int> list2;
// 使用 assign_range 將 list1 中的元素賦值給 list2
list2.assign_range(list1.begin(), list1.end());
// list2 現在包含與 list1 相同的元素
}
原地建构
# include <iostream>
# include <forward_list>
int main(){
std::forward_list<int> list1 = {1, 2, 3, 4};
auto it = list1.begin();
std::advance(it, 2);
// 在位置 it 的後面原地建構元素 5
list1.emplace_after(it, 5);
// list1 = {1, 2, 3, 5, 4}
}
插入范围(C++23)
# include <iostream>
# include <forward_list>
# include <vector>
int main(){
std::forward_list<int> list1 = {1, 2, 3, 4};
std::vector<int> vec = {5, 6, 7};
auto it = list1.begin();
std::advance(it, 2);
// 在位置 it 的後面插入 vec 中的元素
list1.insert_range_after(it, vec.begin(), vec.end());
// list1 = {1, 2, 3, 5, 6, 7, 4}
}
前置范围(C++23)
# include <iostream>
# include <forward_list>
# include <vector>
int main(){
std::forward_list<int> list1 = {3, 4, 5};
std::vector<int> vec = {1, 2};
// 在開始處加入 vec 中的元素
list1.prepend_range(vec.begin(), vec.end());
// list1 = {1, 2, 3, 4, 5}
}
参考文献
|