list模拟实现
成员类型表
这个表中列出了C++标准库中list容器的一些成员类型定义。这些类型定义是为了使list能够与C++标准库的其他组件协同工作，并提供一些通用的标准接口。每个成员类型的用处：
value_type: 这个成员类型代表list容器中存储的数据类型，即模板参数T的类型。
allocator_type: 这个成员类型代表分配器的类型，用于为容器的内存分配和管理。默认情况下，使用allocator<value_type>作为分配器。
reference: 这个成员类型表示对元素的引用类型。对于默认分配器，它是value_type&，即对元素的引用。
const_reference: 这个成员类型表示对常量元素的引用类型。对于默认分配器，它是const value_type&，即对常量元素的引用。
pointer: 这个成员类型表示指向元素的指针类型。对于默认分配器，它是value_type*，即指向元素的指针。
const_pointer: 这个成员类型表示指向常量元素的指针类型。对于默认分配器，它是const value_type*，即指向常量元素的指针。
iterator: 这个成员类型是一个双向迭代器类型，可以用于遍历容器的元素。它可以隐式转换为const_iterator，允许在遍历时修改元素。
const_iterator: 这个成员类型也是一个双向迭代器类型，用于遍历常量容器的元素，不允许修改元素。
reverse_iterator: 这个成员类型是iterator的逆向迭代器，可以从容器尾部向头部遍历。
const_reverse_iterator: 这个成员类型是const_iterator的逆向迭代器，用于从常量容器的尾部向头部遍历。
difference_type: 这个成员类型表示两个迭代器之间的距离，通常使用的是ptrdiff_t，与指针的差值类型相同。
size_type: 这个成员类型表示非负整数的类型，通常使用的是size_t，用于表示容器的大小。
这些成员类型的定义使得list容器能够与其他C++标准库的组件以及用户自定义的代码进行交互，从而实现更加通用和灵活的功能。
list_node节点结构定义
定义链表的节点结构 list_node，用于存储链表中的每个元素。让我们逐一解释每个部分的含义。
template<class T> struct list_node { T _data; // 存储节点的数据 list_node<T>* _next; // 指向下一个节点的指针 list_node<T>* _prev; // 指向前一个节点的指针 // 构造函数 list_node(const T& x = T()) :_data(x) // 使用参数 x 初始化 _data , _next(nullptr) // 初始化 _next 为 nullptr , _prev(nullptr) // 初始化 _prev 为 nullptr {} };
T _data;：存储节点中的数据，类型为模板参数 T，可以是任意数据类型。
list_node<T>* _next;：指向下一个节点的指针，用于构建链表结构。初始时设为 nullptr，表示当前节点没有后继节点。
list_node<T>* _prev;：指向前一个节点的指针，同样用于构建链表结构。初始时设为 nullptr，表示当前节点没有前驱节点。
构造函数 list_node(const T& x = T())：构造函数可以接收一个参数 x，用于初始化节点的数据。如果没有传入参数，默认构造一个空节点。
通过这个节点结构，你可以创建一个双向链表list，将不同类型的数据存储在节点中，并连接节点以构建链表的结构。这个节点结构为链表的实现提供了基础。
std::__reverse_iterator逆向迭代器实现
#pragma once namespace xzq { // 复用，迭代器适配器 template<class Iterator, class Ref, class Ptr> struct __reverse_iterator { Iterator _cur; typedef __reverse_iterator<Iterator, Ref, Ptr> RIterator; __reverse_iterator(Iterator it) :_cur(it) {} RIterator operator++() { --_cur; return *this; } RIterator operator--() { ++_cur; return *this; } Ref operator*() { auto tmp = _cur; --tmp; return *tmp; } Ptr operator->() { return &(operator*()); } bool operator!=(const RIterator& it) { return _cur != it._cur; } }; }
说明：
__reverse_iterator类模板定义了一个逆向迭代器，它有三个模板参数：Iterator（迭代器的类型）、Ref（引用类型）和Ptr（指针类型）。
_cur是一个私有成员变量，保存当前迭代器的位置。构造函数接受一个正向迭代器作为参数，并将其存储在
_cur成员变量中。
operator++()重载了递增操作符，让迭代器向前移动一个位置。
operator--()重载了递减操作符，让迭代器向后移动一个位置。
operator*()重载了解引用操作符，返回逆向迭代器指向的元素的引用。
operator->()重载了成员访问操作符，返回逆向迭代器指向的元素的指针。
operator!=()重载了不等于操作符，用于判断两个逆向迭代器是否不相等。
这个逆向迭代器可以用于支持从容器的尾部向头部的方向进行迭代。在 C++ 标准库中，std::reverse_iterator 用于实现类似的功能。
这个代码实现了一个迭代器适配器。迭代器适配器是一种在现有迭代器基础上提供不同功能的封装器，使得原本的迭代器能够适应新的使用场景。
__reverse_iterator 就是一个逆向迭代器适配器。它封装了一个正向迭代器，但通过重载操作符等方式，使其可以从容器的尾部向头部进行迭代。这样的适配器能够让原本的正向迭代器在逆向遍历时更加方便。在下面的list模拟实现中的反向迭代器函数需要用到，当然它也可以适用于其他容器的模拟实现，因场景而定，并不是所有容器都可以适用。
list迭代器 __list_iterator定义
迭代器 __list_iterator，用于遍历链表中的节点。让我们逐一解释每个部分的含义。
template<class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> Node; // 定义一个类型别名 Node，用于表示 list 节点的类型 typedef __list_iterator<T, Ref, Ptr> iterator; // 定义一个类型别名 iterator，用于表示 list 迭代器的类型 typedef bidirectional_iterator_tag iterator_category; // 定义迭代器的分类，这里是双向迭代器 typedef T value_type; // 定义元素的类型，即模板参数 T typedef Ptr pointer; // 定义指向元素的指针类型，用于迭代器 typedef Ref reference; // 定义对元素的引用类型，用于迭代器 typedef ptrdiff_t difference_type; // 定义表示迭代器之间距离的类型 Node* _node; // 指向链表中的节点 __list_iterator(Node* node) :_node(node) // 初始化迭代器，指向给定的节点 {} bool operator!=(const iterator& it) const { return _node != it._node; // 比较两个迭代器是否不相等 } bool operator==(const iterator& it) const { return _node == it._node; // 比较两个迭代器是否相等 } Ref operator*() { return _node->_data; // 返回当前节点的数据 } Ptr operator->() { return &(operator*()); // 返回当前节点数据的地址 } // ++it iterator& operator++() { _node = _node->_next; // 迭代器自增，指向下一个节点 return *this; } // it++ iterator operator++(int) { iterator tmp(*this); // 创建一个临时迭代器保存当前迭代器 _node = _node->_next; // 迭代器自增，指向下一个节点 return tmp; // 返回保存的临时迭代器 } // --it iterator& operator--() { _node = _node->_prev; // 迭代器自减，指向前一个节点 return *this; } // it-- iterator operator--(int) { iterator tmp(*this); // 创建一个临时迭代器保存当前迭代器 _node = _node->_prev; // 迭代器自减，指向前一个节点 return tmp; // 返回保存的临时迭代器 } };
这个迭代器结构为链表提供了遍历节点的能力。它可以用于循环遍历链表的每个元素，提供了类似于指针的行为，使得遍历链表变得更加方便。
这里提一下迭代器类型的分类：
C++ 标准库中的迭代器分为五种主要类型，每种类型提供了不同的功能和支持的操作。这些类型分别是：
输入迭代器（Input Iterator）：只允许从容器中读取元素，但不能修改容器内的元素。只支持逐个移动、解引用、比较以及比较是否相等等操作。输入迭代器通常用于算法中，如 std::find()。
输出迭代器（Output Iterator）：只允许向容器写入元素，但不能读取容器内的元素。支持逐个移动和逐个写入元素等操作。
前向迭代器（Forward Iterator）：类似于输入迭代器，但支持多次解引用。前向迭代器可以用于一些需要多次迭代的操作，如遍历一个单链表。
双向迭代器（Bidirectional Iterator）：在前向迭代器的基础上，增加了向前遍历的能力。除了支持输入迭代器的操作外，还支持向前移动和逐个向前移动元素等操作。
随机访问迭代器（Random Access Iterator）：是最强大的迭代器类型。除了支持前向迭代器和双向迭代器的所有操作外，还支持类似指针的算术操作，如加法、减法，以及随机访问容器中的元素。随机访问迭代器通常用于数组等支持随机访问的数据结构中。
在上面的代码中，typedef bidirectional_iterator_tag iterator_category; 表示这个迭代器是双向迭代器类型，因此它应该支持前向和双向迭代器的所有操作，包括移动、解引用、比较等。这是为了确保这个迭代器在遍历 list 类的容器元素时能够正常工作。
list类成员定义
下面的代码是C++ 中双向链表模板类 list 的类定义部分。这个类定义了一些公共的成员类型和私有成员变量来支持链表的操作。让我们逐一解释每个部分的含义。
template<class T> class list { typedef list_node<T> Node; public: // 定义迭代器类型 typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __reverse_iterator<iterator, T&, T*> reverse_iterator; typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator; private: Node* _head; };
typedef list_node<T> Node;：定义一个别名 Node，代表链表节点类型 list_node<T>。
typedef __list_iterator<T, T&, T*> iterator;：定义了链表的正向迭代器类型 iterator，它使用 __list_iterator 结构模板，并指定了相应的参数类型。
typedef __list_iterator<T, const T&, const T*> const_iterator;：定义了链表的常量正向迭代器类型 const_iterator，用于在不修改链表元素的情况下遍历链表。
typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;：定义了链表的反向迭代器类型 reverse_iterator，这个迭代器从链表末尾向链表开头遍历。
typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;：定义了链表的常量反向迭代器类型 const_reverse_iterator。
Node* _head;：链表的私有成员变量，指向链表的头节点。
这个部分的代码定义了 list 类的公共成员类型和私有成员变量，为实现链表的操作和管理提供了基础。
list成员函数定义
1.begin()、end()、rbegin()和rend()
const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } reverse_iterator rbegin() { return reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); }
这部分代码是关于 list 类的迭代器成员函数的定义。它们用于返回不同类型的迭代器，使得用户可以遍历 list 容器的元素。
const_iterator begin() const: 这是一个常量成员函数，返回一个常量迭代器，它指向容器中的第一个元素（节点）。由于是常量迭代器，所以不允许通过它修改容器内的元素。
const_iterator end() const: 这也是一个常量成员函数，返回一个常量迭代器，它指向容器末尾的“尾后”位置，即不存在的元素位置。常量迭代器不能用于修改元素。
iterator begin(): 这是一个非常量成员函数，返回一个非常量迭代器，它指向容器中的第一个元素（节点）。允许通过这个迭代器修改容器内的元素。
iterator end(): 这也是一个非常量成员函数，返回一个非常量迭代器，它指向容器末尾的“尾后”位置，即不存在的元素位置。非常量迭代器可以用于修改元素。
reverse_iterator rbegin(): 这是一个返回反向迭代器的函数，它将 end() 的迭代器作为参数传递给 reverse_iterator 构造函数，从而返回一个指向容器末尾的反向迭代器。
reverse_iterator rend(): 这是一个返回反向迭代器的函数，它将 begin() 的迭代器作为参数传递给 reverse_iterator 构造函数，从而返回一个指向容器开始的反向迭代器。
这些函数的目的是为了方便用户在不同情况下遍历容器元素，包括正向遍历和反向遍历，以及使用常量或非常量迭代器。通过这些迭代器，用户可以在 list 容器中轻松访问和操作元素。
2.empty_init()
void empty_init() { _head = new Node; // 创建一个新的节点作为链表头部 _head->_next = _head; // 将头部节点的下一个指针指向自身，表示链表为空 _head->_prev = _head; // 将头部节点的前一个指针也指向自身，表示链表为空 }
这是 list 类中的一个私有成员函数 empty_init()，它用于初始化一个空的链表。
该函数的目的是在创建一个新的空链表时，为头部节点 _head 初始化正确的指针，使得链表为空。链表的头部节点 _head 用来标识链表的起始位置和结束位置。
在这个函数中，首先通过 new 运算符创建一个新的节点作为链表的头部。然后，将头部节点的 _next 指针和 _prev 指针都指向自身，表示链表为空。这种情况下，链表的头部节点既是首节点也是尾节点，形成一个环状的链表结构。
在 list 类的构造函数中，通过调用 empty_init() 来创建一个空链表。这在后续的操作中为链表的插入、删除等操作提供了正确的基础。
3.构造函数定义
template <class InputIterator> list(InputIterator first, InputIterator last) { empty_init(); // 初始化一个空链表 while (first != last) { push_back(*first); // 将当前迭代器指向的元素添加到链表尾部 ++first; // 移动迭代器到下一个元素 } }
list 类的构造函数模板，它接受一个范围内的元素，并将这些元素添加到链表中。
这个构造函数使用了一个模板参数 InputIterator，它表示输入迭代器的类型。这样，构造函数可以接受不同类型的迭代器，例如普通指针、list 的迭代器等。
在构造函数中，首先调用 empty_init() 函数来初始化一个空链表，确保链表头部的 _head 节点正确初始化。
然后，使用一个循环遍历输入迭代器范围内的元素。在每次循环中，通过 push_back() 函数将当前迭代器指向的元素添加到链表的尾部。之后，将迭代器向前移动一个位置，以便处理下一个元素。
list() { empty_init(); // 初始化一个空链表 }
这是 list 类的无参构造函数，它用于创建一个空的链表。
这个构造函数不接受任何参数，它只是在对象创建时将 _head 节点初始化为一个空链表。调用 empty_init() 函数会创建一个只包含 _head 节点的链表，该节点的 _next 和 _prev 都指向自身，表示链表为空。
list(const list<T>& lt) { empty_init(); // 初始化一个空链表 list<T> tmp(lt.begin(), lt.end()); // 使用迭代器从 lt 创建一个临时链表 swap(tmp); // 交换临时链表和当前链表，完成拷贝操作 }
这是 list 类的拷贝构造函数，它用于创建一个新链表，该链表与另一个已存在的链表 lt 相同
在这个构造函数中，首先通过调用 empty_init() 函数初始化了一个空链表，然后创建了一个临时链表 tmp，这个临时链表的元素和链表 lt 中的元素相同，通过迭代器从 lt 范围内创建。接着，通过调用 swap() 函数将当前链表与临时链表 tmp 交换，从而实现了链表的拷贝。
这种方式能够实现拷贝构造的效果，因为在 swap() 函数中，临时链表 tmp 的资源会交给当前链表，而临时链表 tmp 会被销毁，从而实现了链表内容的拷贝。
