C++ list的模拟实现

1. list的模拟实现

带头双向循环链表

带头循环双向链表是一种数据结构，它具有一个哨兵位的头节点，该节点不存储实际数据 。链表中的每个节点都包含两个指针，一个指向前一个节点（ prev ），一个指向后一个节点( next ） 。同时，链表的最后一个节点的 next 指针指向头节点，头节点的 prev 指针指向最后一个节点，形成一个闭环 。

C++标准库中 list 的底层结构，本质就是基于“带头循环双向链表”实现的。具体来说， list 的底层实现完全贴合“带头循环双向链表”的核心特征：

• 1. 以 __list_node 为基础单元：每个存储用户数据的节点，都是 __list_node 模板类的实例，通过 _prev 和 _next 实现双向连接。
• 2. 依赖哨兵位简化操作： list 内部会创建一个哨兵头节点（不存有效数据），让整个链表形成“首尾闭环”——最后一个数据节点的 _next 指向哨兵头，哨兵头的 _prev 指向最后一个数据节点，以此消除边界判断，统一增删查改的逻辑。

链表结点的设计

首先我们实现链表节点的结构，链表节点也是一个模板类：

template<class T>
struct __list_node
{
    __list_node<T>* _next;
    __list_node<T>* _prev;
    T _data;
    __list_node(const T& x = T())//默认构造函数，传参也可以调用
        :_next(nullptr)
        ,_prev(nullptr)
        ,_data(x)
    {}
};

要理解这个 __list_node 结构体，核心是抓住双向链表节点的本质功能——既要存储数据，又要通过指针连接前后节点，同时保证初始化的安全性和通用性。
list（STL中的双向链表）的底层逻辑是“节点串联”，每个节点必须同时满足两个需求：

• 1. 数据存储：保存用户传入的元素（如 int 、 string 或自定义对象）；
• 2. 指针连接：通过前驱/后继指针，将当前节点与前一个、后一个节点关联，形成链表结构。

 __list_node 正是为实现这两个需求设计的“基础组件”，所有 list 的增删查改操作（如插入、删除节点），本质都是对 __list_node 的指针和数据进行操作。

成员变量	类型	核心作用
_next	__list_node<T>*	后继指针：指向下一个节点，实现“向后遍历”（如从节点A找到节点B）；
_prev	__list_node<T>*	前驱指针：指向前一个节点，实现“向前遍历”（如从节点B找到节点A）；
_data	T	数据域：存储用户实际需要的数据（如 T=int 时存整数， T=string 时存字符串）

为什么这么设计？
 
1. 保证指针初始安全
若不主动初始化 _next 和 _prev ，指针会是“野指针”（指向随机内存），后续操作（如赋值指针）会导致内存错误。这里强制初始化为 nullptr ，确保新节点的指针状态是明确的（暂未连接其他节点）。
2. 支持“无参创建节点”
构造函数的参数 x 有默认值 T() ——这是 T 类型的“默认构造值”（如 T=int 时 T() 是0， T=string 时 T() 是空字符串，自定义对象时调用其默认构造）。
这意味着：

• 可以无参创建节点（如 new __list_node<int>() ），此时 _data 会被初始化为 int() （即0）；
• 也可以传参创建节点（如 new __list_node<string>("hello") ），此时 _data 被初始化为“hello”，满足灵活初始化需求。

哨兵节点

哨兵位（Sentinel Node，也叫“哨兵节点”）是 基于 __list_node 创建的特殊节点，它本身不存储有效数据，核心作用是“简化链表的边界操作”，二者是“通用组件”与“特殊用途实例”的关系。
 
本质关系：哨兵位是 __list_node 的“空数据实例”
list 的哨兵位（通常是“头哨兵”，部分实现会加“尾哨兵”），本质就是调用 __list_node 的构造函数创建的一个节点：

// 以“带头哨兵的双向链表”为例，创建哨兵位
__list_node<T>* _head = new __list_node<T>();  // 调用默认构造，_data是T()（空值）

可见：

• 哨兵位的“物理结构”和普通节点完全一致（同样有 _prev 、 _next 、 _data ）；
• 区别仅在“用途”：普通节点的 _data 存用户数据，哨兵位的 _data 无意义（仅用它的指针来统一链表的操作逻辑）。

为什么需要哨兵位？—— 解决普通链表的“边界麻烦”
没有哨兵位时，链表的“头节点”“尾节点”是特殊边界（指针可能为 nullptr ），操作时需要额外判断，代码繁琐易错。哨兵位的存在，能让整个链表变成“逻辑上的循环链表”，消除边界差异，所有节点（包括原头、尾节点）的操作逻辑完全统一。

举个具体例子：实现 push_back （尾插）
1. 无哨兵位的情况（麻烦）
需要判断链表是否为空（尾节点是否为 nullptr ），分两种逻辑：

void push_back(const T& x) {
    __list_node<T>* new_node = new __list_node<T>(x);
    if (_tail == nullptr) {  
    // tail是普通的尾节点
    // 链表为空：新节点既是头也是尾
        _head = new_node;
        _tail = new_node;
    } else {  // 链表非空：连接新节点到尾节点后
        _tail->_next = new_node;
        new_node->_prev = _tail;
        _tail = new_node;
    }
}

2. 有哨兵位的情况（简洁）
哨兵位 _head 的 _prev 永远指向“实际尾节点”_tail （即 _head->_prev ), _tail 的 _next 永远指向 _head ，无需判断空：

void push_back(const T& x) {
    __list_node<T>* new_node = new __list_node<T>(x);
    __list_node<T>* tail = _head->_prev;  // 直接通过哨兵位找到尾节点（无需判断）
    
    // 连接新节点：尾节点 ↔ 新节点 ↔ 哨兵位
    tail->_next = new_node;
    new_node->_prev = tail;
    new_node->_next = _head;
    _head->_prev = new_node;
}

简单说：哨兵位是用 __list_node 造的“工具人”，它的价值不在存数据，而在让链表的增删查改更简单。

list模板底层

list模板类的底层是什么呢？成员变量是什么呢？我们一起来看看：

list的成员变量是头节点，通过上面内容可以知道我们实现的是带头循环双向链表：

template<class T>
class list
{
    typedef __list_node Node;
public:
    list()
    {
        _head = new Node;
        _head->_next = _head;
        _head->prev = _head;
    }
private:
    Node* _head;
};

这段代码展示了C++标准库中 list 模板类底层实现的核心结构，是带头循环双向链表的关键定义list 的底层是带头循环双向链表，通过 __list_node（节点）和哨兵头节点 _head 实现：

• 每个节点（ __list_node ）包含 _prev （前驱指针）、 _next （后继指针）、 _data （数据域），支持双向连接。
• 哨兵头节点 _head 不存储有效数据，仅作为“逻辑锚点”，让链表形成首尾闭环（自己的 _next 和 _prev 都指向自己），从而统一所有操作的边界逻辑。

成员变量解析:
类中唯一的私有成员变量是  Node* _head ，它是哨兵头节点的指针：

• 类型  Node*  是  __list_node<T>*  的别名（通过  typedef __list_node Node;  定义），适配任意数据类型  T 。
• 作用：作为链表的“入口”，通过它可以定位到实际的头节点（ _head->_next ）、尾节点（ _head->_prev ），进而完成所有增删查改操作。

构造函数的核心逻辑:
list()  构造函数负责初始化哨兵头节点：

list()
{
    _head = new Node;       // 创建哨兵头节点（调用__list_node的默认构造）
    _head->_next = _head;   // 哨兵头的后继指针指向自己，形成循环
    _head->prev = _head;    // 哨兵头的前驱指针指向自己，形成循环
}

这一步让新创建的 list 在初始化时，就形成了“自循环”的哨兵结构——此时链表为空，但通过 _head 的双向指针，后续插入、删除节点时无需再判断“空链表”的特殊情况，极大简化了操作逻辑。
总结:
这段代码是 list 底层实现的“骨架”：通过哨兵头节点 _head 和双向循环链表结构，为 list 提供了“任意位置增删效率高、双向遍历灵活”的特性，也是STL中 list 能支持快速插入/删除的核心原因。

