详解C++ STL模拟实现list

namespace qgw {
	/// @brief list 中每个节点
	/// @tparam T 节点存储的数据的类型
	template <class T>
	struct _list_node {
		_list_node(const T& data = val());	// 节点类的构造函数

		_list_node<T>* _prev;				// 指向前一节点
		_list_node<T>* _next;				// 指向后一节点
		T _data;							// 存储节点数据
	};

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

		typedef T		value_type;
		typedef Ptr		pointer;
		typedef Ref		reference;
		typedef _list_node<T> list_node;
		
        // 构造函数
        _list_iterator(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);
		self& operator--();
		self operator++(int);

		list_node* _node;	// 指向对应的 list 节点
	};

	template <class T>
	class list {
	public:
		typedef T value_type;
		typedef T* pointer;
		typedef T& reference;
		typedef _list_node<T>	list_node;
		typedef _list_iterator<T, T&, T*>             iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

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

		// 元素访问
		reference front();
		reference back();

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

		// 容量
		bool empty() const;
		size_t size() const;

		// 修改器
		void clear();
		iterator insert(iterator pos, const T& val);
		void push_front(const T& val);
		void push_back(const T& val);
		iterator erase(iterator pos);
		void pop_front();
		void pop_back();
		void swap(list& other);

		// 操作
		void splice(iterator pos, list& other);
		void splice(iterator pos, list& other, iterator it);
        void splice(iterator pos, list& other, iterator first, iterator last);
		void merge(list& other);
		void remove(const T& value);
		void reverse();
		void unique();

	private:
		list_node* _node;	// 指向链表头节点
	};
}

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

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

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

/// @brief 用给定容器初始化
/// @param other 用来初始化的容器
list(const list<T>& other) {
    _node = new list_node; 
    _node->_next = _node;
    _node->_prev = _node;
    for (const auto& e : other) {
        push_back(e); 
    }
}

/// @brief 替换容器内容
/// @param other 用作数据源的另一容器
/// @return *this
list<T>& operator=(const list<T>& other) {
    // tmp 出了作用域就销毁了
    list<T> tmp(other);
    swap(tmp);
    // 返回引用可以连续赋值
    return *this;
}

/// @brief list 迭代器的构造函数
/// @param node 用来构造的节点
_list_iterator(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 _node != x._node;
}

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

// 有一个学生类，里面有姓名和学号两个成员
struct Stu {
	string name;
    string id;
};

list<Stu> s;
Stu s1 = { "qgw", "001" };
Stu s2 = { "wlr", "002" };
s.push_back(s1);
s.push_back(s2);
list<Stu>::iterator ptr = s.begin();
// 输出第一个学生的姓名和学号
cout << (*ptr).name << endl;
cout << s.begin()->id << 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 返回后退一步后的迭代器
self& operator--() {
    _node = _node->_prev;
    return *this;
}

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

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

/// @brief 返回容器中最后一个元素的引用
/// @return 最后元素的引用
reference back() {
    return *(--end());
}

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

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

/// @brief 返回指向 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 返回容器中的元素数
/// @return 容器中的元素数量
size_t size() const {
    size_t sz = 0;
    auto it = begin();
    while (it != end()) {
        ++it;
        ++sz;
    }
    return sz;
}

/// @brief 插入元素到容器中的指定位置
/// @param pos     将内容插入到 pos 之前
/// @param val 要插入的元素值
/// @return 指向被 插入 val 的迭代器
iterator insert(iterator pos, const T& val) {
    list_node* tmp = new list_node(val);    // 创建要插入的节点
    tmp->_next = pos._node;                    // (1)
    tmp->_prev = pos._node->_prev;            // (2)
    (pos._node->_prev)->_next = tmp;        // (3)
    pos._node->_prev = tmp;                    // (4)
    return tmp;
}

/// @brief 添加给定元素 val 到容器起始
/// @param val 要添加的元素值
void push_front(const T& val) {
    insert(begin(), val);
}

/// @brief 添加给定元素 val 到容器尾
/// @param val 要添加的元素值
void push_back(const T& val) {
    insert(end(), val);
}

