《C++初阶之STL》【list容器：详解 + 实现】

往期《C++初阶》回顾：

/------------ 入门基础 ------------/
【C++的前世今生】
【命名空间 + 输入&输出 + 缺省参数 + 函数重载】
【普通引用 + 常量引用 + 内联函数 + nullptr】
/------------ 类和对象 ------------/
【类 + 类域 + 访问限定符 + 对象的大小 + this指针】
【类的六大默认成员函数】
【初始化列表 + 自定义类型转换 + static成员】
【友元 + 内部类 + 匿名对象】
【经典案例：日期类】
/------------ 内存管理 ------------/
【内存分布 + operator new/delete + 定位new】
/------------ STL ------------/
【泛型编程 + STL简介】
【auto关键字 + 范围for循环 + 迭代器】
【string类：详解 + 实现】
【vector容器：详解 + 实现】

前言

🌈元气满满的更新通知 🌞
hi～小伙伴们大家好呀！(ﾉ>ω<)ﾉ 我又来给大家更新日期小贴士啦！
明天就是中伏了，这意味着为期 10 天的头伏即将结束，但三伏天还没走完哦(>﹏<)～🔥 现在正值盛夏，我们依然处在夏季最热的阶段，大家一定要记得做好防暑措施呀～🍉（递上冰镇西瓜）

💻技术内容预告 ☕
今天为大家带来的内容是：【list 容器：详解 + 实现】 📚。这可是 STL 中真正开始有挑战性的容器啦！(๑•̀ㅂ•́)و✧ 但相信有了前面 “string + vector” 的学习铺垫，list 对大家来说应该不算太难(｡•̀ᴗ-)✧～💪
本文依旧是长篇内容（哈哈，说 “巨制” 可谈不上(⁄ ⁄•⁄ω⁄•⁄ ⁄)），全文大约2w字，内容还是分为 “详解” 和 “实现” 两个部分。

---

✨ 这里温馨提示一下： ✨
实现部分在目录里虽然只占 3 个条目，但这绝不代表它不重要！恰恰相反，这部分是全篇最核心的内容～🌟
鼠鼠我没有把不同的接口实现单独拆分出来，而是直接放了一整个文件的代码 —— 主要是考虑到在 CSDN 上阅读可能不太方便，以及拆分之后会缺失对整体的架构理解。所以大家可以直接把代码拷走，放到自己的 VS 里细细推敲、运行调试哦～👨💻
大家不用担心看不懂呦！(｡･ω･｡)ﾉ♡ 每个接口鼠鼠我都按步骤添加了注释～📝 而且对于一些核心的设计问题，在实现内容下方还有专门的针对性解释，相信大家一定能掌握的！(ﾉ≧∀≦)ﾉ

------------标准接口介绍------------

标准模板库中的list容器是什么样的呢？

cplusplus网站上关于C++的list容器的介绍：list - C++ Reference

C++标准模板库（STL）中对 list容器的介绍主要涵盖以下两个方面：

1. 成员函数：容器自身提供的方法（如：插入、删除、排序），用于直接操作容器，封装底层实现细节
2. 非成员函数重载：定义在容器外部的通用函数（如：比较、交换等），通过重载适配容器类型，提供统一操作接口

1. 常见的构造

// constructing lists
#include <iostream>
#include <list>

/*--------------------使用不同构造函数创建list对象--------------------*/
int main()
{
    /*--------------第一种构造函数：“默认”构造函数--------------*/
    std::list<int> first;  //创建空列表

    /*--------------第二种构造函数：“填充”构造函数--------------*/
    std::list<int> second(4, 100);   //4个值为100的元素

    /*--------------第三种构造函数：“范围”构造函数--------------*/
    std::list<int> third(second.begin(), second.end());  //复制second的所有元素

    /*--------------第四种构造函数：“拷贝”构造函数--------------*/
    std::list<int> fourth(third);   //复制third的所有元素


    /*--------------第四种构造函数：“通过指针范围”构造函数--------------*/
    //1.使用数组初始化列表
    int myints[] = { 16,2,77,29 };
    //2.通过指针范围构造
    std::list<int> fifth(myints, myints + sizeof(myints) / sizeof(int)); //myints指向首元素，myints + 4指向尾后位置

    //3.输出fifth的内容
    std::cout << "fifth链表中的内容是: ";
    for (std::list<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
    {
        std::cout << *it << ' ';
    }
        
    std::cout << '\n';
    return 0;
}

代码案例：初始化列表（简单的了解）

#include <iostream>
using namespace std;

int main()
{
	/*-------------使用 auto 关键字可以自动推导变量il的类型-------------*/
	auto il1 = { 10, 20, 30 };
	cout << "auto il = { 10, 20, 30 }中il的类型：" << typeid(il1).name() << endl;
	cout << "auto il = { 10, 20, 30 }中il的大小：" << sizeof(il1) << endl; //输出 initializer_list 对象的大小（以字节为单位）

	// 注意：
	// initializer_list 本身只包含两个指针（指向数组的开始和结束）
	// 因此其大小通常是指针大小的两倍（例如：在64位系统上是16字节）
	// 它并不直接包含列表中的元素，元素存储在初始化列表创建的临时数组中


	/*-------------显式声明一个 initializer_list 类型的变量il-------------*/
	// initializer_list 是 C++ 标准库中的一种轻量级容器类型，用于表示一个“只读的临时值序列”
	// 它通常用于支持使用花括号初始化列表语法来初始化对象或传递参数
	initializer_list<int> il2 = { 10, 20, 30 };

	cout << "initializer_list<int> il = { 10, 20, 30 }中il的类型：" << typeid(il2).name() << endl;
	cout << "initializer_list<int> il = { 10, 20, 30 }中il的大小：" << sizeof(il2) << endl;

	return 0;
}

2. 迭代器操作

std::list::begin

// list::begin
#include <iostream>
#include <list>

int main()
{
    /*-----------第一阶段：使用“数组初始化列表 + 范围构造”创建一个list容器-----------*/
    int myints[] = { 75,23,65,42,13 };
    std::list<int> mylist(myints, myints + 5);

    /*-----------第二阶段：使用“正向迭代器”遍历整个list容器-----------*/
    std::cout << "mylist中的内容是:";
    for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    return 0;
}

std::list::end

std::list::rbegin

// list::rbegin/rend
#include <iostream>
#include <list>

int main()
{
    /*----------第一阶段：创建一个list的容器并进行初始化----------*/
    std::list<int> mylist;
    for (int i = 1; i <= 5; ++i) mylist.push_back(i);

    std::cout << "mylist backwards:";
    for (std::list<int>::reverse_iterator rit = mylist.rbegin(); rit != mylist.rend(); ++rit)
    {
        std::cout << ' ' << *rit;
    }
        

    std::cout << '\n';

    return 0;
}

std::list::rend

3. 容量的操作

std::list::size

// list::size
#include <iostream>
#include <list>

int main()
{
	std::list<int> mylist;
	std::cout << "初始状态的mylist的size为：" << mylist.size() << '\n';

	for (int i = 0; i < 10; i++) mylist.push_back(i);
	std::cout << "尾插10个节点之后的size为：" << mylist.size() << '\n';

	mylist.insert(mylist.begin(), 10, 100);
	std::cout << "再在下标为10的位置插入10个节点后的size为：" << mylist.size() << '\n';

	mylist.pop_back();
	std::cout << "尾删一个节点之后的size为：" << mylist.size() << '\n';

	return 0;
}

std::list::empty

// list::empty
#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist;
    int sum(0); //使用“直接初始化”进行初始化，等同于：int sum = 0;

    for (int i = 1; i <= 10; ++i)
    {
        mylist.push_back(i);
    }

    while (!mylist.empty())
    {
        sum += mylist.front();
        mylist.pop_front();
    }

    std::cout << "从1加到的10的和为: " << sum << '\n';

    return 0;
}

4. 访问的操作

std::list::front

// list::front
#include <iostream>
#include <list>

int main()
{
	std::list<int> mylist;

	mylist.push_back(77);
	mylist.push_back(22);

	std::cout << "初始状态下的mylist.front()是：" << mylist.front() << '\n';

	mylist.front() -= mylist.back();

	std::cout << "经过操作现在mylist.front()是：" << mylist.front() << '\n';

	return 0;
}

std::list::back

// list::back
#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist;

    mylist.push_back(10);

    while (mylist.back() != 0)
    {
        mylist.push_back(mylist.back() - 1);
    }

    std::cout << "mylist的内容是:";
    for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    }
        

    std::cout << '\n';

    return 0;
}

4. 修改的操作

std::list::clear

int main()
{
    std::list<int> mylist;
    std::list<int>::iterator it;

    mylist.push_back(100);
    mylist.push_back(200);
    mylist.push_back(300);

    std::cout << "mylist的内容是：";
    for (it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    }  
    std::cout << '\n';

    mylist.clear();
    mylist.push_back(1101);
    mylist.push_back(2202);

    std::cout << "经过clear再尾插两个节点后，mylist的内容是：";
    for (it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    return 0;
}

std::list::swap

// swap lists
#include <iostream>
#include <list>

int main()
{
    std::list<int> first(3, 100);   //使用“填充构造函数”创建出一个有三个100的链表 first
    std::list<int> second(5, 200);  //使用“填充构造函数”创建出一个有五个200的链表 second

    first.swap(second);

    std::cout << "first链表中的内容是:";
    for (std::list<int>::iterator it = first.begin(); it != first.end(); it++)
        std::cout << ' ' << *it;
    std::cout << '\n';

    std::cout << "second链表中的内容是:";
    for (std::list<int>::iterator it = second.begin(); it != second.end(); it++)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

std::list::push_front

// list::push_front
#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist(2, 100);   //使用“填充构造函数”初始化一个有两个100的链表mylist
    mylist.push_front(200);
    mylist.push_front(300);

    std::cout << "mylist中的内容是：";
    for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << ' ' << *it;

    std::cout << '\n';
    return 0;
}

std::list::push_back

代码示例1：push_back接口函数的使用

// list::push_back
#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist;
    int myint;

    std::cout << "请输入一些整数（输入 0 结束）:\n";

    do 
    {
        std::cin >> myint;
        mylist.push_back(myint);
    } while (myint);

    std::cout << "mylist中存储节点的个数为：" << mylist.size();

    return 0;
}

代码示例2：push_back和emplace_back的区别

