详解C++ STL模拟实现forward_list

namespace qgw {
	/// @brief forward_list 中每个节点
	/// @tparam T 节点存储的数据类型
	template <class T>
	struct _forward_list_node {
		_forward_list_node(const T& data = T());	// 节点类的构造函数
			
		_forward_list_node<T>* _next;				// 指向后一节点
		T _data;									// 存储节点数据
	};

	/// @brief forward_list 的迭代器
	/// @tparam T forward_list 数据的类型
	/// @tparam Ref 数据的引用类型
	/// @tparam Ptr 数据的指针类型
	template <class T, class Ref, class Ptr>
	struct _forward_list_iterator {
		typedef _forward_list_iterator<T, T&, T*>		iterator;
		typedef _forward_list_iterator<T, Ref, Ptr>		self;

		typedef Ptr pointer;
		typedef Ref reference;
		typedef _forward_list_node<T> forward_list_node;

		// 构造函数
		_forward_list_iterator(forward_list_node* node = nullptr);

		// 各种运算符重载
		bool operator==(const self& x) const;
		bool operator!=(const self& x) const;
		reference operator*() const;
		pointer operator->() const;
		self& operator++();
		self operator++(int);

		forward_list_node* _node;	// 指向对应的 forward_list 节点
	};

	template <class T>
	class forward_list {
	public:
		typedef T* pointer;
		typedef const T* const_pointer;
		typedef T& reference;
		typedef const T& const_reference;
		typedef _forward_list_node<T>	forward_list_node;
		typedef _forward_list_iterator<T, T&, T*>             iterator;
		typedef _forward_list_iterator<T, const T&, const T*> const_iterator;

	public:
		// 默认成员函数
		forward_list();
		forward_list(const forward_list<T>& other);
		forward_list<T>& operator=(const forward_list<T>& other);
		~forward_list();

		// 元素访问
		reference front();
		const_reference front() const;

		// 迭代器
		iterator begin();
		const_iterator begin() const;
		iterator end();
		const_iterator end() const;

		// 容量
		bool empty() const;

		// 修改器
		void clear();
		iterator insert_after(iterator pos, const_reference val);
		void push_front(const_reference val);
		iterator erase_after(iterator pos);
		void pop_front();
		void swap(forward_list& other);

	private:
		forward_list_node* _node;
	};
}

/// @brief 节点类的构造函数
/// @param data 用来构造节点的初值
_forward_list_node(const T& data = T())
    : _data(data) {
        _next = nullptr;
    }

/// @brief 构造一个空链表
forward_list() {
    _node = new forward_list_node;    // 创建一个头节点
    _node->_next = _node;            // 后面指向自己
}

/// @brief 释放资源
~forward_list () {
    clear();
    delete _node;
    _node = nullptr;
}

/// @brief 迭代器的构造函数
/// @param node 用来构造的节点
_forward_list_iterator(forward_list_node* node = nullptr) {
    _node = node;
}

/// @brief 判断两迭代器指向的节点是否相同
/// @param x 用来比较的迭代器
/// @return 相同返回 true，不同返回 false
bool operator==(const self& x) const {
    return _node == x._node;
}

/// @brief 判断两迭代器指向的节点是否不同
/// @param x 用来比较的迭代器
/// @return 不同返回 true，相同返回 false
bool operator!=(const self& x) const {
    return !operator==(x);
}

/// @brief 获取指向节点中的数据值
/// @return 返回指向节点数据的引用
reference operator*() const {
    return (*_node)._data;
}

// 有一个 Person 类，里面有身高和体重两个成员
struct Person {
    double height;
    double weight;
};

Person p1 = { 165, 105 };
Person* p = &p1;
cout << (*p).height << endl;    // 获取身高数据
cout << p->weight << endl;        // 获取体重数据

/// @brief 获取节点中数据的地址
/// @return 返回节点指向的数据的地址
pointer operator->() const {
    return &(operator*());
}

/// @brief 前置 ++
/// @return 返回前进一步后的迭代器
self& operator++() {
    _node = _node->_next;
    return *this;
}

/// @brief 后置 ++
/// @param  无作用，只是为了与前置 ++ 进行区分，形成重载
/// @return 返回当前的迭代器
self operator++(int) {
    self tmp = *this;
    ++(*this);
    return tmp;
}

/// @brief 返回容器首元素的引用
/// @return 首元素的引用
reference front() {
    return *begin();
}

// 与上面唯一不同就是用于 const 容器
const_reference front() const {
    return *begin();
}

/// @brief 返回指向 forward_list 首元素的迭代器
/// @return 指向首元素的迭代器
iterator begin() {
    // 根据节点指针构造迭代器
    return iterator(_node->_next);
}

// const 版本供 const 容器使用
const_iterator begin() const {
    return const_iterator(_node->_next);
}

/// @brief 返回指向 forward_list 末元素后一元素的迭代器
/// @return 指向最后元素下一位置的迭代器
iterator end() {
    // 调用 iterator 构造函数
    return iterator(_node);
}

const_iterator end() const {
    return const_iterator(_node);
}

/// @brief 检查容器是否无元素
/// @return 若容器为空则为 true，否则为 false
bool empty() const {
    return begin() == end();
}

/// @brief 在容器中的指定位置后插入元素
/// @param pos 内容将插入到其后的迭代器
/// @param val 要插入的元素值
/// @return 指向被插入元素的迭代器
iterator insert_after(iterator pos, const_reference val) {
    forward_list_node* tmp = new forward_list_node(val);    // 创建要插入的节点
    tmp->_next = pos._node->_next;                            // (1)
    pos._node->_next = tmp;                                    // (2)
    return tmp;
}

/// @brief 头插给定元素 val 到容器起始
/// @param val 要头插的元素值
void push_front(const_reference val) {
    // end() 返回头节点位置的迭代器，在这之后插入是头插
    insert_after(end(), val);
}

/// @brief 从容器移除 pos 后面一个元素
/// @param pos 指向要被移除元素前一个元素的迭代器
/// @return 最后移除元素之后的迭代器
iterator erase_after(iterator pos) {
    forward_list_node* nextNode = pos._node->_next;        // 记录 pos 指向节点的下一节点
    pos._node->_next = nextNode->_next;                    // (1)
    delete (nextNode);
    return (iterator)(pos._node->_next);
}

/// @brief 移除容器首元素
void pop_front() {
    erase_after(end());
}

/// @brief 从容器擦除所有元素
void clear() {
    while (!empty()) {
        erase_after(end());
    }
}

/// @brief 将内容与 other 的交换
/// @param other 要与之交换内容的容器
void swap(forward_list& other) {
    std::swap(_node, other._node);
}