更多 C++语法知识在 C++语言学记专栏
往期 STL 容器看点：
这篇文章是关于 C++所有数据结构概览中的单独专题

顺序容器	vector	array	list	deque	forward_list
关联容器	set&multiset	map&multimap	无序关联容器	Unordered set&multiset	Unordered map&multimap
容器适配器	stack	queue	priority_queue	其他容器	string

⚠️C++11 引入的 std::forward_list。

首先，请确保包含了头文件：

#include <forward_list>

std::forward_list 是一个单向链表。它的设计目标是成为最轻量、内存效率最高的顺序容器。为了实现这一目标，它在功能上做出了一些牺牲，比如不支持反向遍历，也没有 size() 方法。可以将其看作是 std::list 的一个更节省空间、但功能更受限的版本。

---

1. 构造函数 (Constructors)

用于创建和初始化一个 forward_list，其构造函数与其它顺序容器类似。

• forward_list(): 创建一个空的 forward_list。

• forward_list(size_type count, const T& value): 创建包含 count 个 value 元素的 forward_list。

• forward_list(size_type count): 创建包含 count 个值初始化元素的 forward_list。

• forward_list(InputIt first, InputIt last): 使用迭代器范围 [first, last) 构造。

• forward_list(const forward_list& other): 拷贝构造函数。

• forward_list(forward_list&& other): 移动构造函数。

• forward_list(std::initializer_list<T> init): 使用初始化列表构造。

示例：

std::forward_list<int> flist = {10, 20, 30};

---

2. 迭代器 (Iterators)

用于遍历 forward_list 中的元素，这是它与 list 区别最显著的地方之一。

• begin() / cbegin()

  • 功能：返回指向 forward_list 第一个元素的迭代器。

• end() / cend()

  • 功能：返回指向 forward_list 尾端（最后一个元素的下一个位置）的迭代器。

• before_begin() / cbefore_begin()

  • 功能：返回一个特殊的“首前”迭代器，它指向第一个元素之前的位置。这个迭代器对于在链表头部进行插入或删除操作至关重要。

重要提示：

1. forward_list 的迭代器是前向迭代器 (Forward Iterator)。你只能对其进行 ++ 操作，不能进行 -- 操作。

2. 它没有反向迭代器，即没有 rbegin() 或 rend() 方法。

示例：

std::forward_list<int> flist = {10, 20, 30};
for(auto it = flist.begin(); it != flist.end(); ++it) {
    std::cout << *it << " "; // 输出: 10 20 30
}

---

3. 大小 (Size)

管理 forward_list 的大小。

• empty()

  • 功能：检查 forward_list 是否为空。

• max_size()

  • 功能：返回理论上能容纳的最大元素数量。

重要提示：forward_list 没有 size() 方法！这是一个 deliberate 的设计选择，旨在保持每个节点最小的内存开销（不需要维护一个大小计数器）。如果需要获取其大小，必须手动遍历，这是一个 O(n) 操作。

#include <iterator>
// ...
std::forward_list<int> flist = {1, 2, 3, 4};
auto size = std::distance(flist.begin(), flist.end()); // size 会是 4

---

4. 元素访问 (Element Access)

• front()

  • 功能：返回对第一个元素的引用。

重要提示：forward_list 没有 以下方法：

• back(): 因为需要 O(n) 时间才能找到最后一个元素。

• operator[] 和 .at(): 因为它不是随机访问容器。

---

5. 修改器 (Modifiers)

forward_list 的修改器函数都带有 _after 后缀，反映了其单向链接的特性。

• push_front(const T& value) / emplace_front(...)

  • 功能：在链表头部添加一个元素。O(1)。

• pop_front()

  • 功能：移除链表的第一个元素。O(1)。

• insert_after(const_iterator pos, ...)

  • 功能：在迭代器 pos 指向的位置之后插入元素。这是它的核心插入方法。

• emplace_after(const_iterator pos, ...)

  • 功能：在迭代器 pos 指向的位置之后就地构造一个元素。

• erase_after(const_iterator pos) / erase_after(const_iterator first, const_iterator last)

  • 功能：移除迭代器 pos 指向位置之后的一个或多个元素。

重要提示：由于无法轻易获取前一个节点，所有在链表中间的操作都需要一个指向目标位置前一个元素的迭代器。before_begin() 正是用于在头部进行此类操作。

• assign(): 功能同其他容器。

• swap(): 功能同其他容器，O(1)。

• clear(): 功能同其他容器。

• resize(): 功能同其他容器。

示例：

std::forward_list<int> flist = {10, 40};

flist.push_front(5); // flist: {5, 10, 40}

auto it = flist.begin(); // it 指向 5
flist.insert_after(it, 7); // 在 5 之后插入 7. flist: {5, 7, 10, 40}

flist.erase_after(it); // 移除 5 之后的元素 (7). flist: {5, 10, 40}

// 在最前面插入元素
flist.insert_after(flist.before_begin(), 2); // flist: {2, 5, 10, 40}

---

6. 特有的链表操作 (Specific List Operations)

与 std::list 类似，它也提供了一些高效的成员函数。

• splice_after(const_iterator pos, forward_list& other, ...)

  • 功能：拼接。将 other 中的节点移动到当前 forward_list 的 pos 位置之后。同样是高效的 O(1) 或 O(n)指针移动操作。

• merge(forward_list& other): 功能同 list。

• sort(): 功能同 list。

• unique(): 功能同 list。

• reverse(): 功能同 list。

• remove(const T& value): 功能同 list。

• remove_if(UnaryPredicate p): 功能同 list。

---

7. 非成员函数 (Non-member functions)

• 比较运算符 (==, !=, <, >, <=, >=)

• std::swap()

重要提示：C++20 中为其他容器提供的 std::erase 和 std::erase_if 不适用于 std::forward_list，因为这些全局函数无法高效地实现 _after 语义。

总结：何时使用 std::forward_list？

forward_list 是一个高度特化的工具，适用于以下场景：

1. 对内存占用有极致要求。forward_list 的每个节点没有指向前一个节点的指针，因此比 std::list 更节省内存。

2. 当你处理海量数据，并且 std::list 的额外指针开销变得不可忽视时。

3. 你的算法只需要从头到尾的单向遍历和在头部或迭代器之后位置的插入/删除。

在绝大多数情况下，std::vector 或 std::list 是更实用、更方便的选择。只有在性能分析表明 std::list 的内存开销成为瓶颈时，才应考虑使用 std::forward_list。

---

至此我们完成了五种顺序容器的介绍，接下来进行关联容器的介绍，并且同时穿插无序关联容器。