int main()
{
    /*------------------第一阶段：创建一个“存储内置类型变量”的list容器------------------*/
    list<int> lt1;

    //1.使用push_back进行尾插
    lt1.push_back(1);

    //2.使用emplace_back进行尾插
    //注意：区别 C++11新特性：就地构造，避免临时对象（对基本类型效果相同）
    lt1.emplace_back(2);  
    lt1.emplace_back(3);
    lt1.emplace_back(4);

    for (auto it : lt1)
    {
        cout << it << " ";
    }
    cout << endl; 


    /*------------------第二阶段：创建一个“存储自定义类型变量”的list容器------------------*/
    list<A> lt2;              



    /*------------展示：push_back接口函数的使用------------*/
    cout << "=============展示：push_back接口函数的使用=============" << endl;
    cout << "情况1：" << endl;
    // 情况1：先构造对象，再push_back（调用1次构造+1次拷贝构造）
    A aa1(1, 1);                // 显式构造A对象（调用构造函数）
    lt2.push_back(aa1);         // 尾插已构造的对象（调用拷贝构造）

    cout << "情况2：" << endl;
    // 情况2：直接push_back临时对象（调用1次构造）
    lt2.push_back(A(2, 2));     // 尾插临时对象（直接构造，效率更高）

    // 错误示例：push_back仅接受单个参数
    //lt2.push_back(3, 3);      // 错误！push_back仅接受单个参数


    /*------------展示：emplace_back接口函数的使用------------*/
    cout << "=============展示：emplace_back接口函数的使用=============" << endl;
    cout << "情况1：" << endl;
    // 情况1：emplace_back“已有对象”（等价于push_back，调用1次拷贝构造）
    A aa2(1, 1);
    lt2.emplace_back(aa2);      // 尾插对象（调用拷贝构造，等价于push_back(aa1)）

    cout << "情况2：" << endl;
    // 情况2：emplace_back“临时对象”（与push_back临时对象效果相同）
    lt2.emplace_back(A(2, 2));  // 尾插临时对象（直接构造）

    cout << "情况3：" << endl;
    // C++11特性：emplace_back可直接传递构造参数，避免临时对象
    // 情况3：emplace_back的核心优势：直接传递构造参数（调用1次构造，无拷贝）
    lt2.emplace_back(3, 3);     // 无需创建临时对象，直接在容器内存中构造对象

    return 0;
}

std::list::insert

// inserting into a list
#include <iostream>
#include <list>
#include <vector>

int main()
{
    std::list<int> mylist;
    std::list<int>::iterator it;

    // set some initial values:
    for (int i = 1; i <= 5; ++i) mylist.push_back(i); 

    it = mylist.begin();
    ++it;      //注意：现在的迭代器指向节点2   

    /*-----------使用list容器的：“普通的指定位置插入”操作-----------*/
    mylist.insert(it, 10);                        // 1 10 2 3 4 5

    //                                                    ^
    //进行完“普通的指定位置插入”插入之后，it迭代器还是指向2


    /*-----------使用list容器的：“填充指定插入”操作-----------*/
    mylist.insert(it, 2, 20);                      // 1 10 20 20 2 3 4 5

    --it;                  //                                  ^
    //进行完“填充指定插入”操作之后，it迭代器还是指向2，但是--后现在的it迭代器指向第二个20
    //所以下面的“迭代器范围插入”操作是在20的前面插入两个30



    /*-----------使用list容器的：“迭代器范围指定插入”操作-----------*/
    std::vector<int> myvector(2, 30);  //使用vector容器的“填充构造函数”初始化一个有两个30的vector容器
    mylist.insert(it, myvector.begin(), myvector.end());  //使用list容器的“迭代器范围指定插入”为list容器进行赋值
    // 1 10 20 30 30 20 2 3 4 5
    //                ^
    //进行完“迭代器范围指定插入”操作之后，it迭代器还是指向20
    

    std::cout << "mylist中的内容是:";
    for (it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    return 0;
}

std::list::pop_front

// list::pop_front
#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist;
    mylist.push_back(100);
    mylist.push_back(200);
    mylist.push_back(300);

    std::cout << "弹出 mylist 中的元素:";
    while (!mylist.empty())
    {
        std::cout << ' ' << mylist.front();
        mylist.pop_front();
    }

    std::cout << "\n最终mylist中节点的个数是：" << mylist.size() << '\n';

    return 0;
}

std::list::pop_back

// list::pop_back
#include <iostream>
#include <list>

int main()
{
    std::list<int> mylist;
    int sum(0);
    mylist.push_back(100);
    mylist.push_back(200);
    mylist.push_back(300);

    while (!mylist.empty())
    {
        sum += mylist.back();
        mylist.pop_back();
    }

    std::cout << "mylist中所有节点的和为：" << sum << '\n';

    return 0;
}

std::list::erase

// erasing from list
#include <iostream>
#include <list>

int main()
{
    /*-------------第一步：定义第一个list容器，并定义两个迭代器-------------*/
    std::list<int> mylist;
    std::list<int>::iterator it1, it2;

    /*-------------第二步：对list容器的进行赋值-------------*/
    for (int i = 1; i < 10; ++i)
    {
        mylist.push_back(i * 10);
    }

    /*-------------第三步：对list迭代器的进行赋值-------------*/
                                // 10  20 30 40 50 60 70  80 90
    it1 = it2 = mylist.begin(); // ^^
    advance(it2, 6);            // ^                   ^
    ++it1;                      //      ^              ^


    /*-------------第四步：使用list的erase接口-------------*/
    
    /*-------使用list容器的：“普通的指定迭代器删除”操作-------*/
    //1.删除it1指向的节点
    it1 = mylist.erase(it1);   // 10 30 40 50 60 70 80 90
                               //    ^           ^
    //1.删除it2指向的节点
    it2 = mylist.erase(it2);   // 10 30 40 50 60 80 90
                               //    ^           ^

    ++it1;                      //       ^        ^
    --it2;                      //       ^     ^


    /*-------使用list容器的：“迭代器范围删除”操作-------*/
    mylist.erase(it1, it2);     // 10 30 60 80 90
                                //        ^
    //注：删除[it1, it2)范围内的元素(左闭右开区间)，即删除40、50，但不删除60



    std::cout << "mylist中的内容是:";
    for (it1 = mylist.begin(); it1 != mylist.end(); ++it1)
    {
        std::cout << ' ' << *it1;
    }
        
    std::cout << '\n';

    return 0;
}

5. 其他的操作

std::list::splice

// splicing lists
#include <iostream>
#include <list>

int main()
{
    /*----------------第一阶段：定义两个“list的容器” + “list的迭代器”----------------*/
    std::list<int> mylist1, mylist2;
    std::list<int>::iterator it;

    /*----------------第二阶段：为两个list容器进行初始化----------------*/
    for (int i = 1; i <= 4; ++i)
    {
        mylist1.push_back(i);      // mylist1: 1 2 3 4
    }
        

    for (int i = 1; i <= 3; ++i)
    {
        mylist2.push_back(i * 10);   // mylist2: 10 20 30
    }
        
    /*----------------第三阶段：为list的迭代器进行初始化----------------*/
    it = mylist1.begin();
    ++it;                         //it -> 2（现在it指向的mylist1的节点2）




    /*----------------第四阶段：展示splice接口函数的三种使用方式----------------*/
    /*---------第一种使用方式：“整个列表”的拼接操作---------*/
    mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4
                                 // mylist2 (empty)           
    //注：将mylist2的所有元素转移到mylist1的it位置前
    //注意: it 仍然指向2（转移后成为第5个元素）


    /*---------第二种使用方式：“单个元素”的拼接操作---------*/
    mylist2.splice(mylist2.begin(), mylist1, it);  // mylist1: 1 10 20 30 3 4
                                                   // mylist2: 2
    //注：将mylist1中it指向的元素(2)转移到mylist2的开头
    //注意: 转移后it失效，因为原位置元素已被移除


    /*---------第三种使用方式：“元素范围”的拼接操作---------*/
    it = mylist1.begin();
    std::advance(it, 3);           //it -> 30（现在it指向的mylist1的节点30）

    mylist1.splice(mylist1.begin(), mylist1, it, mylist1.end()); // mylist1: 30 3 4 1 10 20
                                                                
    //注：将mylist1中[it, end)的元素转移到自身开头，转移范围: [30, end)，即30, 3, 4




    std::cout << "mylist1中的内容是:";
    for (it = mylist1.begin(); it != mylist1.end(); ++it) 
    {
        std::cout << ' ' << *it;
    }
        
    std::cout << '\n';

    std::cout << "mylist2中的内容是:";
    for (it = mylist2.begin(); it != mylist2.end(); ++it)
    {
        std::cout << ' ' << *it;
    }   
    std::cout << '\n';

    return 0;
}

std::list::remove

// remove from list
#include <iostream>
#include <list>

int main()
{
    /*----------第一阶段：使用“数组初始化列表 + 范围构造”创建一个list容器----------*/
    int myints[] = { 17,89,7,14 };
    std::list<int> mylist(myints, myints + 4);

    /*----------第二阶段：使用remove删除list容器中“指定值”的节点----------*/
    mylist.remove(89);  //remove()会遍历整个列表，删除所有等于给定值的元素


    std::cout << "mylist中的内容是:";
    for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    return 0;
}

std::list::remove_if

// list::remove_if
#include <iostream>
#include <list>

//1. 函数对象（谓词）：判断数值是否为个位数（小于 10）
bool single_digit(const int& value) 
{ 
    return (value < 10); 
}

//2. 函数对象（谓词）：判断数值是否为奇数
struct is_odd 
{
    bool operator() (const int& value)  //注意：用结构体实现，需重载 operator()，使其能像函数一样被调用
    { 
        return (value % 2) == 1; 
    }
};

int main()
{
    /*------------第一阶段：使用“数组初始化列表 + 范围构造”创建一个list容器------------*/
    int myints[] = { 15,36,7,17,20,39,4,1 };
    std::list<int> mylist(myints, myints + 8);//mylist：15 36 7 17 20 39 4 1

    /*------------第二阶段：使用remove删除list容器中“满足条件”的节点------------*/

    //1.第一次调用 remove_if：传入函数名 single_digit 作为条件
    mylist.remove_if(single_digit);           //mylist：15 36 17 20 39

    //2.第二次调用 remove_if：传入 is_odd 结构体的临时对象 is_odd()
    mylist.remove_if(is_odd());               //mylist：36 20


    std::cout << "mylist中的内容是:";
    for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    } 
    std::cout << '\n';
    return 0;
}