/// @brief 从容器擦除指定的元素
/// @param pos 指向要移除的元素的迭代器
/// @return 最后移除元素之后的迭代器
iterator erase(iterator pos) {
    list_node* nextNode = pos._node->_next;		// 记录 pos 指向节点的下一节点
    list_node* prevNode = pos._node->_prev;		// 记录 pos 指向节点的前一节点
    prevNode->_next = nextNode;					// (1)
    nextNode->_prev = prevNode;					// (2)
    delete (pos._node);
    return (iterator)nextNode;
}

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

/// @brief 移除容器的末元素
void pop_back() {
    erase(--end());
}

/// @brief 从容器擦除所有元素
void clear() {
    iterator it = begin();
    while (it != end()) {
        it = erase(it);
    }
}

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

/// @brief 将 [first, last) 范围的所有元素移动到 pos 之前
/// @param pos 将内容移动到 pos 之前
/// @param first 范围起始位置
/// @param last 范围结束位置
void transfer(iterator pos, iterator first, iterator last) {
    if (pos != last) {
        last._node->_prev->_next = pos._node;        // (1)
        first._node->_prev->_next = last._node;        // (2)
        pos._node->_prev->_next = first._node;        // (3)
        list_node* tmp = pos._node->_prev;            // (4)
        pos._node->_prev = last._node->_prev;        // (5)
        last._node->_prev = first._node->_prev;        // (6)
        first._node->_prev = tmp;                    // (7)
    }
}

/// @brief 将 other 接合于 pos 所指位置之前，两者不能是同一 list
/// @param pos 将内容插入到它之前
/// @param other 要从它转移内容的另一容器
void splice(iterator pos, list& other) {
    if (!other.empty()) {
        transfer(pos, other.begin(), other.end());
    }
}

/// @brief 将 it 所指元素接合到 pos 所指位置之前
/// @param pos 	将内容插入到它之前
/// @param other 要从它转移内容的另一容器
/// @param it 从 other 转移到 *this 的元素
void splice(iterator pos, list& other, iterator it) {
    // 取得一个 [i, j) 的范围，使得能调用 transfer
    iterator j = it;
    ++j;
    // 检查是否有必要执行
    // pos == it 时说明 pos 和 it 指向的是同一节点
    // pos == j 时说明，it 刚好在 pos 之前
    if (pos == it || pos == j) {
        return;
    }
    transfer(pos, it, j);
}

/// @brief 将 [first, last) 内的所有元素接合于 pos 所指位置之前
/// @param pos 将内容插入到它之前
/// @param first 起始位置
/// @param last 结束位置
void splice(iterator pos, list& other, iterator first, iterator last) {
    if (first != last) {
        transfer(pos, first, last);
    }
}

/// @brief 合并两个递增链表，合并到 *this 上
/// @param other 要合并的另一容器
void merge(list& other) {
    iterator first1 = begin();
    iterator end1 = end();
    iterator first2 = other.begin();
    iterator end2 = other.end();

    while (first1 != end1 && first2 != end2) {
        if (*first2 < *first1) {
            iterator next = first2;
            transfer(first1, first2, ++next);
            first2 = next;
        } else {
            ++first1;
        }
    }
    if (first2 != end2) {
        // 将 other 链表剩余元素合并到 *this 中
        transfer(first1, first2, end2);
    }
}

/// @brief 移除等于 val 元素
/// @param val 要移除的元素的值
void remove(const T& val) {
    iterator first = begin();
    iterator last = end();
    while (first != last) {
        iterator next = first;
        ++next;
        if (*first == val) {
            erase(first);
        }
        first = next;
    }
}

/// @brief 将 *this 的内容逆置
void reverse() {
    // 空链表或只有一个元素直接返回
    if (_node->_next == _node || _node->_next->_next == _node) {
        return;
    }

    iterator first = begin();
    ++first;
    while (first != end()) {
        iterator old = first;			// 第一次循环时指向第 2 个元素
        ++first;						// 第一次循环时指向第 3 个元素
        transfer(begin(), old, first);
    }
}

/// @brief 移除数值相同的连续元素
void unique() {
    iterator first = begin();
    iterator last = end();
    if (first == last) {
        return;
    }

    iterator next = first;
    while (++next != last) {
        // 此时 next 指向 first 下一个节点
        if (*first == *next) {
            // 连续的相同，就删除后一个
            erase(next);
        } else {
            // 不相同 first 向 end 移动
            first = next;
        }
        // 使 next 再次指向 first
        // 这样再进 while 时，++next 又使 next 指向 first 下一个
        next = first;
    }
}