list的迭代器怎么实现的呢？list迭代器不仅仅是指针，和vector和string不一样，它的迭代器是用一个类去封装了节点的指针

迭代器的实现方式分析：

1. 原生指针(天然的迭代器)，要求：原生指针指向的空间物理上是连续的，能正确的解引用，以及++，–等操作。比如string和vector
2. 它还是原生指针(比如Node)，但是它指向的物理结构不连续(链表)，但是它不能满足解引用以及++，–等操作，所以需要用一个类去封装原生指针，重载相关运算符，让这个类的对象用起来像指针一样。比如list、map等。

迭代器的本质是：不破坏容器封装的情况，屏蔽底层结构差异，提供统一的方式去访问容器

list迭代器的实现:

template<class T>
struct __list_iterator
{
	typedef __list_node<T> Node;
    typedef __list_iterator<T> self;//为了方便将类类型typedef成self
    Node* _node;//指向节点的指针
    
    __list_iterator(Node* node)
        :_node(node)
    {}
    //*it ->it.operator*()
    //*it = 10//需要可以写，所以返回引用
    T& operator*()
    {
        return _node->data;
    }
    //++it -> it.operator++()
    self& operator++()
    {
        _node = _node->_next;
        return *this;
    }
    //++it -> it.operator++(0)
    self operator++(int)
    {
        __list_iterator<T> tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    
    self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }
    //--it -> it.operator--(0)
    self operator--(int)
    {
        __list_iterator<T> tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    //!=
    bool operator!=(self& it)
    {
        return _node!=it._node;
    }
    bool operator==(self& it)
    {
        return _node==it._node;
    }   
};

要理解这个list迭代器 (__list_iterator) 的设计逻辑，需从迭代器的本质作用和双向链表的遍历特性出发：
设计目的：让链表支持“迭代器风格的遍历与操作”
 
STL迭代器的核心作用是封装底层容器的访问细节，让用户能以统一的“指针式语法”(如 *it 、 ++it ）操作容器元素。对于 list  (双向链表），迭代器需要：

• 支持双向遍历（ ++ 向后、 -- 向前）；
• 支持读写元素（通过 *it 访问数据）；
• 支持比较迭代器是否相等（判断遍历是否结束）。

  __list_iterator 就是为满足这些需求，对“链表节点指针”进行的面向对象封装。

1. 类型别名与成员变量

typedef __list_node<T> Node;
typedef __list_iterator<T> self;
Node* _node;

• Node ：将 __list_node<T> 重命名，简化节点类型的使用，明确迭代器操作的是链表节点。
• self ：将迭代器自身类型重命名，方便在成员函数中返回迭代器对象（如 operator++ 的返回值）。
• _node ：指向 __list_node<T> 的指针，是迭代器的“核心数据”——迭代器的本质就是封装了节点指针的工具，所有操作都基于这个指针展开。

2. 构造函数：初始化迭代器的指向

__list_iterator(Node* node)
    :_node(node)
{}

• 作用：创建迭代器时，需要明确它“指向哪个节点”。例如， list 的 begin() 迭代器会指向“第一个数据节点”（ _head->_next ）， end() 迭代器会指向“哨兵头节点”（ _head ），构造函数就是用来传递这个 node 指针的。

3. 解引用操作符 operator* ：访问节点数据

T& operator*()
{
    return _node->data;
}

• 作用：让迭代器支持“类似指针的解引用”，例如 *it = 10; 可以直接修改节点的 _data 。
• 细节：返回 T& （引用）而非 T ，是为了支持读写操作（如果返回值，只能读不能写）。

4. 前置++与后置++：向后遍历  

// 前置++：++it
self& operator++()
{
    _node = _node->_next;
    return *this;
}

// 后置++：it++
self operator++(int)
{
    __list_iterator<T> tmp(*this); // 先保存旧迭代器
    _node = _node->_next;          // 移动到下一个节点
    return tmp;                    // 返回旧迭代器（符合后置++的语义）
}

• 语义区分：C++通过“是否带 int 参数”区分前置和后置++。前置++返回“移动后的迭代器自身”，后置++返回“移动前的临时迭代器”，完全贴合原生指针的行为（如 int* p; ++p; 和 p++; 的区别）。
• 实现逻辑：本质是让 _node 指针指向下一个节点（ _next ），从而实现“向后遍历”。

5. 前置--与后置--：向前遍历

// 前置--：--it
self& operator--()
{
    _node = _node->_prev;
    return *this;
}

// 后置--：it--
self operator--(int)
{
    __list_iterator<T> tmp(*this); // 保存旧迭代器
    _node = _node->_prev;          // 移动到前一个节点
    return tmp;                    // 返回旧迭代器
}

• 核心逻辑：让 _node 指针指向前一个节点（ _prev ），利用双向链表的特性实现“向前遍历”，这是 list 迭代器区别于 vector 迭代器的关键（ vector 是顺序表，不支持向前遍历）。

6. 比较操作符 == 与 != ：判断迭代器是否相等

bool operator!=(self& it)
{
    return _node != it._node;
}
bool operator==(self& it)
{
    return _node == it._node;
}

• 作用：迭代器的比较本质是“节点指针的比较”——如果两个迭代器的 _node 指向同一个节点，说明它们相等。这是遍历终止的判断依据（如 while (it != list.end()) ）。

 有一个问题？我们要不要写拷贝构造和赋值重载、析构函数

list<int>::iterator it = lt.begin();

答案是不需要，因为默认生成的就可以用，我们不需要深拷贝，上面的那一行的代码本来就需要的是浅拷贝，所以不需要我们去实现，而且节点不属于迭代器，而是属于链表，不需要迭代器去释放 , 这个 __list_iterator 类依赖编译器自动生成的默认拷贝构造、赋值重载和析构函数，且这些默认行为完全满足迭代器的设计需求（迭代器只需要“指向节点”，不需要管理节点内存）。

const对象一般需要const迭代器，例如下面代码：

void print_list(const list<int>& lt)
{
    list<int>::iterator it = lt.begin();
    while(it != lt.end())
    {
        cout<<*it<<" ";
    }
    cout<<endl;
}

这里就不能用了，因为lt是const对象，const对象需要提供const迭代器:

void print_list(const list<int>& lt)
{
    list<int>::const_iterator it = lt.begin();
    while(it != lt.end())
    {
        cout<<*it<<" ";
    }
    cout<<endl;
}

const迭代器的实现

那么我们就重新再写个const迭代器的类：

template<class T>
struct __list_const_iterator
{
	typedef __list_node<T> Node;
    typedef __list_const_iterator<T> self;
    Node* _node;//指向节点的指针
    
    __list_iterator(Node* node)
        :_node(node)
    {}
    //*it ->it.operator*()
    //*it = 10//需要可以写，所以返回引用
    const T& operator*()
    {
        return _node->data;
    }
    //++it -> it.operator++()
    self& operator++()
    {
        _node = _node->_next;
        return *this;
    }
    //++it -> it.operator++(0)
    self operator++(int)
    {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    
    self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }
    //--it -> it.operator--(0)
    self operator--(int)
    {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    //!=
    bool operator!=(const self& it)const
    {
        return _node!=it._node;
    }
    bool operator==(const self& it)const
    {
        return _node==it._node;
    }   
};

const迭代器只需要将*运算符重载的返回值改为const即可，让他不能写，我们发现普通迭代器和const迭代器代码有好多相同的部分，都是微改，那么我们有没有办法可不可以只写一个类模板呢？

答案是可以的，我们可以增加模板参数，Ref(自引用)，Ptr(结构体指针)，为什么添加Ptr我们下面会说：

list迭代器和const迭代器模拟实现

template<class T,class Ref,class Ptr>
struct __list_iterator
{
	typedef __list_node<T> Node;
    typedef __list_iterator<T,Ref,Ptr> self;
    Node* _node;//指向节点的指针
    
    __list_iterator(Node* node)
        :_node(node)
    {}
    //*it ->it.operator*()
    //*it = 10//需要可以写，所以返回引用
    Ref operator*()
    {
        return _node->data;
    }
    //++it -> it.operator++()
    self& operator++()
    {
        _node = _node->_next;
        return *this;
    }
    //++it -> it.operator++(0)
    self operator++(int)
    {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    
    self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }
    //--it -> it.operator--(0)
    self operator--(int)
    {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }
    //!=
    bool operator!=(const self& it)const
    {
        return _node!=it._node;
    }
    bool operator==(const self& it)const
    {
        return _node==it._node;
    }   
};
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;
    iterator begin()
    {
        return iterator(_head->next);
    }
    iterator e()
    {
        return iterator(_head->prev);
    }
    const_iterator begin()const
    {
        return const_iterator(_head->next);
    }
    const_iterator end()const
    {
        return const_iterator(_head);
    }
    list()
    {
        _head = new Node;
        _head->_next = _head;
        _head->prev = _head;
    }
private:
    Node* _head;
};

这段代码是对 list 容器和迭代器的完善实现，核心优化是通过迭代器的模板参数泛化，同时支持“普通迭代器”和“const迭代器”，解决了“只读访问容器”的需求。
 
设计核心：用迭代器模板参数区分“读写权限”

• 普通迭代器（ iterator ）需要支持读写元素（如 *it = 10 ）
• const迭代器（ const_iterator ）需要支持只读元素（如 cout << *it ，不能修改）。

这段代码的关键设计是：给 __list_iterator 增加 Ref （引用类型）和 Ptr （指针类型）两个模板参数，通过不同参数实例化，实现“一套迭代器代码，适配两种访问权限”，避免重复编写代码。

代码分析:
1. 迭代器类 __list_iterator ：模板参数泛化访问权限

template<class T, class Ref, class Ptr>
struct __list_iterator
{
    typedef __list_node<T> Node;
    typedef __list_iterator<T, Ref, Ptr> self; // 迭代器自身类型（带权限参数）
    Node* _node; // 核心：指向链表节点的指针

    // 1. 构造函数：初始化迭代器指向的节点
    __list_iterator(Node* node) : _node(node) {}

    // 2. 解引用运算符：通过Ref控制读写权限
    Ref operator*() { return _node->data; }
    // - 若Ref是T&（普通引用）：*it返回可修改的引用（支持读写）；
    // - 若Ref是const T&（const引用）：*it返回只读引用（禁止修改）。

    // 3. 双向遍历运算符：++/--（逻辑和之前一致，不涉及权限）
    self& operator++() { _node = _node->_next; return *this; } // 前置++
    self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } // 后置++
    self& operator--() { _node = _node->_prev; return *this; } // 前置--
    self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } // 后置--

    // 4. 比较运算符：增加const修饰，支持const迭代器的比较
    bool operator!=(const self& it) const { return _node != it._node; }
    bool operator==(const self& it) const { return _node == it._node; }
};

在这个迭代器模板中， Ref  和  Ptr  是 用来泛化“元素的引用类型”和“元素的指针类型”的模板参数，核心目的是通过不同的参数实例化，让一套迭代器代码同时支持“普通读写访问”和“const只读访问”，具体含义和作用如下：
 
1. Ref：Reference（元素的引用类型）

• 字面含义： Ref  是“Reference”的缩写，代表迭代器解引用（ *it ）后返回的元素引用类型。
• 核心作用：控制迭代器是否能修改元素——通过传递不同的引用类型，实现“读写”或“只读”的权限控制。
• 两种关键实例化场景：
• 当迭代器是普通迭代器（iterator） 时： Ref  被指定为  T& （普通引用）。此时  *it  返回  T& ，支持通过迭代器修改元素（如  *it = 10; ）。
• 当迭代器是const迭代器（const_iterator） 时： Ref  被指定为  const T& （const引用）。此时  *it  返回  const T& ，只能读取元素，禁止修改（如  cout << *it;  合法， *it = 10;  编译报错）。

2. Ptr：Pointer（元素的指针类型）

• 字面含义： Ptr  是“Pointer”的缩写，代表迭代器通过箭头运算符（ it-> ）访问元素成员时，返回的元素指针类型（当前代码未显式使用，但为后续扩展预留）。
• 核心作用：和  Ref  对应，控制通过指针访问元素成员时的权限，确保“const迭代器”无法通过指针修改成员。
• 两种关键实例化场景：
• 当迭代器是普通迭代器（iterator） 时： Ptr  被指定为  T* （普通指针）。
• 若元素是自定义结构体/类（如  struct Person { int age; }; ），则  it->age  等价于  (*it).age ，支持修改成员（如  it->age = 20; ）。
• 当迭代器是const迭代器（const_iterator） 时： Ptr  被指定为  const T* （const指针）。此时  it->age  只能读取成员值（如  cout << it->age; ），禁止修改（ it->age = 20;  编译报错）。

总结：Ref和Ptr的本质是“权限控制的模板参数”
二者的核心价值是 “一套迭代器代码，适配两种访问权限”：

• 通过  Ref  控制“解引用（ *it ）的读写权限”；
• 通过  Ptr  控制“箭头访问（ it-> ）的读写权限”；
• 无需为普通迭代器和const迭代器写两套重复代码，仅通过不同的  Ref / Ptr  参数实例化即可，既简洁又符合STL设计规范。

2. list类：实例化两种迭代器，定义begin/end接口

template<class T>
class list
{
    typedef __list_node<T> Node;
public:
    // 1. 定义两种迭代器类型：通过不同Ref/Ptr参数实例化
    typedef __list_iterator<T, T&, T*> iterator; // 普通迭代器：Ref=T&（读写），Ptr=T*
    typedef __list_iterator<T, const T&, const T*> const_iterator; // const迭代器：Ref=const T&（只读），Ptr=const T*