std::list::unique

// list::unique
#include <iostream>
#include <cmath>
#include <list>

//1. 二元谓词（函数形式）：判断两个浮点数的整数部分是否相同
bool same_integral_part(double first, double second)  //注意：用于 unique 的自定义去重逻辑，接收两个 double 参数，返回 bool
{
    return (int(first) == int(second));
}

//2. 二元谓词（函数对象/仿函数形式）：判断两个浮点数的差值是否小于 5.0
struct is_near  //注意：用结构体实现，需重载 operator()，使对象能像函数一样被调用
{
    bool operator() (double first, double second) 
    {
        return (fabs(first - second) < 5.0); //用 fabs 计算绝对值，判断差值是否小于 5.0
    }
};

int main()
{
    /*------------第一阶段：使用“数组初始化列表 + 范围构造”创建一个list容器------------*/
    double mydoubles[] = 
    { 
        12.15,  2.72, 73.0, 12.77, 3.14, 
        12.77, 73.35, 72.25, 15.3, 72.25 
    };
    std::list<double> mylist(mydoubles, mydoubles + 10);


    /*------------第二阶段：展示unique不同的使用方法------------*/
    //1.首先对list容器进行排序
    mylist.sort();             // 2.72,  3.14, 12.15, 12.77, 12.77,
                               // 15.3,  72.25, 72.25, 73.0,  73.35

    //2.然后再使用unique删除相邻的重复元素
    /*----------第一种：“无参数”版本的unique----------*/
    mylist.unique();           // 2.72,  3.14, 12.15, 12.77
                               // 15.3,  72.25, 73.0,  73.35

    /*----------第二种：“带二元谓词参数”版本的unique----------*/
    mylist.unique(same_integral_part);  // 2.72,  3.14, 12.15
                                        // 15.3,  72.25, 73.0

    mylist.unique(is_near());           //  2.72, 12.15, 72.25
    //  传入 is_near() 临时对象，删除“差值小于 5.0”的连续元素
    //  逻辑：遍历 list，若相邻元素差值 < 5.0，则视为“重复”并删除
    //  执行过程（基于上一步结果）：
    //  - 2.72 和 3.14：差值 0.42 < 5 → 删除 3.14 → 保留 2.72
    //  - 2.72 和 12.15：差值 9.43 ≥ 5 → 保留 12.15
    //  - 12.15 和 15.3：差值 3.15 < 5 → 删除 15.3 → 保留 12.15
    //  - 12.15 和 72.25：差值 60.1 ≥ 5 → 保留 72.25
    //  - 72.25 和 73.0：差值 0.75 < 5 → 删除 73.0 → 保留 72.25
    //  最终内容：2.72, 12.15, 72.25


    std::cout << "mylist中的内容是:";
    for (std::list<double>::iterator it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    return 0;
}

std::list::merge

// list::merge
#include <iostream>
#include <list>

//自定义比较函数：仅比较浮点数的整数部分
bool mycomparison(double first, double second) //用于 merge 的自定义排序逻辑
{
    return (int(first) < int(second));
}

int main()
{
    /*------------------第一阶段：创建两个list容器并进行初始化------------------*/
    std::list<double> first, second;

    first.push_back(3.1);
    first.push_back(2.2);
    first.push_back(2.9);

    second.push_back(3.7);
    second.push_back(7.1);
    second.push_back(1.4);

    /*------------------第二阶段：展示merge不同的使用方法------------------*/
    //1.首先对两个list容器进行排序
    first.sort();  // sort 后 first： 2.2, 2.9, 3.1
    second.sort(); // sort 后 second：1.4, 3.7, 7.1

    /*----------使用“无自定义比较器”的merge操作----------*/

    first.merge(second); // 执行后 first：1.4, 2.2, 2.9, 3.1, 3.7, 7.1 
                         // second 变为空（元素已被转移）



    /*----------使用“带自定义比较器”的merge操作----------*/

    second.push_back(2.1);
    first.merge(second, mycomparison);



    std::cout << "first链表中的内容是:";
    for (std::list<double>::iterator it = first.begin(); it != first.end(); ++it)
    {
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    return 0;
}

std::list::sort

代码示例1：sort接口函数的使用

// list::sort
#include <iostream>
#include <list>
#include <string>
#include <cctype>

//自定义比较函数：不区分大小写的字符串比较
bool compare_nocase(const std::string& first, const std::string& second)
{
    unsigned int i = 0;
    while ((i < first.length()) && (i < second.length())) //只要两个字符串中有一个字符串已经遍历完毕while循环就结束
    {
        
        if (tolower(first[i]) < tolower(second[i])) return true; //注意：转换为小写后比较（不区分大小写的字符串的比较）
        else if (tolower(first[i]) > tolower(second[i])) return false;

        ++i;
    }

    return (first.length() < second.length()); //注意：如果所有已比较字符都相同，则较短的字符串排在前面
}

int main()
{
    /*------------------第一阶段：创建两个list容器并进行初始化------------------*/
    std::list<std::string> mylist;
    std::list<std::string>::iterator it;

    mylist.push_back("one");
    mylist.push_back("two");
    mylist.push_back("Three"); //注意：插入三个字符串，包含大小写不同的情况



    /*------------------第二阶段：展示sort不同的使用方法------------------*/
     /*----------使用“无自定义比较器”的sort操作----------*/
    // 第一次排序：使用默认比较（字典序，区分大小写）
    // 默认规则下，大写字母排在小写字母之前
    // 排序结果：Three, one, two
    mylist.sort();

    std::cout << "使用“无自定义比较器”的sort排序后mylist中的内容是:";
    for (it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    }
    std::cout << '\n';


    /*----------使用“带自定义比较器”的sort操作----------*/
    // 第二次排序：使用自定义比较函数 compare_nocase
    // 自定义规则：不区分大小写，仅按字母顺序和长度排序
    // 排序结果：one, Three, two
    mylist.sort(compare_nocase);

    std::cout << "使用“带自定义比较器”的sort排序后mylist中的内容是:";
    for (it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    return 0;
}

代码示例2：sort接口函数的使用

#include <iostream>
#include <list>
using namespace std;

int main()
{
    list<int> mylist;

    mylist.push_back(1);
    mylist.push_back(20);
    mylist.push_back(3);
    mylist.push_back(5);
    mylist.push_back(4);
    mylist.push_back(5);
    mylist.push_back(6);
    cout << "排序后mylist中的内容是:";
    for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
    {
        cout << ' ' << *it;
    }
    cout << '\n';

    /*---------------使用sort“默认的升序排序”---------------*/

    //mylist.sort();  //sort() 方法使用元素类型的 operator< 进行比较

    


    /*---------------使用sort结合“仿函数实现：升序+降序”---------------*/
    // less<int> ls;        // 升序仿函数（默认）
    // greater<int> gt;     // 降序仿函数
    mylist.sort(greater<int>());   // 传入降序仿函数，链表排序为: 20 6 5 5 4 3 1
    //注意：greater<int>() 返回一个函数对象，定义 a > b 的比较规则

    cout << "排序后mylist中的内容是:";
    for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
    {
        cout << ' ' << *it;
    }
    return 0;
}

std::list::reverse

// reversing list
#include <iostream>
#include <list>
#include <algorithm>

int main()
{
    /*------------------第一阶段：创建一个list容器并进行初始化------------------*/
    std::list<int> mylist;

    for (int i = 1; i < 10; ++i)
    {
        mylist.push_back(i);
    }

    std::cout << "反转前mylist中的内容是:";
    for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    /*------------------第二阶段：展示list容器的两种反转方法------------------*/
    /*-----------使用“list容器的成员函数”进行反转-----------*/
    //mylist.reverse(); 

    //注意事项：
    //1.直接修改链表结构，交换每个节点的前后指针
    //2.时间复杂度 O(n)，高效且不需要额外空间


    /*-----------调用“STL中的反转算法”进行反转-----------*/

    reverse(mylist.begin(), mylist.end());

    //注意事项：
    //1.需要包含 <algorithm> 头文件
    //2.此方法不适用于 list，因为 std::reverse 要求随机访问迭代器
    //3.而 list 仅提供双向迭代器，编译时会报错

    std::cout << "反转后mylist中的内容是:";
    for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)
    {
        std::cout << ' ' << *it;
    }

    std::cout << '\n';

    return 0;
}

------------模拟实现展示------------

list容器存储结构的设计

在 C++ 标准模板库（STL）中，list容器的底层实现依托于数据结构中的 双向链表，更具体地说，它采用的是带头节点的双向循环链表结构。

• 这种设计使得 list 在元素插入、删除等操作上具备高效性，且能灵活支持双向遍历。

---

具体来看，带头节点的双向循环链表结构包含以下核心特点：

• 双向性：每个节点除了存储数据本身外，还包含两个指针，这使得从任意节点出发都能便捷地向前或向后访问其他节点。
  • 一个指向其前一个节点（前驱指针）
  • 一个指向其后一个节点（后继指针）
• 循环性：链表的最后一个节点的后继指针会指向头节点，而头节点的前驱指针则指向最后一个节点，形成一个闭环。
  • 避免了传统非循环链表中 “尾节点后继为空” 的边界判断问题
  • 简化了链表操作的逻辑
• 头节点：链表中存在一个不存储实际数据的头节点（哨兵节点），它作为链表的起始标记，统一了空链表与非空链表的操作方式。
  • 无论是插入、删除还是遍历，都无需额外处理链表为空的特殊情况
  • 提升了实现的简洁性和鲁棒性

正是基于这种底层结构，list容器能够在任意位置以常数时间复杂度$O(1)$完成元素的插入和删除操作（只需调整节点指针指向）

同时支持双向迭代器遍历，成为处理频繁插入删除场景的理想选择。

/************************** 任务2.1：list节点类的定义 **************************/
template <class T>
struct list_node
{
	/*--------------------成员变量--------------------*/
    //1.存储数据
    //2.指向前一个节点的指针 
    //3.指向下一个节点的指针
    
	T _data;				
	list_node<T>* _prev;  //注意：类型是“类类型的指针”，但是list类又是模板类，所以类型应该是；list_node<T>*
	list_node<T>* _next;   

	/*--------------------成员函数：全缺省默认构造函数--------------------*/
    

};

/************************** 任务2.3：list类的定义 **************************/

template <class T>
class list
{
private:
	/*--------------------------第一部分：定义类型别名--------------------------*/

	//重命名“list节点”的类型：list_node<T> ---> Node
	typedef list_node<T> Node;

	/*--------------------------第二部分：定义成员变量--------------------------*/

	Node* _head; //头节点指针（指向不存储有效数据的哨兵节点）
	size_t _size; //链表中有效元素的个数

public:
	/*--------------------------第一部分：定义类型别名--------------------------*/

	/*--------------------第一种情况：当我们使用的是“单模板参数 + 两个迭代器模板”*/
	////1.重命名“普通迭代器（可读可写）”的类型：list_iterator<T> ---> iterator
	//typedef list_iterator<T> iterator;

	////2.重命名“常量迭代器（只读）”的类型：list_iterator<T> ---> const_iterator
	//typedef list_const_iterator<T> cont_iterator;


	/*--------------------第二种情况：当我们使用的是“三模板那参数 + 一个迭代器模板”*/

	//1.重命名“普通迭代器（可读可写）”的类型：list_iterator<T,T&,T*> ---> iterator
	typedef list_iterator<T, T&, T*> iterator;

	//2.重命名“常量迭代器（只读）”的类型：list_iterator<T,const T&, const T*> ---> const_iterator
	typedef list_iterator<T, const T&, const T*> const_iterator;


	/*--------------------------第二部分：定义迭代器接口--------------------------*/


	/*--------------------------第三部分：构造/赋值/析构--------------------------*/


	/*--------------------------第四部分：容量相关的操作--------------------------*/
	

	/*--------------------------第五部分：增删改查的修改操作--------------------------*/

};

头文件：list.h

#pragma once

//任务1：包含需要的头文件
#include <iostream>
#include <assert.h>
#include <algorithm>
using namespace std;



//任务2：定义自定义命名空间mySpace
		//任务2.1：实现list节点的类模板
		//任务2.2：实现list迭代器的类模板
		//任务2.3：实现list的类模板
		//任务2.4：实现print_container的函数模板

namespace mySpace
{
	/************************** 任务2.1：list节点类的定义 **************************/

	/**
	* @brief 双向链表节点类
	* @tparam T 节点存储的数据类型
	*		包含数据域_data，前驱指针_prev，后继指针_next
	*		构造函数支持默认初始化，方便空节点创建
	*/
	template <class T>
	struct list_node
	{
		/*--------------------成员变量--------------------*/
		T _data;				//存储数据
		list_node<T>* _prev;	//指向前一个节点的指针 ---> 注意：类型是“类类型的指针”，但是list类又是模板类，所以类型应该是；list_node<T>*
		list_node<T>* _next;    //指向下一个节点的指针


		/*--------------------成员函数：全缺省默认构造函数--------------------*/
		list_node(const T& data = T()) :  //注意：list_node类有三个成员变量，但是传参时只传一个，另外两个用初始化列表的nullptr进行初始化
			_data(data),
			_prev(nullptr),
			_next(nullptr)
		{}
	};



	/************************** 任务2.2：list迭代器类的定义 **************************/

	/**
	* @brief 双向链表迭代器模板（支持普通引用和指针）
	* @tparam T 迭代器操作的数据类型
	* @tparam Ref 数据的引用类型（T& 或 const T&）
	* @tparam Ptr 数据的指针类型（T* 或 const T*）
	*		实现迭代器的基本操作：解引用、指针运算符、自增自减、比较运算
	*/

	template <class T, class Ref, class Ptr>
	struct list_iterator
	{
		/*--------------------定义类型别名--------------------*/

		//1.重命名“list节点”的类型：list_node<T> ---> Node
		typedef list_node<T> Node;

		//2.重命名“list迭代器”的类型：list_iterator<T,Ref,Ptr> ---> Self
		typedef list_iterator<T, Ref, Ptr> Self;

		/*--------------------定义成员变量--------------------*/

		Node* _node; //迭代器内部存储的节点指针，指向当前位置


		/*--------------------定义成员函数--------------------*/

		//1.实现：“有参构造函数”
		list_iterator(Node* node) :
			_node(node)
		{}


		//2.实现：“解引用运算符重载函数”
		Ref operator*()  //注意：返回节点数据的引用
		{
			return _node->_data;
		}

		//3.实现：“指针运算符重载函数”
		Ptr operator->() //注意：返回节点数据的指针
		{
			return &_node->_data;
		}

		//4.实现：“前置自增运算符的重载函数”
		Self& operator++() //注意：移动到下一个节点，返回自身引用
		{
			_node = _node->_next;

			return *this;
		}

		//5.实现：“前置自减运算符的重载函数”
		Self& operator--()  //注意：移动到前一个节点，返回自身引用
		{
			_node = _node->_prev;

			return *this;
		}

		//6.实现：“后置自增运算符的重载函数”
		Self operator++(int)
		{
			//1.首先复制当前迭代器状态
			Self tmp(*this);

			//2.其次移动到下一个位置
			_node = _node->_next;


			//3.最后返回旧位置的迭代器
			return tmp;
		}


		//7.实现：“后置自减运算符的重载函数”
		Self operator--(int)
		{
			//1.首先复制当前迭代器状态
			Self tmp(*this);

			//2.其次移动到前一个节点
			_node = _node->_prev;


			//3.最后返回旧位置的迭代器
			return tmp;
		}

		//8.实现：“等号运算符的重载函数”

		bool operator==(const Self& lt) const
		{
			return _node == lt._node;  //比较节点指针地址
		}

		//9.实现：“不等号运算符的重载函数”
		bool operator!=(const Self& lt) const
		{
			return _node != lt._node;
		}
	};





	///*--------------------------“非常量”迭代器的实现--------------------------*/
	//template<class T>
	//struct list_iterator
	//{
	//	/*--------------------定义类型别名--------------------*/
	//	//1.重命名“list节点”的类型：list_node<T> ---> Node
	//	typedef list_node<T> Node;

	//	//2.重命名“list迭代器”的类型：list_iterator<T> ---> Self
	//	typedef list_iterator<T> Self;

	//	/*--------------------定义成员变量--------------------*/
	//	Node* _node;


	//	/*--------------------定义成员函数--------------------*/
	//	//1.实现：“有参构造函数”
	//	list_iterator(Node* node)
	//		:_node(node)
	//	{}

	//	//2.实现：“*运算符的重载函数”
	//	T& operator*()
	//	{
	//		return _node->_data;
	//	}


	//	//3.实现：“->运算符的重载函数”
	//	T* operator->()
	//	{
	//		return &_node->_data;
	//	}

	//	//4.实现：“前置++运算符的重载函数”
	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}

	//	//5.实现：“前置--运算符的重载函数”
	//	Self& operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}

	//	//6.实现：“后置++运算符的重载函数”
	//	Self operator++(int)
	//	{
	//		Self tmp(*this);

	//		_node = _node->_next;

	//		return tmp;
	//	}


	//	//7.实现：“后置--运算符的重载函数”
	//	Self& operator--(int)
	//	{
	//		Self tmp(*this);

	//		_node = _node->_prev;

	//		return tmp;
	//	}




	//	//8.实现：“==运算符的重载函数”
	//	bool operator==(const Self& lt) const
	//	{
	//		return _node == lt._node;
	//	}

	//	//9.实现：“!=运算符的重载函数”
	//	bool operator!=(const Self& lt) const
	//	{
	//		return _node != lt._node;
	//	}

	//};


	///*--------------------------“常量”迭代器的实现--------------------------*/
	//template<class T>
	//struct list_const_iterator
	//{
	//	/*--------------------定义类型别名--------------------*/
	//	//1.重命名“list节点”的类型：list_node<T> ----> Node
	//	typedef list_node<T> Node;

	//	//2.重命名：“list迭代器”的类型：list_const_iterator<T> ---> Self
	//	typedef list_const_iterator<T> Self;

	//	/*--------------------定义类型别名--------------------*/
	//	Node* _node;

	//	/*--------------------定义类型别名--------------------*/
	//	//1.实现：“有参构造函数”
	//	list_const_iterator(Node* node)
	//		:_node(node)
	//	{}

	//	//2.实现“*运算符的重载函数”
	//	const T& operator*()
	//	{
	//		return _node->_data;
	//	}


	//	//3.实现：“->运算符的重载函数”
	//	const T* operator->()
	//	{
	//		return &_node->_data;
	//	}


	//	//3.实现：“前置++运算符的重载函数”
	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}


	//	//4.实现：“前置--运算符的重载函数”
	//	Self& operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}


	//	//5.实现：“后置++运算符的重载函数”
	//	Self operator++(int)
	//	{
	//		Self tmp(*this);

	//		_node = _node->_next;

	//		return tmp;
	//	}


	//	//6.实现：“后置--运算符的重载函数”
	//	Self& operator--(int)
	//	{
	//		Self tmp(*this);

	//		_node = _node->_prev;

	//		return tmp;
	//	}


	//	//8.实现：“==运算符的重载函数”
	//	bool operator==(const Self& lt) const
	//	{
	//		return _node == lt._node;
	//	}

	//	//9.实现：“!=运算符的重载函数”
	//	bool operator!=(const Self& lt) const
	//	{
	//		return _node != lt._node;
	//	}
	//};






	/************************** 任务2.3：list类的定义 **************************/

	/**
	* @brief 双向循环链表模板类
	*		实现双向循环链表的基本功能：插入、删除、遍历、拷贝构造、赋值运算符等
	*		使用带头结点的循环链表结构，头节点不存储有效数据，方便边界处理
	*/

	template <class T>
	class list
	{
	private:
		/*--------------------------第一部分：定义类型别名--------------------------*/

		//重命名“list节点”的类型：list_node<T> ---> Node
		typedef list_node<T> Node;

		/*--------------------------第二部分：定义成员变量--------------------------*/

		Node* _head; //头节点指针（指向不存储有效数据的哨兵节点）
		size_t _size; //链表中有效元素的个数

	public:
		/*--------------------------第一部分：定义类型别名--------------------------*/

		/*--------------------第一种情况：当我们使用的是“单模板参数 + 两个迭代器模板”*/
		////1.重命名“普通迭代器（可读可写）”的类型：list_iterator<T> ---> iterator
		//typedef list_iterator<T> iterator;

		////2.重命名“常量迭代器（只读）”的类型：list_iterator<T> ---> const_iterator
		//typedef list_const_iterator<T> cont_iterator;


		/*--------------------第二种情况：当我们使用的是“三模板那参数 + 一个迭代器模板”*/

		//1.重命名“普通迭代器（可读可写）”的类型：list_iterator<T,T&,T*> ---> iterator
		typedef list_iterator<T, T&, T*> iterator;

		//2.重命名“常量迭代器（只读）”的类型：list_iterator<T,const T&, const T*> ---> const_iterator
		typedef list_iterator<T, const T&, const T*> const_iterator;


		/*--------------------------第二部分：定义迭代器接口--------------------------*/

		//1.实现：“返回指向首元节点的普通迭代器” ----> 头节点指向的第一个有效节点
		iterator begin()
		{
			///*---------方法一：有名对象---------*/
			//iterator it = (_head->_next);
			//return it;

			///*---------方法二：匿名对象---------*/
			//return iterator(_head->_next);

			/*---------方法三：隐式转换---------*/
			return _head->_next;
		}

		//2.实现：“返回指向尾后位置的普通迭代器” ---> 头节点
		iterator end()
		{
			return _head;
		}


		//3.实现：“返回指向首元节点的常量迭代器”
		const_iterator begin()const
		{
			return _head->_next;
			//return const_iterator(_head->_next);  // 显式构造 const_iterator
		}

		//4.实现：“返回指向尾后位置的常量迭代器”
		const_iterator end()const
		{
			return _head;
			//return const_iterator(_head);  // 显式构造 const_iterator
		}




		/*--------------------------第三部分：构造/赋值/析构--------------------------*/

		//1.实现：“空链表初始化函数”
		void empty_init()
		{
			//1.动态创建list的头节点
			_head = new Node;

			//2.初始化list的元素数量为0
			_size = 0;

			//3.初始化list的前驱后继指针
			//3.1：初始化_prev指针 ---> 头节点的next指向自己，构成空循环
			_head->_prev = _head;
			//3.2：初始化_next指针 ---> 头节点的prev指向自己，构成空循环
			_head->_next = _head;

		}


		//2.实现：“默认构造函数”
		list()
		{
			empty_init();
		}


		//3.实现：“初始化列表构造函数”
		list(initializer_list<T> il)
		{
			//1.首先初始化空链表
			empty_init();

			//2.循环遍历初始化列表
			for (auto& it : il)
			{
				//3.尾插遍历的到的每一个元素
				push_back(it);
			}
		}


		//4.实现：“拷贝构造函数”
		list(const list<T>& lt)
		{
			//1.初始化空链表
			empty_init();

			//2.遍历原链表，逐个尾插元素  ---> （利用push_back实现深拷贝）
			for (auto& it : lt)
			{
				push_back(it);
			}
		}


		//5.实现：“赋值运算符重载函数”
		list<T>& operator=(list<T> lt) //使用现代写法
		{
			swap(lt);      //交换当前对象与临时对象的数据

			return *this;  //返回当前对象（临时对象会自动析构，释放原资源）
		}


		//6.实现：“析构函数”
		~list()
		{
			//1.检查
			if (_head)
			{
				//2.清理
				clear();

				//3.释放
				delete _head;

				//4.置空
				_head = nullptr;
			}
		}


		/*--------------------------第四部分：容量相关的操作--------------------------*/
		size_t size()const
		{
			return _size;
		}

		bool empty()const
		{
			return _size == 0;
		}

		/*--------------------------第五部分：增删改查的修改操作--------------------------*/

		//1.实现：“清空链表的操作”
		void clear()  //注意：释放所有有效节点，不会释放内存空间，保留头节点
		{
			//1.获取首元节点的迭代器
			auto it = begin();

			//2.使用迭代器循环遍历每个节点并将其删除掉（除了头节点）
			while (it != end())
			{
				it = erase(it);   //注意：删除当前节点，并获取下一个节点的迭代器
			}
		}

		//2.实现：“交换两个链表的函数”
		void swap(list<T>& lt)
		{
			//1.交换头节点指针
			std::swap(_head, lt._head);

			//2.交换链表的元素的个数
			std::swap(_size, lt._size);
		}



		//3.实现：“尾插操作的函数”
		void push_back(const T& x)
		{
			/*-----------方法一：直接在list的尾部插入一个节点----------*/
			/*-----------------第一步：创建一个节点-----------------*/
			//Node* newNode = new Node(x);


			///*-----------------第二步：找到和插入节点相关的节点-----------------*/
			////2.1：头节点：我们不用特意的找，已经拥有指向list头节点的指针：_head
			////2.2：原尾节点：
			//Node* tail = _head->_prev;

			///*-----------------第三步：调整指针将新节点插入到：tail和_head之间-----------------*/
			//tail->_next = newNode;
			//newNode->_prev = tail;

			//newNode->next = _head;
			//_head->_prev = newNode;

			///*------------第四步：更新节点的个数------------*/
			//++_size;


			/*-----------方法二：间接调用insert在list的尾部插入一个节点----------*/
			insert(end(), x);	//在尾后位置（头节点前）插入新元素
		}

		//4.实现：“头插操作的函数”
		void push_front(const T& x)
		{
			insert(begin(), x);  //在首元节点前插入新元素
		}


		//5.实现：“在指定位置之前插入节点的函数”
		iterator insert(iterator pos, const T& x)
		{
			/*------------第一步：创建要插入的节点------------*/
			Node* newNode = new Node(x);

			/*------------第二步：找到和插入节点相关的节点------------*/
			//2.1：获取插入位置的节点
			Node* last = pos._node;
			//2.2：获取插入位置之前的节点
			Node* first = last->_prev;


			/*------------第三步：调整指针将新节点插入到：first和last之间------------*/
			first->_next = newNode;
			newNode->_prev = first;

			newNode->_next = last;
			last->_prev = newNode;


			/*------------第四步：更新节点的个数并返回“新节点的迭代器”------------*/
			++_size;
			return iterator(newNode);
		}


		//6.实现：“尾删操作的函数”
		void pop_back()
		{
			erase(--end());  //end()指向头节点，--end()指向最后一个元素
		}

		//7.实现：“头删操作的函数”
		void pop_front()
		{
			erase(begin());  //直接删除首元节点
		}

		//8.实现：“删除指定位置的节点的函数”
		iterator erase(iterator pos)
		{
			/*------------第一步：断言检查，不能删除end()位置的节点的头节点------------*/
			assert(pos != end());


			/*------------第二步：找到和删除节点相关的节点------------*/
			//2.1：获取要删除节点的前驱节点
			Node* first = pos._node->_prev;

			//2.2：获取要删除节点的后继节点
			Node* last = pos._node->_next;


			/*------------第三步：调整前驱和后继的指针，跳过待删除节点------------*/
			first->_next = last;
			last->_prev = first;


			/*------------第四步：释放待删除节点------------*/
			delete pos._node;

			/*------------第五步：更新节点的个数并返回“后继节点的迭代器”------------*/
			--_size;
			return iterator(last);
		}

	};




	/************************** 任务2.4：实现print_container的函数模板 **************************/


	template<class Container>
	void print_container(const Container& con)
	{
		/*--------------方法一：使用迭代器进行遍历list容器--------------*/
		//1.首先定义一个常量迭代器
		typename Container::const_iterator it = con.begin();

		//2.然后再使用迭代器循环遍历这个容器
		while (it != con.end())
		{
			//2.1：打印遍历到的每个节点的值
			cout << *it << " ";

			//2.2：让迭代器进行自增
			++it;

		}
		cout << endl;


		/*
		//--------------方法二：使用范围for循环遍历list容器--------------
		for (auto& it : con)
		{
			cout << it << " ";
		}
		cout << endl;
		*/
	}

}

