编写基于节点的容器(例如 std::list、std::unordered_map、std::map 等)是一项有趣的练习。本章中，这种有趣之处未必会立刻显现出来。这类容器类的有趣特点将在第13章和第14章中更加明显。不过，我们仍会在此处编写一个基本的简化版本，以便在接下来的章节中更清晰地展示我们容器类型的并行演进过程。
forward_list 是对精简性的一种练习。我们希望该类型体积小巧，并能高效地完成其职责。某些 forward_list 在内存中仅占用一个指针的大小(指向序列中第一个节点的指针)。在实现中，为了使 size() 成员函数具有常数时间复杂度的保证，将额外付出一个整数(元素数量)的空间代价。
我们的实现中，ForwardList<T> 将会包含节点，每个节点保存一个由值(类型为 T)和一个指向序列中下一个节点的指针组成的配对。最后一个节点的下一个节点指针，将是一个空指针(null pointer)。
因此， ForwardList<T> 对象的表示方式将是一个指向节点的指针(Node*)，以及一个无符号整数(用于表示列表中元素的数量)。我们的实现将会非常简单，并只展示一小部分成员函数。只要保证添加的函数都能高效实现，就可以根据需要自由扩展该类的功能。
正如我们对 Vector<T> 所做的那样，将逐步展示最初的(简单的)ForwardList<T> 实现。第一步是通过符合标准库的类型别名(type aliases)来定义类，并选择内部表示形式，这与我们通常处理容器的方式一致：
#include <cstddef>
#include <algorithm>
#include <utility>
#include <iterator>
#include <initializer_list>
#include <concepts>
template <class T>
class ForwardList {
public:
using value_type = T;
using size_type = std::size_t;
using pointer = T*;
using const_pointer = const T*;
using reference = T&;
using const_reference = const T&;
// ...ForwardList<T>::Node 对象将保存一个值以及一个指向序列中下一个节点的指针。最初，下一个节点指针始终为空指针；组织节点是列表自身的责任，而各个节点则负责其所存储值的所有权：
// ...
private:
struct Node {
value_type value;
Node *next = nullptr;
Node(const_reference value) : value { value } {
}
Node(value_type &&value)
: value { std::move(value) } {
}
};
Node *head {};
size_type nelems {};
// ...一个 ForwardList<T> 对象的默认状态将等价于一个空列表(head 为 null 指针且没有元素)。对于大多数容器来说，这是一个合理默认状态。在实际中，用户通常期望默认构造函数生成一个空容器。
size() 和 empty() 这两个成员函数的实现都非常简单。我将 empty() 表达为判断 head 是否为 null 指针，而不是通过 size() 是否为零来判断，因为在某些(合理的)forward_list 实现中，size() 是可计算的，而不是存储的，这会使 size() 成为一个具有线性复杂度的操作，而不是常数时间的操作。实际上，提供一个常数时间复杂度的 size() 成员函数是一个好主意，其更符合大多数用户的预期：
// ...
public:
size_type size() const { return nelems; }
bool empty() const { return !head; }
// ...链表上的迭代器不能是原始指针，其所存储的元素在内存中并不是连续存放的。我们需要一个类，其实例可以遍历列表中的元素，并且能够考虑到元素的 const 性质(或缺乏 const 性质)。
我们(私有的)ForwardList<T>::Iterator 类将是一个以某种类型 U 为模板的类，其中(实际上)当用于 ForwardList<T>::iterator 时，U 是 T；而当用于 ForwardList<T>::const_iterator 时，U 是 const T。
C++ 中的标准迭代器预期会提供5个类型别名：
value_type：所指向值的类型。
reference：所指向值的引用的类型。
pointer：所指向值的指针的类型。
difference_type：表示两个该类型迭代器之间距离的类型(一个有符号整数类型)。
iterator_category：截至 C++20，共有6种类别，它们通过描述迭代器能做什么来指导代码生成。在我们的例子中，由于提供 ++ 操作但不提供 --，因此迭代器将归类为forward_iterator_category。
迭代器是一个描述我们如何遍历一系列值的对象，ForwardList<T>::Iterator 也不例外。迭代器所暴露的关键操作包括：
operator++() —— 向前移动一个位置；
operator!=() —— 比较两个迭代器，以判断是否到达了序列的末尾；
operator*() 和 operator→() —— 访问所指向的元素或其成员函数。
我们将 ForwardList<T> 声明为友元类(friend)，该类负责节点的组织工作，而这种操作在拥有对 cur 等私有数据成员的完全访问权限时更容易实现。
// ...
private:
template <class U> class Iterator {
public:
using value_type =
typename ForwardList<T>::value_type;
using pointer = typename ForwardList<T>::pointer;
using reference = typename ForwardList<T>::reference;
using difference_type = std::ptrdiff_t;
using iterator_category =
std::forward_iterator_tag;
friend class ForwardList<T>;
private:
Node *cur {};
public:
Iterator() = default;
Iterator(Node *p) : cur { p } {
}
Iterator& operator++() {
cur = cur->next;
return *this;
}
Iterator operator++(int) {
auto temp = *this;
operator++();
return temp;
}
bool operator==(const Iterator &other) const {
return cur == other.cur;
}
// 自C++20起，就不在需要了
bool operator!=(const Iterator &other) const {
return !(*this == other);
}
U& operator*() { return cur->value; }
const U& operator*() const { return cur->value; }
U* operator->() { return cur->value; }
const U* operator->() const { return cur->value; }
};
public:
using iterator = Iterator<T>;
using const_iterator = Iterator<const T>;
// ...上述建议的实现使用了一个基于元素类型 U 的模板，用于 Iterator<U> 遍历。我们使用了 U 而不是 T，因为 T 是 ForwardList<T> 对象中元素值的类型。在 ForwardList<T> 中，随后通过 iterator 和 const_iterator 分别为 Iterator<T> 和 Iterator<const T> 类型定义了别名。也可以选择编写两个完全不同的类型，但更倾向于使用模板，因为它更为简洁。
begin() 和 end() 这一组成员函数本质上非常简单；begin() 返回指向列表头部的迭代器，而 end() 所返回的、逻辑上表示列表尾后位置的节点是一个空指针，这正好是 Iterator<U> 的默认构造函数所生成的结果。
// ...
iterator begin() { return { head }; }
const_iterator begin() const { return { head }; }
const_iterator cbegin() const { return begin(); }
iterator end() { return {}; }
const_iterator end() const { return {}; }
const_iterator cend() const { return end(); }
// ...有时需要调用 clear() 来清空一个 ForwardList<T> 对象，这将导致销毁该容器的内容。在此实现中，为了简化代码，我让析构函数调用了 clear() 成员函数，但其实可以通过单独编写析构函数来节省一小部分处理时间(析构函数中不需要重新初始化 elems)：
// ...
void clear() noexcept {
for(auto p = head; p; ) {
auto q = p->next;
delete p;
p = q;
}
nelems = 0;
}
~ForwardList() {
clear();
}
// ...有一件事可能看起来很诱人，就是编写一个 Node 的析构函数，让它对其 next 成员执行 delete 操作；这样，clear() 函数就可以简单地写成 delete head;(这会递归地调用 head→next 的析构函数，依此类推)，然后设置 nelems = 0;。
如果是我的话，不会这么做：从原则上讲，ForwardList<T> 对象应该负责组织这些节点，而这项责任不应该交给众多的 Node 对象自己去处理。此外，还有一个小的技术问题：调用 delete head; 会导致 delete head→next; 被调用，而这又会调用 delete head→next→next;，依此类推。如果链表足够长，这将非常容易导致栈溢出，用循环来实现则完全可以避免这个问题。
这里有一个简单的经验：当每个类只承担一个责任时，生活会更加轻松。这其实是一个早已被广泛认可的设计原则，称为“单一职责原则”。这个原则是著名的面向对象设计原则 SOLID 中的“S”。让容器来管理基于节点的结构组织，让节点只负责存储值即可。
至于构造函数，我们只为这个类实现一小部分常用的构造方式：
一个默认构造函数，用于创建一个表示空列表的对象
一个构造函数，接受一个 std::initializer_list
一个复制构造函数，按顺序复制源列表中的每一个节点
一个移动构造函数
一个序列构造函数，接受两个属于某个类型 It 的对象作为参数，该类型满足 std::input_iterator 概念(本质上是说，允许至少对序列进行一次遍历并逐个访问元素，而这正是我们所需要的功能)
事实上，最后一个构造函数可以看作是前面某些构造函数的泛化形式，而只有默认构造函数和移动构造函数在单独编写时才会有优势(如果不把工作委托给一个通用构造函数，理论上可以更高效地计算序列的大小；因此，如果你的代码库中性能差异显著，可以自由选择实现方式)：
// ...
ForwardList() = default;
template <std::input_iterator It>
ForwardList(It b, It e) {
if(b == e) return;
try {
head = new Node{ *b };
auto q = head;
++nelems;
for(++b; b != e; ++b) {
q->next = new Node{ *b };
q = q->next;
++nelems;
}
} catch (...) {
clear();
throw;
}
}
ForwardList(const ForwardList& other)
: ForwardList(other.begin(), other.end()) {
}
ForwardList(std::initializer_list<T> other)
: ForwardList(other.begin(), other.end()) {
}
ForwardList(ForwardList&& other) noexcept
: head{ std::exchange(other.head, nullptr) },
nelems{ std::exchange(other.nelems, 0) } {
}
// ...不出所料，赋值操作可以通过之前 Vector<T> 类型中，使用过的安全赋值惯用法来实现：
// ...
void swap(ForwardList& other) noexcept {
using std::swap;
swap(head, other.head);
swap(nelems, other.nelems);
}
ForwardList& operator=(const ForwardList& other) {
ForwardList{ other }.swap(*this);
return *this;
}
ForwardList& operator=(ForwardList&& other) {
ForwardList{ std::move(other) }.swap(*this);
return *this;
}
// ...其余的一些操作可以合理地认为是简单的，例如 front()、operator==() 和 push_front()。
对于前向链表(forward list)，我们不会实现 back() 或 push_back() 这样的成员函数，根据表示方式选择，这样做将没有高效的实现方式(唯一合理的方法是遍历整个链表以找到最后一个节点，这会导致线性复杂度的算法)：
// ...
// 前置条件: 非空)
reference front() { return head->value; }
const_reference front() const { return head->value; }
bool operator==(const ForwardList &other) const {
return size() == other.size() &&
std::equal(begin(), end(), other.begin());
}
// 自C++20起，可以省略
bool operator!=(const ForwardList &other) const {
return !(*this == other);
}
void push_front(const_reference val) {
auto p = new Node{ val };
p->next = head;
head = p;
++nelems;
}
void push_front(T&& val) {
auto p = new Node{ std::move(val) };
p->next = head;
head = p;
++nelems;
}
// ...作为向容器中插入值的一个示例，请看下面的 insert_after() 成员函数，用于在由 pos 指向的节点之后插入一个值为 value 的节点。通过这个函数，可以轻松地构建更复杂的操作，例如向链表中某个位置之后插入一连串的值(各位读者可以试着实现它！)：
// ...
iterator insert_after
(iterator pos, const_reference value) {
auto p = new Node{ value };
p->next = pos.cur->next;
pos.cur->next = p;
++nelems;
return { p };
}
// ...为容器提供添加元素的功能无疑是一项有用的特性。同样，提供从容器中删除元素的选项也十分必要。作为一个示例，请看以下 erase_after() 成员函数的实现：
// ...
iterator erase_after(iterator pos) {
if (pos == end() || std::next(pos) == end())
return end();
auto p = pos.cur->next->next;
delete pos.cur->next;
pos.cur->next = p;
return { p->next };
}
}这样，我们便完成了对该类功能的补充。在本章的剩余部分，对于 ForwardList<T> 来说，已经没有多少改进的空间了，但我们将在第 13 章再次回顾这个类，在第 14 章中更是会深入探讨。
然而，对于 Vector<T> 来说，目前的实现还有很大提升空间……当然，这种改进是以增加一些复杂性为代价的。不过，我们已经准备好迎接这一挑战了，不是吗？