    // 2. 普通迭代器的begin/end（适配非const list对象）
    iterator begin() { return iterator(_head->_next); } // begin指向第一个数据节点（_head->_next）
    iterator end() { return iterator(_head); } // end指向哨兵头节点（遍历终止标志）
    // （注：原代码中“iterator e()”应为笔误，标准end()指向哨兵头节点）

    // 3. const迭代器的begin/end（适配const list对象，如const list<int> lst）
    const_iterator begin() const { return const_iterator(_head->_next); }
    const_iterator end() const { return const_iterator(_head); }

    // 4. 构造函数：初始化哨兵头节点（自循环）
    list() {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head; // 原代码“prev”漏了下划线，修正为_head->_prev
    }

private:
    Node* _head; // list的核心：哨兵头节点指针
};

为什么要这样设计？
1. 解决“const迭代器”的只读需求
当 list 是 const 对象时（如 const list<int> lst ），不能通过迭代器修改元素，此时需要 const_iterator ：

• 调用 lst.begin() 时，会返回 const_iterator ，其 operator*() 返回 const int& ，禁止 *it = 10 这类修改操作；
• 普通 list<int> lst 调用 begin() ，返回 iterator ， operator*() 返回 int& ，支持修改。

2. 避免代码冗余
若不使用 Ref / Ptr 泛化，需要单独写 __list_const_iterator 类（逻辑和普通迭代器几乎一致，仅权限不同），会导致大量重复代码。通过模板参数复用一套迭代器代码，更简洁高效。
3. 符合STL接口规范
STL中 list 的 begin() / end() 需同时支持普通和const版本，这段代码的接口设计（如 const_iterator begin() const ）完全对齐STL标准，确保用户能以熟悉的方式使用（如遍历const list）。
总结:
这段代码的核心是“用迭代器模板参数泛化访问权限”：

1. 迭代器通过 Ref 控制解引用的读写（T&/const T&），通过 Ptr （当前代码未用，后续可扩展 -> 运算符）控制指针访问权限；
2. list类通过实例化两种迭代器，提供普通/const版本的 begin() / end() ，适配不同场景下的链表访问，同时符合STL设计规范。

我们继续分析 , 可以看到我们进行了显式实例化：

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
iterator it;

是iterator就传T, T&, T*去实例化对象，是const_iterator就传T, const T&, const T*去实例化对象。

那么为什么要有T*呢？

我们看下面一段代码:

struct TreeNode
{
    struct TreeNode* _left;
    struct TreeNode* _right;
    int _val;
    TreeNode(int val)
        :_left(nullptr)
        ,_right(nullptr)
        ,_val(val)
        {}
};

void test_list2()
{
    list<TreeNode> lt;
    lt.push_back(TreeNode(1));
    lt.push_back(TreeNode(2));
    lt.push_back(TreeNode(3));
    lt.push_back(TreeNode(4));
    list<TreeNode>::iterator it = lt.begin();//it现在指向的是结构体
    while(it != lt.end())
    {
        cout<<*it<<" ";
        ++it;
    }
    cout<<endl;
}

这里编译不过：

为什么会报错呢？我们分析一下，TreeNode是一个自定义类型，相当于这里的T：

typedef __list_iterator<T, T&, T*> iterator;

将TreeNode传过去，T为TreeNode，我们解引用it时，这里返回的是TreeNode，返回的是一个结构体对象，那么我们当然不能对它解引用了打印了，除非我们在TreeNode里面实现<<运算符重载

ostream operator<<(ostream& out,TreeNode n);

不实现这个重载我们只能这样访问：

cout<<(*it)._val<<" ";

那么我们能不能这样访问呢？

cout<<it->_val<<" ";

现在还不可以，it是一个结构体(迭代器)对象，不能够支持这样，对于内置类型的指针：int* p，我们取数据用*p，对应自定义类型指针TreeNode* p ，我们取数据用p->_val

所以我们需要给迭代器重载->运算符：

Ptr operator->()
{
    return &_node->_data;//这里的_data相当于是TreeNode，
}

下面我们测试一下：

void test_list2()
{
    list<TreeNode> lt;
    lt.push_back(TreeNode(1));
    lt.push_back(TreeNode(2));
    lt.push_back(TreeNode(3));
    lt.push_back(TreeNode(4));
    list<TreeNode>::iterator it = lt.begin();//it现在指向的是结构体
    while(it != lt.end())
    {
        
        //cout<<(*it)._val<<" ";
        //假设打印这三个
        //printf("val:%d,left:%p,right:%p\n",(*it)._val,(*it)._left,(*it)._right);
        printf("val:%d,left:%p,right:%p\n",it->_val,it->_left,it->_right);
       	
        ++it;
    }
    cout<<endl;
}

it->本质上是这样调用的it.operator->()，它返回一个结构体指针。本来这个调用应该是it->->_val，但是这里这样写，可读性太差了，所以编译器进行了特殊处理，省略了一个->，保持程序的可读性

vector迭代器和list迭代器比较

list迭代器：

typedef __list_iterator<T,T&,T*> iterator;

vector迭代器：

typedef T* iterator;

在逻辑上感觉list比vector更复杂，但在物理上它们并没有什么区别。

vector迭代器是原生指针，它的大小为4个字节，那么list迭代器呢？

list迭代器也是4个字节，因为它是一个自定义类型，他只有一个成员是指针，所以他也是4个字节，C++的类，运算符重载的能力让我们在用的角度我们感觉并没有什么区别

push_back模拟实现

void push_back(const T& x)
{
	Node* tail = _head->_prev;
	Node* newnode = new Node(x);

	newnode->_next = _head;
	newnode->_prev = tail;
	tail->_next = newnode;
	_head->_prev = newnode;
}

这段代码是双向循环链表的 push_back （尾插）函数实现，功能是在链表末尾插入一个值为 x 的新节点。
 
代码逻辑:

• 1. 定位尾节点： _head 是链表的哨兵头节点（不存储实际数据），其前驱指针 _prev 指向链表的最后一个有效节点，用 tail 接收该尾节点。
• 2. 创建新节点：通过 new Node(x) 动态创建一个存储值 x 的新节点 newnode 。
• 3. 建立新节点的前后链接：
• - 新节点的后继（ _next ）指向哨兵头节点 _head （维持“循环”特性）；
• - 新节点的前驱（ _prev ）指向原尾节点 tail 。
• 4. 更新原尾节点和哨兵头节点的链接：
• - 原尾节点 tail 的后继指向新节点 newnode ；
• - 哨兵头节点 _head 的前驱指向新节点 newnode ，完成尾插。

关键前提:

1. 链表结构为双向循环链表，且包含一个 _head 哨兵节点（用于简化边界操作，无需处理 nullptr ）。
2. Node 类/结构体需包含三个成员：存储数据的 T 类型成员、指向后继节点的 _next 指针、指向前驱节点的 _prev 指针。

我们在VS中来验证一下:

push_front模拟实现

void push_front(const T& x)
{
    Node* next = _head->_next;
    Node* newnode = new Node(x);
    
    newnode->_next = next;
    newnode->_prev = _head;
    _head->_next = newnode;
    next->_prev = newnode;
}

这段代码是双向循环链表的 push_front （头插）函数实现，功能是在链表的哨兵头节点 _head 之后，插入一个值为 x 的新节点（即链表的第一个有效位置）。

代码逻辑:

• 1. 定位原首节点： _head 是哨兵头节点（不存实际数据），其前驱指针 _next 指向链表的第一个有效节点，用 next 接收该节点。
• 2. 创建新节点：通过 new Node(x) 动态创建存储值 x 的新节点 newnode 。
• 3. 建立新节点的前后链接：
• - 新节点的后继（ _next ）指向原首节点 next ；
• - 新节点的前驱（ _prev ）指向哨兵头节点 _head 。
• 4. 更新哨兵头节点和原首节点的链接：
• - 哨兵头节点 _head 的后继指向新节点 newnode ；
• - 原首节点 next 的前驱指向新节点 newnode ，完成头插。

关键前提（与 push_back 一致）:

1. 链表为双向循环链表，依赖 _head 哨兵节点简化操作（无需处理空链表时的 nullptr 边界）。
2. Node 类/结构体需包含三个成员： T 类型的数据成员、指向后继的 _next 指针、指向前驱的 _prev 指针。

可以看到成功头插了

insert模拟实现

iterator insert(iterator pos, const T& x)
{
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* newnode = new Node(x);
    
    newnode->_next = cur;
    cur->_prev = newnode;
    prev->_next = newnode;
    newnode->_prev = prev;
    
    return iterator(newnode);
}

这段代码是双向循环链表迭代器版本的 insert 函数实现，功能是在迭代器 pos 指向的节点之前，插入一个值为 x 的新节点，并返回指向这个新节点的迭代器。
代码逻辑:

• 1. 获取关键节点指针：
• - 通过迭代器 pos 的内部成员 _node ，获取其指向的目标节点 cur （新节点将插入到 cur 之前）；
• - 找到 cur 的前驱节点 prev （即 cur->_prev ）。
• 2. 创建新节点：通过 new Node(x) 动态创建存储值 x 的新节点 newnode 。
• 3. 建立新节点与前后节点的链接：
• - 新节点的后继（ _next ）指向目标节点 cur ；
• - 目标节点 cur 的前驱指向新节点 newnode ；
• - 新节点的前驱（ _prev ）指向 cur 的原前驱 prev ；
• -  prev 的后继指向新节点 newnode ，完成插入。
• 4. 返回新节点的迭代器：将新节点 newnode 封装成迭代器并返回，方便后续操作新插入的节点。

关键前提:

1. 链表仍为双向循环链表，依赖 _head 哨兵节点（虽代码未直接显式使用，但迭代器 pos 的合法性隐含了链表结构）。
2. 迭代器 iterator 类需包含内部成员 _node （指向链表的 Node 节点），且支持通过 Node 指针构造迭代器（即 iterator(newnode) 合法）。
3. -Node 结构体/类需包含 T 类型数据成员、 _next （后继指针）和 _prev （前驱指针）。

erase模拟实现

//类模板中的成员函数是按需实例化，调用了哪个成员函数，实例化哪一个
//成员函数是函数模板
iterator erase(iterator pos)
{
    assert(pos != end())
    Node* cur = pos._node;
    Node* prev = cur->_prev;
    Node* next = cur->_next;
    
    prev->_next = next;
    next->_prev = prev;
    delete cur;
    return iterator(next);
}

这段代码是双向循环链表迭代器版本的 erase 函数实现，功能是删除迭代器 pos 指向的节点，并返回指向被删除节点下一个节点的迭代器（避免迭代器失效）。
代码逻辑:

• 1. 合法性校验：通过 assert(pos != end()) 确保待删除的迭代器 pos 不是链表的尾后迭代器（ end() 通常指向哨兵头节点 _head ，不对应有效节点，禁止删除）。
• 2. 获取关键节点指针：
• - 从迭代器 pos 的内部成员 _node ，获取待删除节点的指针 cur ；
• - 找到 cur 的前驱节点 prev （ cur->_prev ）和后继节点 next （ cur->_next ）。
• 3. 断开待删除节点的链接：
• - 让 prev 的后继（ _next ）直接指向 next ；
• - 让 next 的前驱（ _prev ）直接指向 prev ，此时 cur 节点脱离链表。
• 4. 释放内存并返回新迭代器：
• - 通过 delete cur 释放被删除节点的内存，避免内存泄漏；
• - 返回封装了 next 节点的迭代器（ iterator(next) ），该迭代器指向被删节点的下一个位置，可继续用于后续遍历。

关键前提:

1. 链表为双向循环链表， end() 迭代器指向哨兵头节点 _head （因此 pos != end() 是为了排除删除哨兵节点的非法操作）。
2. 迭代器 iterator 类需包含内部成员 _node （指向 Node 节点），且支持通过 Node 指针构造迭代器。
3. Node 结构体/类需包含 T 类型数据成员、 _next （后继指针）和 _prev （前驱指针）。

重要注意事项:

1. 迭代器失效问题：被删除的迭代器 pos 会直接失效（其指向的 cur 节点已被释放），后续不可再使用 pos ，必须使用函数返回的新迭代器（指向 next ）继续操作。

pop_back模拟实现

void pop_back()
{
    erase(--end());       
} 

这段代码是双向循环链表的 pop_back （尾删）函数实现，功能是删除链表的最后一个有效节点，核心是通过复用已实现的 erase 函数来简化逻辑。
代码逻辑:

• 1. 定位尾节点的迭代器：
•   end() ：通常指向链表的哨兵头节点 _head （尾后迭代器，不对应有效数据）；
•   --end() ：对尾后迭代器 end() 进行自减操作，会得到指向链表最后一个有效节点的迭代器（因为链表是循环的， _head 的前驱就是尾节点）。
• 2. 调用 erase 删除：将指向尾节点的迭代器传入 erase 函数，由 erase 完成节点删除、内存释放，并返回下一个节点的迭代器（此处无需接收返回值，仅需删除动作）。

关键前提:

1. 依赖 end() 的正确实现： end() 必须返回指向哨兵头节点 _head 的迭代器，才能通过 --end() 定位到尾节点。
2. 依赖 erase 函数的正确性： erase 需能正确删除迭代器指向的有效节点，并处理节点间的指针链接与内存释放（如之前实现的 erase 逻辑）。
3. 链表非空：若链表为空（无有效节点）， --end() 会指向 _head ，调用 erase 时会触发 assert(pos != end()) 断言失败，因此实际使用前需确保链表非空（或在 pop_back 中增加空判断）。

pop_front模拟实现

void pop_front()
{
    erase(begin());
}

这段代码是双向循环链表的 pop_back （尾删）函数实现，功能是删除链表的最后一个有效节点，核心是通过复用已实现的 erase 函数来简化逻辑。
代码逻辑:

• 1. 定位尾节点的迭代器：
•   end() ：通常指向链表的哨兵头节点 _head （尾后迭代器，不对应有效数据）；
•   --end() ：对尾后迭代器 end() 进行自减操作，会得到指向链表最后一个有效节点的迭代器（因为链表是循环的， _head 的前驱就是尾节点）。
• 2. 调用 erase 删除：将指向尾节点的迭代器传入 erase 函数，由 erase 完成节点删除、内存释放，并返回下一个节点的迭代器（此处无需接收返回值，仅需删除动作）。

关键前提:

1. 依赖 end() 的正确实现： end() 必须返回指向哨兵头节点 _head 的迭代器，才能通过 --end() 定位到尾节点。
2. 依赖 erase 函数的正确性： erase 需能正确删除迭代器指向的有效节点，并处理节点间的指针链接与内存释放（如之前实现的 erase 逻辑）。
3. 链表非空：若链表为空（无有效节点）， --end() 会指向 _head ，调用 erase 时会触发 assert(pos != end()) 断言失败，因此实际使用前需确保链表非空（或在 pop_back 中增加空判断）。

size模拟实现

size_t size()
{
    size_t n=0;
    iterator it = begin();
    while(it!=end())
    {
        it++;
        n++;
    }
    return n;
}

这段代码是双向循环链表的 size 函数实现，功能是遍历链表并统计有效节点的总数，最终返回链表的长度（元素个数）。
代码逻辑:

• 1. 初始化计数与迭代器：
• - 定义 size_t 类型变量 n 并初始化为 0 ，用于累计有效节点的数量；
• - 定义迭代器 it ，通过 begin() 获取指向链表第一个有效节点的迭代器（常规实现中， begin() 对应 _head->_next ）。
• 2. 遍历链表计数：通过 while 循环遍历链表，循环条件为 it != end() （ end() 指向哨兵头节点 _head ，是遍历的终止标志）：
• - 每次循环中，迭代器 it 向后移动一位（ it++ ，本质是让 it 指向当前节点的后继 _next ）；
• - 同时计数变量 n 自增 1 ，记录当前遍历到的有效节点。
• 3. 返回计数结果：循环结束后， n 的值即为链表中有效节点的总数，返回 n 。

关键前提:

1. 依赖 begin() 和 end() 的正确实现：
2. begin() 需返回指向第一个有效节点的迭代器；
3. end() 需返回指向哨兵头节点 _head  的尾后迭代器（作为遍历终止条件）。
4. 迭代器支持 ++ 运算符： it++ 需能正确实现“向后移动一位”的逻辑（即内部将 _node 指向当前节点的 _next ）。

注意事项:

1. 时间复杂度：该实现的时间复杂度为 O(N) （ N 为链表长度），因为需要遍历所有有效节点才能完成计数。若需频繁调用 size ，可优化为在链表类中增加 _size 成员变量（插入/删除时同步更新），使 size 函数的时间复杂度降为 O(1) 。
2. 空链表兼容性：若链表为空（无有效节点）， begin() 会等于 end() （均指向 _head ），循环直接不执行， n 保持为 0 ，返回结果正确。

empty模拟实现

bool empty()
{
    return begin()==end();
    //如果begin等于end就是链表为空的时候
}

这段代码是双向循环链表的 empty 函数实现，功能是判断链表是否为空，核心逻辑是通过比较 begin() 和 end() 迭代器是否相等来得出结果。
代码逻辑:

• begin() 的含义：按链表常规实现， begin() 返回指向第一个有效节点的迭代器（即 _head->_next 对应的迭代器）。
• end() 的含义： end() 返回指向哨兵头节点 _head  的尾后迭代器（不对应任何有效数据，仅作为遍历/判断的终止标志）。
• - 判断逻辑：
• 当链表为空时：没有任何有效节点， _head->_next 直接指向 _head 本身，因此 begin() （指向 _head->_next ）和 end() （指向 _head ）的迭代器相等，返回 true 。
• 当链表非空时： _head->_next 指向第一个有效节点（而非 _head ），因此 begin() 和 end() 的迭代器不相等，返回 false 。

关键前提:

1. 必须依赖 begin() 和 end() 的正确实现： begin() 需指向首个有效节点， end() 需指向哨兵头节点 _head ，否则判断逻辑会失效。
2. 链表结构为双向循环链表且包含 _head 哨兵节点：这是 begin() 与 end() 能通过“是否相等”判断空链表的基础（无哨兵节点的链表无法用此逻辑）。

clear模拟实现

void clear()
{
    iterator it = begin();
    while(it!=end())
    {
        Node* del = it->_node;
        ++it;
        delete del;
    }
    _head->_next = _head;
}

这段代码是双向循环链表的 clear 函数实现，功能是删除链表中所有有效节点（释放内存），使链表恢复为空状态（仅保留哨兵头节点 _head ）。
代码逻辑:

• 1. 初始化迭代器：定义迭代器 it ，通过 begin() 获取指向链表第一个有效节点的迭代器，开始遍历所有有效节点。
• 2. 遍历并删除所有有效节点：通过 while(it != end()) 循环遍历（ end() 指向哨兵头节点，作为遍历终止标志）：
• - 先用 Node* del = it->_node 获取当前迭代器 it 指向的节点指针（记录待删除节点，避免后续 it 移动后丢失地址）；
• - 迭代器 it 先向后移动一位（ ++it ，指向当前节点的下一个有效节点）；
• - 通过 delete del 释放刚才记录的待删除节点内存，避免内存泄漏。
• 3. 重置哨兵头节点链接：所有有效节点删除后，将哨兵头节点 _head 的后继指针（ _head->_next ，注意代码中 -_next 应为笔误，正确是 ->_next ）指向自身，使链表恢复为“空链表”的循环状态（ _head->_next = _head 且 _head->_prev = _head ）。

关键前提:

1. 链表为双向循环链表，包含哨兵头节点 _head （ clear 不删除 _head ，仅删除有效节点）。
2. 迭代器 it 支持 ++ 运算符（能正确指向当前节点的后继 _next ），且内部包含 _node 成员（可获取指向 Node 的指针）。

:注意事项

1. 完整空链表状态：若要完全恢复空链表，除了设置 _head->_next = _head ，还需同步设置 _head->_prev = _head （确保 _head 的前驱也指向自身，维持循环特性），否则后续操作可能出现异常。
2. 迭代器操作顺序：必须先移动迭代器（ ++it ）再删除节点（ delete del ），若先删除节点， it 的 _node 会变成野指针，后续 ++it 会导致非法访问。

也可以直接复用：

void clear()
{
    iterator it = begin();
    while(it!=end())
    {
        it = erase(it);
    }
}

erase会帮我们链接好最后删除完后仅剩的头节点

析构函数模拟实现

~list()
{
    clear();
    delete _head;
    _head = nullptr;
}

这段代码是双向循环链表类的析构函数实现，功能是在链表对象生命周期结束时，彻底释放链表占用的所有内存（包括所有有效节点和哨兵头节点 _head ），避免内存泄漏。
代码逻辑:

• 1. 释放所有有效节点：调用之前实现的 clear() 函数，该函数会遍历并 delete 链表中所有有效节点（仅保留哨兵头节点 _head ），确保有效节点的内存被释放。
• 2. 释放哨兵头节点：通过 delete _head 释放哨兵头节点 _head 的内存（ clear() 未删除 _head ，此处需单独处理）。
• 3. 避免野指针：将 _head 指针赋值为 nullptr ，防止后续误访问已释放的内存（野指针），提升代码安全性。

关键前提:

1. 依赖 clear() 函数的正确性： clear() 需能完整删除所有有效节点（且不删除 _head ），否则会导致有效节点内存泄漏。
2. _head 是动态分配的： _head 必须是通过 new 动态创建的节点（如链表构造函数中 _head = new Node() ），才能通过 delete _head 合法释放，若 _head 是栈上节点则会触发错误。

作用与意义:

• 析构函数是“资源清理的最后一道防线”：当链表对象（如局部变量出作用域、动态对象被 delete ）销毁时，该析构函数会自动执行，确保链表占用的所有动态内存（有效节点+ _head ）被彻底释放，避免程序运行过程中累积内存泄漏。

拷贝构造模拟实现

void test_list4()
{
    list<int> lt;
    lt.push_back(1);
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    list<int> lt1(lt);
}

这段代码是双向循环链表类（list）的拷贝构造测试函数，功能是创建一个链表 lt 并插入数据，再通过拷贝构造创建新链表 lt1 （ lt1 是 lt 的副本），核心用于验证拷贝构造功能是否正常。

关键注意事项（潜在问题）:
若 list 类未显式实现深拷贝构造函数，仅依赖编译器生成的默认拷贝构造（浅拷贝），会导致严重错误：

1. 浅拷贝仅复制 _head 指针的值，使 lt 和 lt1 的 _head 指向同一块哨兵头节点内存。
2. 后续操作（如 lt 或 lt1 调用 clear() 、析构函数）时，会对同一批节点（包括 _head ）进行多次 delete ，触发双重释放（double free） ，导致程序崩溃或内存错误。
3. 因此，要使该测试代码正常运行， list 类必须显式实现深拷贝构造函数：遍历原链表（ lt ）的所有有效节点，为新链表（ lt1 ）动态创建独立的节点（复制数据），并构建独立的双向循环结构。

同样的list也有拷贝构造函数：

拷贝构造传统写法

//lt2(lt1)
list(const list<T>& lt)
{
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    for(const auto& e:lt)
    {
        push_back(e);
    }
}

这段代码是双向循环链表类的深拷贝构造函数实现，能正确完成从源链表 lt 到新链表的独立拷贝（数据和节点内存均不共享），解决了默认浅拷贝的“双重释放”问题，逻辑正确且简洁。

代码逻辑:

• 1. 初始化新链表的哨兵头节点：
• - 为新链表动态创建独立的哨兵头节点 _head （ new Node ）；
• - 将 _head 的 _next 和 _prev 都指向自身（ _head->_next = _head; _head->_prev = _head ），使新链表初始化为空的双向循环结构。
• 2. 深拷贝源链表数据：
• - 通过范围for循环（ for(const auto& e:lt) ）遍历源链表 lt 的所有有效节点（依赖 list 类已正确实现迭代器，范围for本质是通过 begin() 和 end() 迭代）；
• - 对遍历到的每个元素 e ，调用已实现的 push_back(e) 接口，为新链表动态创建独立的节点并插入尾部，最终实现源链表数据的完整复制（新节点与源节点内存独立）。

为什么该实现正确？（解决的核心问题）

1. 彻底的深拷贝：新链表的 _head 是独立 new 的，所有有效节点也是通过 push_back 内部 new 创建的，与源链表 lt 的节点内存完全分离，不存在“共享节点”的问题。
2. 避免双重释放：由于新、源链表的节点内存独立，后续两者调用 clear() 或析构函数时，会各自释放自己的节点，不会出现“同一内存被多次 delete ”的崩溃问题。
3. 复用已有接口：直接复用 push_back 完成节点插入，无需重复编写节点链接逻辑，减少代码冗余且保证一致性。

关键前提:

1. 源链表 lt 的迭代器需正确实现：范围for循环依赖 lt 的 begin() （指向首个有效节点）和 end() （指向哨兵头节点），以及迭代器的 ++ 和 != 运算符，确保能遍历所有有效数据。
2. push_back 函数需正确实现：能正常创建新节点、建立双向循环链接，确保拷贝的数据能正确插入新链表。

拷贝构造现代写法

//lt2(lt1)
template<class InputIterator,class InputIterator>
list(InputIterator first,InputIterator last)
{
    _head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    while(first!=last)
    {
        push_back(*first);
        ++first;
    }
}
list(const list<T>& lt)
{
    this->_head = new Node;//这里需要给lt2头节点，不然lt2的_head指向的空间都没有创建，_head是空指针，swap会出问题
    _head->_next = _head;
    _head->_prev = _head;
    
    list<T> tmp(lt.begin(),lt.end());
    std::swap(_head,tmp._head);//tmp函数调用结束会销毁
    //这里不能这样交换：
    //swap(lt,tmp);
    //因为swap的底层实现用到了拷贝构造函数，我们正在写的就是拷贝构造函数，这里就会出问题
}

这段代码包含双向循环链表的两个构造函数实现：一个是“迭代器区间构造函数”（从指定迭代器范围拷贝数据），另一个是“拷贝构造函数”（通过复用迭代器区间构造+指针交换，实现安全深拷贝），逻辑严谨且避免了代码冗余和递归问题。
 
1. 迭代器区间构造函数（ list(InputIterator first, InputIterator last) ）
 
功能 : 接收一个迭代器范围  [first, last) ，构造一个新链表，将该范围中的所有元素依次插入新链表尾部。
核心逻辑:

• 1. 初始化哨兵头节点：
• - 动态创建新链表的哨兵头节点  _head ；
• - 设  _head->_next = _head  且  _head->_prev = _head ，使新链表初始为空的双向循环结构。
• 2. 遍历迭代器范围并插入元素：
• - 循环条件  first != last ：遍历  [first, last)  区间内的所有元素；
• -  push_back(*first) ：取迭代器  first  指向的元素值，通过  push_back  插入新链表尾部（ push_back  内部会创建新节点，实现深拷贝）；
• -  ++first ：迭代器向后移动，继续遍历下一个元素，直至区间结束。

关键作用:
作为“通用数据导入接口”，既支持拷贝其他  list  对象的迭代器范围，也支持拷贝  vector 、 array  等其他容器的迭代器范围（只要迭代器支持  != 、 ++ 、 *  操作）。
 
2. 拷贝构造函数（ list(const list<T>& lt) ）
 
功能 : 创建一个新链表，作为源链表  lt  的深拷贝副本（新链表与源链表节点内存完全独立，避免浅拷贝的“双重释放”问题）。
 
核心逻辑拆解（巧妙复用+避免问题）

• 1. 初始化新链表的哨兵头节点：
• - 先为新链表（ this ）创建独立的哨兵头节点  _head  并初始化（ _head->_next = _head->_prev = _head ）；
• - 这一步是关键：若不先创建  _head ，新链表的  _head  是野指针，后续  swap  会导致非法访问。
• 2. 用迭代器区间构造临时链表  tmp ：
• - 调用上面的“迭代器区间构造函数”，创建临时链表  tmp ；
• - 传入的范围是  lt.begin() （源链表首个有效节点）和  lt.end() （源链表哨兵头节点），使  tmp  成为  lt  的完整深拷贝副本（ tmp  的节点内存与  lt  完全独立）。
• 3. 交换  this  与  tmp  的  _head  指针：
• - 通过  std::swap(_head, tmp._head) ，将  this  的  _head （空哨兵头节点）与  tmp  的  _head （包含完整深拷贝数据的链表头）交换；
• - 交换后， this  拥有了  tmp  的完整链表结构（即  lt  的深拷贝），而  tmp  拥有了原  this  的空哨兵头节点。
• 4. 临时链表  tmp  自动销毁，避免内存泄漏：
• - 函数结束时， tmp  出作用域，会调用析构函数；
• -  tmp  的  _head  此时指向原  this  的空哨兵头节点，析构时会释放该空哨兵头节点（无有效节点，仅释放  _head ），不会影响  this  的有效数据，完美避免内存泄漏。

关键设计：为什么不直接  swap(lt, tmp) ？

1. 若调用  swap(lt, tmp) （假设是自定义的链表  swap  函数），其底层通常会交换两个链表的  _head  指针；
2. 但  swap  函数的参数若为  list<T>&  类型，调用时可能会触发“隐式拷贝”（若参数传递或内部实现依赖拷贝构造），而当前正在实现拷贝构造函数，会导致“递归调用拷贝构造”，最终栈溢出崩溃。
3. 因此直接交换  _head  指针（仅交换一个指针变量，不涉及链表整体操作），避免了递归风险，且高效（时间复杂度  O(1) ）。

两个构造函数的核心关联:

• 拷贝构造函数复用了迭代器区间构造函数的逻辑，无需重复编写“遍历源链表、创建新节点、链接节点”的代码，既减少冗余，又保证了逻辑一致性（避免两处实现出现差异），是代码设计的“复用思想”体现。

operator=模拟实现

赋值重载传统写法

//lt1 = lt4 传统写法
list<T>& operator=(const list<T>& lt)
{
    if(this!=&lt)
    {
        clear();
        for(const auto& e:lt)
        {
            push_back(e);
        }
    }
}

这段代码是双向循环链表赋值运算符重载的传统实现，功能是将源链表 lt 的内容深拷贝到当前链表（ this ），实现“ lt1 = lt4 ”这类赋值操作，且能避免自我赋值和内存泄漏。
代码逻辑:

• 1. 自我赋值检查：
• 通过 if(this != &lt) 判断当前对象（ this ）是否与源对象（ lt ）是同一个（即避免 lt1 = lt1 这类自我赋值）。
• - 若不检查，后续 clear() 会先删除当前链表的节点，导致源链表（因自我赋值时指向同一块内存）的节点也被释放，后续拷贝会访问野指针，引发错误。
• 2. 清空当前链表：
• 调用 clear() 函数，删除当前链表（ this ）中所有有效节点（释放内存），仅保留哨兵头节点 _head ，为接收源链表数据腾出空间。
• 3. 深拷贝源链表数据：
• 通过范围for循环（ for(const auto& e:lt) ）遍历源链表 lt 的所有有效节点（依赖 lt 的迭代器正确实现），对每个元素 e ，调用 push_back(e) 将其插入当前链表尾部。
• -  push_back 内部会动态创建新节点存储 e ，实现“深拷贝”——当前链表的节点与源链表 lt 的节点内存完全独立，后续修改互不影响。
• 4. 返回当前对象引用：
• 函数返回 list<T>& 类型（代码中遗漏了 return *this; ，需补充），支持“链式赋值”（如 lt1 = lt2 = lt3 ）。

关键注意事项:
 
1. 必须补充返回语句：

• 原代码缺少 return *this; ，不符合赋值运算符重载的语法要求（需返回修改后的当前对象引用），编译会报错，正确结尾应添加 return *this; 。

2. 优点与局限性：

• 优点：逻辑直观，步骤清晰（先清空再拷贝），能保证深拷贝的安全性，避免浅拷贝的双重释放问题。
• 局限性：时间复杂度为 O(N) （ N 为源链表长度），且若当前链表原本节点数远少于源链表，清空后再逐个插入的效率中规中矩（后续可通过“临时对象交换法”优化为更高效的实现，但传统写法胜在易理解）。

3. 依赖前提：

• clear() 函数需正确实现：仅删除有效节点，保留哨兵头节点 _head 。
• 范围for循环需依赖 lt 的迭代器（ begin() / end() ）正确实现，确保能遍历所有有效数据。

赋值重载现代写法

list<T>& operator=(list<T> lt)
{
    swap(_head,lt._head);
    return *this;
}

这段代码是双向循环链表赋值运算符重载的“现代写法”，通过“值传递+指针交换”实现高效深拷贝，逻辑更简洁且能自动处理自我赋值和内存释放。
代码逻辑:

• 1. 参数按值传递，自动完成深拷贝：
• - 函数参数 list<T> lt 是值传递，而非引用传递。调用赋值运算符时（如 lt1 = lt4 ），会先通过 list 的拷贝构造函数，创建源链表 lt4 的完整深拷贝副本（即参数 lt ）；
• - 这一步已确保 lt 的节点内存与源链表完全独立，且自我赋值时（如 lt1 = lt1 ），值传递会拷贝一个临时副本，后续交换不会破坏原链表，天然避免自我赋值问题。
• 2. 交换当前链表与参数 lt 的哨兵头节点指针：
• - 通过 swap(_head, lt._head) ，将当前对象（ this ）的 _head （指向原链表的哨兵头节点及有效节点）与参数 lt 的 _head （指向源链表的深拷贝副本）交换；
• - 交换后，当前对象 this 拥有了 lt 的深拷贝数据（即完成赋值目标），而 lt 则拥有了当前对象的原链表数据。
• 3. 参数 lt 出作用域，自动释放原链表内存：
• - 赋值运算符执行结束后，参数 lt （局部变量）会出作用域，自动调用 list 的析构函数；
• - 此时 lt 的 _head 指向当前对象的原链表数据，析构函数会调用 clear() 删除原链表的所有有效节点，并释放原哨兵头节点，完美实现“自动清理当前对象旧数据”，无需手动调用 clear() ，避免内存泄漏。

核心优势（对比传统写法）:

1. 代码更简洁：无需手动写自我赋值检查（ if(this != &lt) ）和 clear() 清理旧数据，逻辑浓缩为2行核心代码。
2. 效率更优：传统写法“清空旧数据+逐个拷贝新数据”需两次遍历（清空1次+拷贝1次），而现代写法仅需1次拷贝（值传递时的拷贝构造），且交换指针是 O(1) 操作。
3. 安全性更高：天然避免自我赋值风险，且旧数据的释放依赖析构函数，减少手动操作出错概率（如传统写法漏写 clear() 导致内存泄漏）。

关键前提:

1. 需正确实现 list 的拷贝构造函数：值传递参数 lt 时，依赖拷贝构造函数完成源链表的深拷贝，若拷贝构造是浅拷贝，此写法仍会出现双重释放问题。
2. swap 函数需能正确交换指针：此处 swap(_head, lt._head) 是对两个 Node* 指针的简单交换（可直接用 std::swap ，无需自定义链表 swap ），确保交换后指针指向正确。

list模拟实现完整代码：

#include<iostream>
#include<vector>
#include<stdio.h>
#include<assert.h>
using namespace std;
namespace Z
{
	template<class T>
	struct __list_node
	{
		__list_node<T>* _next;
		__list_node<T>* _prev;
		T _data;
		//默认构造函数
		__list_node(const T& x = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}

	};
	//迭代器类
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef __list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> self;
		Node* _node;
		__list_iterator(Node* node)
			:_node(node)
		{}
		//*it->it.operator*()
		T& operator*()//这里需要返回引用，*it = 1;当做这样的操作时需要能够写
		{
			return _node->_data;
		}
		Ptr operator->()//这里需要返回引用，*it = 1;当做这样的操作时需要能够写
		{
			return &_node->_data;
		}
		//operator->()
		//{