/*-------------测试：list的“初始化列表”和“隐式类型转换”的功能-------------*/
/**
 * 测试常量链表的遍历
 * 接收一个常量list引用，验证在只读条件下能否正确遍历元素
 */
void func(const list<int>& lt) 
{
    // 调用打印函数，使用迭代器遍历容器元素
    print_container(lt);
}

void test_list5() 
{
    cout << "==========测试：list的“初始化列表”和“隐式类型转换”的功能==========" << endl;
    
    // 直接构造方式：使用初始化列表显式构造list对象
    // 调用list的initializer_list构造函数，将大括号内的元素依次插入链表
    list<int> lt1({ 1,2,3,4,5,6 });
    // 传递给接受常量引用的函数，验证常量迭代器是否正常工作
    func(lt1);

    // 隐式类型转换方式1：拷贝初始化
    // 使用赋值语法，但实际调用initializer_list构造函数
    // 编译器自动将右侧的初始化列表转换为list<int>临时对象，再拷贝构造lt2
    // 注意：如果list未定义initializer_list构造函数，此语句将无法编译
    list<int> lt2 = { 1,2,3,4,5,6,7,8 };
    
    // 隐式类型转换方式2：直接绑定到常量引用
    // 右侧的初始化列表先转换为list<int>临时对象
    // 再将该临时对象的生命周期延长到常量引用lt3的作用域
    // 临时对象的生命周期将持续到当前代码块结束
    const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };

    // 测试函数调用时的隐式转换
    // 实参直接使用初始化列表，编译器自动转换为list<int>临时对象
    // 传递给接受常量引用的函数参数
    // 等价于 func(list<int>({1,2,3,4,5,6}));
    func({ 1,2,3,4,5,6 });

    // 验证原始列表内容未被修改
    print_container(lt1);
}

测试文件：test.cpp

#include "list.h"

namespace mySpace
{
	/************************** 测试用结构体 **************************/
	struct AA
	{
		int _a1 = 1;        // 成员变量，默认初始化为1
		int _a2 = 1;        // 成员变量，默认初始化为1
	};


	/************************** 测试函数 **************************/

	/*-------------测试：list的“基本”的功能-------------*/

	void test_list01()
	{
		cout << "==========测试：list中存储自定义类型的变量==========" << endl;
		list<AA> lt;
		lt.push_back(AA());
		lt.push_back(AA());
		lt.push_back(AA());
		lt.push_back(AA());



		cout << "使用迭代器遍历list容器" << endl;
		//1.定义指向的list首元节点的迭代器
		list<AA>::iterator it = lt.begin();  //注意：迭代器类型的前面的域限定：list<AA>

		//2.使用迭代器循环遍历整个list容器
		while (it != lt.end())
		{
			//1.访问

			/*-----------第一种：使用“.运算符”访问结构体成员-----------*/
			//cout << (*it)._a1 << "," << (*it)._a2 << endl;

			/*-----------第二种：使用“->运算符”访问结构体成员-----------*/
			cout << it->_a1 << "," << it->_a2 << endl;

			/*-----------第三种：使用“operator->()重载函数”访问结构体成员-----------*/
			//cout << it.operator->()->_a1 << "," << it.operator->()->_a2 << endl;


			//2.移动
			++it;

		}
		cout << endl;
	}