		//}
		self& operator++()//前置++,返回引用减少拷贝构造
		{
			_node = _node->_next;
			return *this;
		}
		self operator++(int)//后置++，不能返回引用，因为tmp出了作用域就销毁了
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self& operator--()//前置--,返回引用减少拷贝构造
		{
			_node = _node->_prev;
			return *this;
		}
		self operator--(int)//后置--，不能返回引用，因为tmp出了作用域就销毁了
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		bool operator==(const self& it)
		{
			return _node == it._node;
		}
		bool operator!=(const self& it)
		{
			return _node != it._node;
		}
	};
	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;
		//默认构造函数
		list()
		{
			//带头双向链表
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		//lt2(lt1)
		//传统拷贝构造
		//list(const list<T>& lt)
		//{
		//	_head = new Node;
		//	_head->_next = _head;
		//	_head->_prev = _head;
		//	for (const auto& e : lt)
		//	{
		//		push_back(e);
		//	}
		//}
		//现代拷贝构造
		//迭代器构造函数
		template<class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
		//lt2(lt1)
		//拷贝构造现代写法
		list(const list<T>& lt)
		{
			//this->_head = new Node;//这里需要给lt2创建头节点，不然lt2的_head是空指针，swap会出问题
			//_head->_next = _head;
			//_head->_prev = _head;
			list<T> tmp(lt.begin(), lt.end());
			std::swap(_head, tmp._head);
		}
		//赋值重载传统写法
		list<T>& operator=(const list<T>& lt)
		{
			if (this != &lt)
			{
				//不是相同的对象就交换
				clear();
				for (const auto& e : lt)
				{
					push_back(e);
				}
			}
		}
		//赋值重载现代写法
		list<T>& operator=(list<T> lt)
		{
			swap(_head, lt._head);
			return *this;
		}
		////迭代器的模拟实现
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end()const
		{
			return const_iterator(_head);
		}
		void push_back(const T& x)
		{
			Node* tail = _head->_prev;
			Node* newnode = new Node(x);

			newnode->_next = _head;
			newnode->_prev = tail;
			tail->_next = newnode;
			_head->_prev = newnode;
		}
		void push_front(const T& x)
		{
			Node* next = _head->_next;
			Node* newnode = new Node(x);

			newnode->_next = next;
			newnode->_prev = _head;
			next->_prev = newnode;
			_head->_next = newnode;
		}
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(x);

			newnode->_next = cur;
			cur->_prev = newnode;
			prev->_next = newnode;
			newnode->_prev = prev;

			return iterator(newnode);
		}
		//类模板中的成员函数是按需实例化，调用了哪个成员函数，实例化哪一个
//成员函数是函数模板
		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;
			delete cur;
			return iterator(next);
		}
		size_t size()
		{
			size_t n = 0;
			iterator it = begin();
			while (it != end())
			{
				it++;
				n++;
			}
			return n;
		}
		bool empty()
		{
			return begin() == end();
			//如果begin等于end就是链表为空的时候
		}
		/*void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				Node* del = it->_node;
				++it;
				delete del;
			}
			_head - _next = _head;
		}*/
		//可以复用
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

	private:
		Node* _head;
	};
	struct TreeNode
	{
		struct TreeNode* _left;
		struct TreeNode* _right;
		int _val;
		TreeNode(int val = -1)
			:_left(nullptr)
			, _right(nullptr)
			, _val(val)
		{}
	};
	//ostream operator<<(ostream& out,TreeNode n);
	void test_list1()
	{
		Z::list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_front(10);
		lt.push_front(20);
		lt.push_front(30);
		lt.push_front(40);
		list<int> lt1(lt);
		list<int>::iterator it = lt1.begin();
		while (it != lt1.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;
	}
	void test_list2()
	{
		Z::list<TreeNode> lt;
		lt.push_back(TreeNode(1));
		lt.push_back(TreeNode(2));
		lt.push_back(TreeNode(3));
		lt.push_back(TreeNode(4));
		list<TreeNode>::iterator it = lt.begin();//it现在指向的是结构体
		while (it != lt.end())
		{
			//cout<<*it<<" ";
			//cout << (*it)._val << " ";
			//假设打印这三个
			//printf("val:%d,left:%p,right:%p\n", (*it)._val, (*it)._left, (*it)._right);
			printf("val:%d,left:%p,right:%p\n", it->_val, it->_left, it->_right);
			++it;
		}
		cout << endl;
	}
}
int main()
{
	Z::test_list1();
	return 0;
}

总结:

本文详细解析了C++中list容器的模拟实现，重点介绍了带头双向循环链表的结构设计和迭代器实现。主要内容包括：

1. 链表节点设计：采用模板类__list_node包含prev、next指针和数据域，支持默认构造和灵活初始化；
2. 哨兵节点机制：通过不存储数据的哨兵头节点简化边界操作，形成循环链表结构；
3. 迭代器实现：封装节点指针，重载操作符模拟指针行为，通过模板参数区分普通迭代器和const迭代器；
4. 核心接口实现：包括push_back、insert、erase等操作，以及现代写法实现的拷贝构造和赋值重载。

该实现完整展现了STL list的底层机制，突出了双向链表的优势，同时体现了C++模板编程和运算符重载的灵活运用。

感谢大家的观看!