	/*-------------测试：list的“迭代器”的功能-------------*/
	void test_list02()
	{
		cout << "==========测试：list的“迭代器”的功能==========" << endl;
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		cout << "链表初始内容为：" << endl;
		print_container(lt);

		cout << "使用迭代器遍历并修改使每个元素都+10后：" << endl;
		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			*it += 10;
			cout << *it << " ";
			++it;
		}
		cout << endl;

		cout << "使用范围for遍历链表" << endl;
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;

	}





	/*-------------测试：list的“插入和删除”的功能-------------*/
	void test_list03()
	{
		cout << "==========测试：list的“插入和删除”的功能==========" << endl;
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		cout << "链表初始内容为：" << endl;
		print_container(lt);

		/*----------------第一种的情况：list的头插----------------*/
		cout << "在链表的首元节点的位置处插入10，然后再将原先的第一个元素+100后：" << endl;
		list<int>::iterator it = lt.begin();

		lt.insert(it, 10);   //注意：insert操作后迭代器不失效
		*it += 100;
		print_container(lt);


		/*----------------第二种的情况：list的任意插----------------*/
		//1.获取首元节点的迭代器
		it = lt.begin();
		//2.定义偏移量
		int k = 3;
		//3.使用while循环进行偏移
		while (k--)
		{
			++it;   //移动迭代器到第4个元素（索引3，链表从0开始计数）
		}

		cout << "在索引为3的位置处插入30后：" << endl;
		lt.insert(it, 30);
		print_container(lt);




		cout << "删除链表的中值为偶数的节点后：" << endl;
		it = lt.begin();
		while (it != lt.end())
		{
			if (*it % 2 == 0)  //注意：erase操作后迭代器失效，需正确处理
			{
				it = lt.erase(it);  //删除偶数，返回下一个元素的迭代器
			}
			else
			{
				++it;
			}
		}
		print_container(lt);

	}


	/*-------------测试：list的“拷贝和赋值”的功能-------------*/
	void test_list04()
	{
		cout << "==========测试：list的“拷贝和赋值”的功能==========" << endl;
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		cout << "链表lt1为：" << endl;
		print_container(lt1);

		/*---------拷贝构造---------*/
		cout << "使用lt1拷贝构造的链表lt2为：" << endl;

		list<int> lt2(lt1);
		print_container(lt2);

		/*---------赋值操作---------*/
		list<int> lt3;
		lt3.push_back(10);
		lt3.push_back(20);
		lt3.push_back(30);
		lt3.push_back(40);
		cout << "链表lt3为：" << endl;
		print_container(lt3);
		cout << "用lt3为链表lt1赋值后lt1为：" << endl;
		lt1 = lt3;
		print_container(lt1);
	}



	/*-------------测试：list的“初始化列表”的功能-------------*/
	/**
	 * 测试常量链表的遍历
	 */
	void func(const list<int>& lt)
	{
		print_container(lt);
	}

	void test_list05()
	{
		cout << "==========测试：list的“初始化列表”的功能==========" << endl;

		/*----------------直接构造方式：使用初始化列表显式构造list对象----------------*/
		cout << "直接构造方式：list<int> lt1({ 1,2,3,4,5,6 });" << endl;
		list<int> lt1({ 1,2,3,4,5,6 });  //调用list的initializer_list构造函数，将大括号内的元素依次插入链表
		func(lt1);  //传递给接受常量引用的函数，验证常量迭代器是否正常工作



		/*----------------隐式类型转换方式1：拷贝初始化----------------*/
		cout << "隐式类型转换方式1：list<int> lt2 = { 1,2,3,4,5,6,7,8 };" << endl;
		list<int> lt2 = { 1,2,3,4,5,6,7,8 };
		/*
		* 使用赋值语法，但实际调用initializer_list构造函数
		*       1.编译器自动将右侧的初始化列表转换为list<int>临时对象
		*       2.再拷贝构造lt2
		*/
		func(lt2);



		/*----------------隐式类型转换方式2：直接绑定到常量引用----------------*/
		cout << "隐式类型转换方式2：const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };" << endl;
		const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };
		/*
		 *    1.右侧的初始化列表先转换为list<int>临时对象
		 *    2.再将该临时对象的生命周期延长到常量引用lt3的作用域
		 * 注：临时对象的生命周期将持续到当前代码块结束
		 */
		func(lt3);



		//测试函数调用时的隐式转换
		cout << "测试函数调用时的隐式转换：func({ 1,2,3,4,5,6 })" << endl;
		func({ 1,2,3,4,5,6 });
		/*
		 *    1.实参直接使用初始化列表，编译器自动转换为list<int>临时对象
		 *    2.传递给接受常量引用的函数参数
		 * 注：等价于 func(list<int>({1,2,3,4,5,6}));
		 */


		cout << "使用print_container函数分别打印这三个链表：" << endl;
		print_container(lt1);
		print_container(lt2);
		print_container(lt3);

	}
}

/************************** 主函数：测试入口 **************************/
int main() 
{
   
    mySpace::test_list01();
    mySpace::test_list02();
    mySpace::test_list03();
    mySpace::test_list04();
    mySpace::test_list05();

    return 0;
}

运行结果：

------------核心问题深究------------

一、迭代器失效问题

1. list容器中哪些操作会导致迭代器失效？

在 C++ 中，list 是基于双向链表实现的容器，其迭代器失效情况相对简单，主要与删除操作相关，插入操作一般不会导致迭代器失效 。

---

1. 删除操作（erase）

当使用 list 的 erase 成员函数删除元素时，仅指向被删除节点的迭代器会失效，其他迭代器不受影响 。

• 核心原理：list 的底层是双向链表，节点通过指针连接。

  • 删除一个节点时，只会断开该节点与前后节点的链接，其他节点的位置和指针不受影响。
  • 因此，只有指向被删除节点的迭代器会因为所指节点被销毁而失效，指向其他节点的迭代器仍能正常使用。

• 使用示例：

   list<int> mylist = {1, 2, 3, 4};
  
   auto it = mylist.begin(); // it 指向 1
  
   mylist.erase(it); // 删除 1，it 失效
   // 此时，指向 2、3、4 的迭代器仍有效
   auto it2 = mylist.begin(); // it2 指向 2，可正常使用
  

• 解决方法：erase 函数会返回被删除节点的后继节点的迭代器，可利用该返回值更新失效的迭代器，继续遍历或操作

   list<int> mylist = {1, 2, 3, 4};
    
   auto it = mylist.begin();
    
   while (it != mylist.end()) 
   {
       // 先通过 it++ 保存下一个节点的迭代器，再删除当前节点
       it = mylist.erase(it); 
       // it 现在指向被删除节点的后继，可继续循环
   }
  

---

2. 插入操作（insert、push_front、push_back 等）

由于 list 是链表结构，插入新节点时，只需调整相邻节点的指针，不会移动其他节点的位置

因此，插入操作不会导致任何迭代器失效（包括指向插入位置附近节点的迭代器）

• 使用示例：

  list<int> mylist = {1, 3, 4};
  auto it = mylist.begin();
  
  ++it; // it 指向 3
  
  // 在 3 前插入 2，it 仍指向 3（节点 3 未被移动，指针未变）
  mylist.insert(it, 2); 
  // 遍历结果：1 2 3 4，所有迭代器（包括原来指向 3 的 it）都有效
  

---

3. 清空操作 （clear）

• clear 会删除 list 中所有元素，所有指向该 list 元素的迭代器都会失效（因为没有元素可指向了）
• 调用 clear 后，若再使用之前的迭代器，会导致未定义行为

---

4. 赋值 / 交换操作 （assign、swap 等）

• assign：会替换 list 的内容，原 list 所有元素被删除，原迭代器全部失效，需重新获取新 list 的迭代器。
• swap：交换两个 list 的内容后，原 list 的迭代器会指向另一个 list 的元素（逻辑上 “转移” 了指向），若原 list 被销毁或内容改变，需注意迭代器的有效性。

案例一：erase造成的迭代器失效

#include <iostream>
#include <list>
using namespace std;

// 错误示例：迭代器失效问题
void TestListIterator01()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> lt(array, array + sizeof(array) / sizeof(array[0]));

    auto it = lt.begin();
    while (it != lt.end())
    {

        lt.erase(it);
        ++it; //未定义行为：对失效迭代器进行递增操作

        //错误分析：
        // erase会删除it指向的节点，并使it失效
        // 失效的迭代器不能再进行++操作
    }
}

// 正确示例：处理迭代器失效
void TestListIterator02()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> lt(array, array + sizeof(array) / sizeof(array[0]));

    auto it = lt.begin();
    while (it != lt.end())
    {
        /*-------方法1：利用后置++的特性-------*/
 
        //lt.erase(it++);

        //正确分析：
        // it++ 返回旧值（当前有效迭代器）
        // erase删除旧值指向的节点
        // it 被递增为下一个有效节点

        /*-------方法2：显式接收erase返回的迭代器-------*/

        //it = lt.erase(it); // erase返回下一个有效迭代器
    }
}


int main()
{
    //TestListIterator01();
    TestListIterator02();


    return 0;
}

二、反向迭代器实现问题

通过前面的例子可知：

• 反向迭代器的 ++ 操作，对应正向迭代器的 -- 操作
• 反向迭代器的 -- 操作，对应正向迭代器的 ++ 操作

基于此，反向迭代器的实现可借助正向迭代器来完成，具体来说：

反向迭代器内部可包含一个正向迭代器，通过对该正向迭代器的接口进行封装、调整逻辑，就能实现反向迭代器的功能 。

//反向迭代器适配器：将正向迭代器转换为反向迭代器
template<class Iterator>
class ReverseListIterator
{
private:
    Iterator _it;  //底层维护的正向迭代器

public:
    /*--------------------------第一部分：定义类型别名--------------------------*/
    
    //1.重命名“list正向迭代器中的引用类型”：Iterator::Ref ---> Ref
    typedef typename Iterator::Ref Ref;

    //2.重命名“list正向迭代器的指针类型”：Iterator::Ptr ---> Ptr
    typedef typename Iterator::Ptr Ptr;

    //3.重命名“list反向迭代器”的类型：ReverseListIterator ---> Self
    typedef ReverseListIterator<Iterator> Self;

    //注意：
    //1.此处typename的作用是明确告诉编译器，Ref是“Iterator类中的类型”，而不是“静态成员变量”
    //2.否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
    //3.因为静态成员变量也是按照 “类名::静态成员变量名” 的方式访问的

    /*--------------------------第二部分：定义成员变量--------------------------*/

    //1.实现：“有参数构造函数”
    ReverseListIterator(Iterator it) 
        : _it(it)  //用正向迭代器初始化反向迭代器
    {}

    //2.实现：“*运算符的重载函数”
    Ref operator*()  //注意：返回当前位置前一个元素的引用（反向迭代器的特性）
    {
        //1.创建临时迭代器
        Iterator temp(_it);

        //2.前移一位（注意：这是正向迭代器的--）
        --temp;  

        //3.返回临时迭代器的解引用
        return *temp; 
    }

    //3.实现：“->运算符的重载函数”
    Ptr operator->()  //注意：返回当前位置前一个元素的指针
    { 
        return &(operator*());  //复用解引用运算符，取地址
    }


    //4.实现：“前置++运算符的重载函数”
    Self& operator++()  //（反向迭代器递增 = 正向迭代器递减）
    {
        --_it;   //注意：调整底层正向迭代器向前移动
        return *this;
    }

    //5.实现：“前置--运算符的重载函数”
    Self& operator--()  //（反向迭代器递减 = 正向迭代器递增）
    {
        ++_it;   //注意：调整底层正向迭代器向后移动
        return *this;
    }

    //6.实现：“后置++运算符的重载函数”
    Self operator++(int)
    {
        Self temp(*this);

        --_it;  //注意：（底层正向迭代器递减）
        return temp;
    }

    //7.实现：“后置--运算符的重载函数”
    Self operator--(int) 
    {
        Self temp(*this);

        ++_it;  //注意：（底层正向迭代器递增）
        return temp;
    }

    //8.实现：“==运算符的重载函数”
    bool operator==(const Self& lt) const
    {
        return _it == lt._it;  //比较底层正向迭代器
    }


    //8.实现：“!=运算符的重载函数”
    bool operator!=(const Self& lt) const 
    { 
        return _it != lt._it;  //比较底层正向迭代器
    }
};

三、vector和list的选择问题

1. STL中的容器分为哪些种类？

C++ STL（标准模板库）中的容器主要分为以下 三大类 ，每类都有独特的特性和适用场景：

序列容器（Sequence Containers）

• vector（动态数组）
• list（双向链表）
• deque（双端队列）
• forward_list（单向链表，C++11 新增）
• array（C++11 新增，固定大小数组）

---

关联容器（Associative Containers）

• 基于红黑树（有序）
  • set（有序集合）
  • multiset（有序多重集合）
  • map（有序键值对映射）
  • multimap（有序多重键值对映射）
• 基于哈希表（无序)
  • unordered_set（无序集合）
  • unordered_multiset（无序多重集合）
  • unordered_map（无序键值对映射）
  • unordered_multimap（无序多重键值对映射）

---

容器适配器（Container Adapters）

• stack（栈，LIFO：后进先出）
• queue（队列，FIFO：先进先出）
• priority_queue（优先队列）

一、序列容器

序列容器：是元素按插入顺序存储，强调 “线性排列”，支持位置相关的插入、访问操作。

---

1. vector（动态数组）：底层是动态分配的连续内存

• 优势：
  • 尾部插入/删除高效（push_back/pop_back 为 O(1) ）
  • 支持随机访问（通过下标 [] 或 at()，时间复杂度 O(1) ）
• 劣势：
  • 中间和头部插入/删除 效率低（需移动元素，O(n) ）
  • 扩容时可能触发内存重新分配（拷贝旧数据）
• 适用场景：需频繁随机访问、尾部操作
  • 例如：存储一组可按索引快速查询的数据（如：游戏存档列表）

---

2. list（双向链表）：底层是双向链表，节点通过指针连接，非连续内存

• 优势：
  • 任意位置插入/删除高效（只需调整指针，O(1) ）
  • 内存按需分配（无需预分配或扩容）
• 劣势：
  • 不支持随机访问（需遍历查找，O(n) ）
  • 额外存储指针增加内存开销
• 适用场景：需频繁插入 / 删除
  • 例如：实现 Undo/Redo 历史记录、链表结构的业务逻辑

---

3. deque（双端队列）：底层是分段连续内存，逻辑上视为连续，实际由多个缓冲区拼接

• 优势：
  • 头部和尾部插入/删除高效（push_front/pop_front、push_back/pop_back 均为 O(1) ）
  • 也支持随机访问（但效率略低于 vector ）
• 劣势：
  • 中间插入/删除仍需移动元素（O(n) ），
  • 内存管理比 vector 复杂
• 适用场景：需频繁在头尾操作数据
  • 例如：实现队列（queue 适配器默认用 deque 做底层）

---

4. forward_list（单向链表，C++11 新增）：底层是单向链表，仅支持正向遍历

• 优势：
  • 任意位置插入/删除操作（除尾部外）效率与 list 相当
  • 比 list 更节省内存（少一个指针）
• 劣势：
  • 不支持反向遍历（无 rbegin/rend ）
  • 尾部操作需遍历到末尾（效率低）
• 适用场景：内存敏感且只需正向遍历的场景
  • 例如：简单的单向链表结构

---

5. array（C++11 新增，固定大小数组）：底层是静态数组（大小编译期确定，不可扩容）

• 优势：
  • 类型安全（替代原生数组）
  • 支持随机访问
  • 无动态扩容开销
• 劣势：
  • 大小固定（初始化后无法改变）
• 适用场景：需固定大小数组且希望用 STL 风格接口
  • 例如： begin/end 、迭代器等的场景

二、关联容器

关联容器：是元素按键自动排序或哈希组织，强调 “高效查找”，通常用于快速查询、去重等场景。

• 常用容器底层多基于红黑树或哈希表

---

1. 基于红黑树（有序）

• set（有序集合）：存储唯一键（key），按 key 自动按升序排序（默认用 < 比较，可自定义）
  • 核心特性：插入时自动去重，查找、插入、删除均为 O(logn)（红黑树保证平衡）
  • 适用场景：需自动排序、去重的集合
    • 例如：存储学生学号，保证无重复
• multiset（有序多重集合）：类似 set，但允许键重复（插入重复键时会保留，按序排列）
  • 核心特性：查找、插入、删除仍为 O(logn)
  • 适用场景：需保留重复元素但需有序的场景
    • 例如：统计词频后按词频排序

++++++++++++++++++++++++++++++++++++++++++++

• map（有序键值对映射）：存储唯一键值对（key-value ），按 key 自动升序排序
  • 核心特性：key 唯一，通过 key 查找 value 高效（O(logn) ）
  • 适用场景：常用于字典、配置映射等场景
    • 例如：存储学生学号→姓名
• multimap（有序多重键值对映射）：类似 map，但允许键 key 重复（同一个 key 可对应多个 value ）
  • 核心特性：按 key 排序，查找、插入为 O(log n) ，
  • 适用场景：适用于一对多映射
    • 例如：存储日期→当日事件列表

---

2. 基于哈希表（无序，C++11 新增，前缀 unordered_ ）

• unordered_set（无序集合）：底层是哈希表，存储唯一键，不保证有序
  • 核心特性：平均查找、插入、删除为 O(1)（哈希冲突时退化为 O(n) ），比 set 更高效（无需排序开销）
  • 适用场景：需去重但无需排序的场景
    • 例如：统计网页关键词，只需存在性判断
• unordered_multiset（无序多重集合）：类似 unordered_set，但允许键 key 重复

++++++++++++++++++++++++++++++++++++++++++++

• 核心特性：插入、查找平均 O(1)
• unordered_map（无序键值对映射）：底层是哈希表，存储唯一 key-value，不保证有序
  • 核心特性：通过 key 查找 value 平均 O(1) ，是实际开发中替代 map 的高频选择
  • 适用场景：需去重但无需排序的场景
    • 例如：缓存系统、快速键值查询
• unordered_multimap（无序多重键值对映射）：类似 unordered_map，但允许键 key 重复
  • 核心特性：平均操作 O(1)

三、容器适配器

容器适配器：是基于上述容器（序列容器为主）封装接口，屏蔽部分功能、突出特定行为，简化常用场景的使用。

---

1. stack（栈，LIFO：后进先出）：底层默认基于 deque（也可指定 vector 或 list ）

• 封装接口：
  • push（入栈，默认调 push_back ）
  • pop（出栈，默认调 pop_back ）
  • top（访问栈顶，默认调 back ）
• 适用场景：需后进先出逻辑
  • 例如：函数调用栈模拟、表达式求值

---

2. queue（队列，FIFO：先进先出）：底层默认基于 deque（也可指定 list ）

• 封装接口：
  • push（入队，默认调 push_back ）
  • pop（出队，默认调 pop_front ）
  • front/back（访问队首 / 队尾）
• 适用场景：需先进先出逻辑
  • 例如：任务队列、消息队列

---

3. priority_queue（优先队列）：底层默认基于 vector（用堆算法维护，逻辑上是完全二叉树）

• 核心特性：元素按 “优先级” 自动排序（默认大顶堆，最大元素优先出队；可自定义比较规则）
• 封装接口：
  • push（插入后调整堆，O(log n) ）
  • pop（弹出堆顶，O(log n) ）
  • top（访问堆顶，O(1) ）
• 适用场景：需按优先级处理任务
  • 例如：操作系统进程调度、事件驱动框架

2. STL容器怎么选？

总结（选型简易指南）

• 随机访问 + 尾部操作 → vector
• 任意位置插入 / 删除 → list
• 头尾高效操作 → deque

---

• 自动排序 + 唯一键/键值对 → set/map
• 高效查找（无需排序） + 唯一键/键值对 → unordered_set/unordered_map

---

• 特定逻辑（栈 / 队列 / 优先队列） → 对应适配器（stack/queue/priority_queue ）

3. vector和list的核心差异有什么？

总结：分类对比展示 vector 和 list 的核心差异：

------------代码片段剖析------------

片段一：list迭代器的模板参数为什么是三个？

template <class T, class Ref, class Ptr>
struct list_iterator
{
	/*--------------------定义类型别名--------------------*/

	//1.重命名“list节点”的类型：list_node<T> ---> Node
	typedef list_node<T> Node;

	//2.重命名“list迭代器”的类型：list_iterator<T,Ref,Ptr> ---> Self
	typedef list_iterator<T, Ref, Ptr> Self;

	/*--------------------定义成员变量--------------------*/

	Node* _node; //迭代器内部存储的节点指针，指向当前位置


	/*--------------------定义成员函数--------------------*/

	//1.实现：“有参构造函数”
	list_iterator(Node* node) :
		_node(node)
	{}
}

在 C++ 标准库中，list容器的迭代器模板参数设计为三个（通常是：T, Ref, Ptr），主要是为了支持 常量迭代器 和 非常量迭代器 的区分。

这种设计允许通过模板参数的不同组合，让同一套迭代器代码同时服务于普通迭代器和常量迭代器，避免代码冗余。

---

核心原因解析：

1. 分离值类型、引用类型和指针类型

• 普通迭代器：需要返回T&和T*（可修改元素）
• 常量迭代器：需要返回const T&和const T*（不可修改元素）

通过三个模板参数，可以灵活指定引用和指针的常量性：

• Ref = T&，Ptr = T* 时，是普通迭代器。
• Ref = const T&，Ptr = const T* 时，是常量迭代器。

---

2. 避免代码重复

如果不使用三个参数，需要为普通迭代器和常量迭代器分别编写两套几乎完全相同的代码

如下面使用传统方式实现普通/常量迭代器的代码中，list_iterator和list_const_iterator存在大量重复，但是通过模板参数化Ref和Ptr，可以复用同一套迭代器实现

/*----------------------传统方式（代码冗余）----------------------*/
// 普通迭代器
template <class T>
struct list_iterator 
{
    T& operator*() { /*...*/ }
    T* operator->() { /*...*/ }
};

// 常量迭代器
template <class T>
struct list_const_iterator 
{
    const T& operator*() { /*...*/ }
    const T* operator->() { /*...*/ }
};


/*----------------------模板参数优化方式----------------------*/
template <class T, class Ref, class Ptr>
struct list_iterator 
{
    Ref operator*()  // 可能是 T& 或 const T&
    { 
        return _node->_data; 
    }  

    Ptr operator->() // 可能是 T* 或 const T*
    { 
        return &_node->_data; 
    } 
};

3. 实现容器的const_iterator

当容器对象被声明为const时，调用begin()/end()应返回常量迭代器：

const list<int> clst;

auto it = clst.begin();  // 必须返回const_iterator

通过三个参数的模板设计，容器可以根据自身是否为const来实例化不同的迭代器类型：

template <typename T>
class list
{
public:
    //using iterator = list_iterator<T, T&, T*>;
    //using const_iterator = list_iterator<T, const T&, const T*>;

    //1.重定义普通迭代器的类型：list_iterator<T, T&, T*> ---> iterator
    typedef list_iterator<T, T&, T*> iterator;

    //2.重定义常量迭代器的类型：list_iterator<T, const T&, const T*> ---> const_iterator
    typedef list_iterator<T, const T&, const T*> const_iterator;

    iterator begin()
    {
        return iterator(head->_next);
    }

    const_iterator begin() const  // 关键：返回const_iterator
    {
        return const_iterator(head->_next);
    }
};

1. 为什么不能只用一个模板参数？

如果只使用T作为模板参数，迭代器内部无法区分返回值的常量性：

template <class T>
struct list_iterator
{
       T& operator*() // 无法适配const T&
       {
           return _node->_data;
       }
};

此时：若要支持常量迭代器，必须单独编写一个list_const_iterator类，导致代码冗余。

---

总结：

三个模板参数的设计是 C++ 标准库中实现迭代器的经典技巧。

通过分离值类型、引用类型和指针类型，在保持代码复用的同时，优雅地区分 普通迭代器和常量迭代器。

这种设计使容器能够根据使用场景自动选择正确的迭代器类型，提供一致且安全的接口。

片段二：为什么要实现空链表的初始化函数?

//1.实现：“空链表初始化函数”
void empty_init()
{
	//1.动态创建list的头节点
	_head = new Node;

	//2.初始化list的元素数量为0
	_size = 0;

	//3.初始化list的前驱后继指针
	//3.1：初始化_prev指针 ---> 头节点的next指向自己，构成空循环
	_head->_prev = _head;
	//3.2：初始化_next指针 ---> 头节点的prev指向自己，构成空循环
	_head->_next = _head;
}


//2.实现：“默认构造函数”
list()
{
	empty_init();
}


//3.实现：“初始化列表构造函数”
list(initializer_list<T> il)
{
	//1.首先初始化空链表
	empty_init();

	//2.循环遍历初始化列表
	for (auto& it : il)
	{
		//3.尾插遍历的到的每一个元素
		push_back(it);
	}
}


//4.实现：“拷贝构造函数”
list(const list<T>& lt)
{
	//1.初始化空链表
	empty_init();

	//2.遍历原链表，逐个尾插元素  ---> （利用push_back实现深拷贝）
	for (auto& it : lt)
	{
		push_back(it);
	}
}

在实现双向循环链表时，空链表初始化函数（如：empty_init()）的设计是一种常见的代码复用策略，之所以使用它主要出于以下几个原因：

---

1. 避免构造函数代码重复

• 多个构造函数（如：默认构造函数、初始化列表构造函数、拷贝构造函数）都需要将链表初始化为空状态。

• 如果不抽取公共逻辑，每个构造函数都要重复实现相同的初始化代码。

  // 示例：若不使用empty_init()，默认构造函数需重复实现初始化
  list() 
  {
      _head = new Node;
      _size = 0;
      _head->_prev = _head;
      _head->_next = _head;
  }
  
  // 初始化列表构造函数也需重复相同代码
  list(initializer_list<T> il) 
  {
      _head = new Node;
      _size = 0;
      _head->_prev = _head;
      _head->_next = _head;
      // ...后续代码
  }
  

总结：通过抽取empty_init()，所有构造函数只需调用该函数一次，减少代码冗余。

---

2. 保证初始化逻辑一致性

链表的空状态有严格的定义：

• 头节点的_prev和_next指针必须指向自身，形成循环
• 元素数量_size必须为 0

若分散在多个构造函数中实现，可能因疏忽导致某个构造函数的初始化逻辑不完整（如：忘记设置循环指针），引发难以调试的错误。

集中到一个函数中实现可以确保所有构造函数的初始化行为一致。

---

3. 便于维护和修改

如果后续需要调整空链表的初始化方式（如：添加新的成员变量初始化），只需修改empty_init()一处，而不必改动所有构造函数。

// 假设后续添加了一个新的成员变量_alloc用于内存分配
void empty_init() 
{
    _head = new Node;
    _size = 0;

    _alloc = std::allocator<T>();  // 新增初始化逻辑

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

---

4. 支持拷贝操作的正确实现

• 在拷贝构造函数中，必须先将新对象初始化为空链表，再逐个插入原链表的元素：
• 若不调用empty_init()，直接插入元素会导致未初始化的头节点指针指向随机内存，引发崩溃。

list(const list<T>& lt) 
{
    empty_init();  // 关键：先初始化为空链表

    for (auto& it : lt) 
    {
        push_back(it);
    }
}

片段三：怎么处理依赖名称问题？

template<class Container>
void print_container(const Container& con)
{
	/*--------------方法一：使用迭代器进行遍历list容器--------------*/
	//1.首先定义一个常量迭代器
	typename Container::const_iterator it = con.begin();

	//2.然后再使用迭代器循环遍历这个容器
	while (it != con.end())
	{
		//2.1：打印遍历到的每个节点的值
		cout << *it << " ";

		//2.2：让迭代器进行自增
		++it;

	}
	cout << endl;
}

在 C++ 模板编程中：

typename关键字：用于告诉编译器某个 嵌套名称 是一个类型，而非静态成员或枚举值

• 所以上面的代码中，typename Container::const_iterator it 必须使用 typename

原因如下：

1. 依赖名称与非依赖名称的区分

在模板中，编译器处理依赖名称时需要特殊规则。

依赖名称是指依赖于模板参数的名称，例如：

• Container：是模板参数
• Container::const_iterator：是依赖于 Container 的嵌套名称（所以这里的Container::const_iterator就是依赖名称）

编译器在实例化模板前，无法确定 Container::const_iterator 是一个类型、静态成员变量还是枚举值

---

2. 默认假设与显式类型声明

C++ 标准规定，默认情况下，依赖名称不被视为类型

因此：如果不使用 typename，编译器会将 Container::const_iterator 解释为一个值（如：静态变量或枚举），而非类型。

Container::const_iterator it;           // 错误：默认假设const_iterator是静态成员
typename Container::const_iterator it;  // 正确：显式声明const_iterator是类型

---

3. 编译器实例化时的解析需求

模板在编译时分为两个阶段：

1. 定义阶段：编译器只检查语法，不实例化模板。此时无法确定 Container::const_iterator 的性质。
2. 实例化阶段：当模板被调用（如：print_container(list<int>)）时，编译器才知道 Container 的具体类型。

总结：使用 typename 是为了在定义阶段解决类型解析的歧义，确保编译通过。

---

4. 例外情况

• 只有当嵌套名称是依赖类型时，才需要 typename ，例如：

template <typename T>
struct Example 
{
   static const int value = 42;  // 静态成员变量
   typedef T type;               // 类型别名

   void func() 
   {
       type x;        //不需要typename，因为type不依赖其他模板参数，type是Example的成员
       T::type* ptr;  //需要typename，因为T::type是依赖于模板参数 T 的嵌套名称，编译器默认不认为它是类型
   }
};

---

总结：

在上面的代码中，typename Container::const_iterator it 的 typename 是必需的，因为：

• Container::const_iterator 是依赖于模板参数 Container 的嵌套名称。
• 编译器默认不将依赖名称视为类型，需用 typename 显式声明。
• 这一规则确保模板在实例化前能正确解析类型，避免编译错误。