深入解析C++ STL链表（List）模拟实现

目录

一、需要实现的三个类及其成员函数接口

二、结点类的模拟实现

构造函数

三、迭代器类的模拟实现

1、迭代器类的作用

2、迭代器类模板参数说明

3、构造函数

4、前置++运算符重载

5、后置++运算符重载

6、前置 -- 运算符重载

7、后置 -- 运算符重载

8、==运算符重载

9、重载 != 运算符

10、解引用运算符的重载

11、->运算符的重载

四、List 模拟实现

1、默认成员函数

构造函数

拷贝构造函数

赋值运算符重载函数

传统写法

现代写法

析构函数

2、迭代器相关函数：begin和end

3、访问容器相关函数

front()和back()

4、插入与删除函数

insert函数

erase 函数

push_back 和 pop_back 函数

push_front 和 pop_front 函数

5、其他函数

size

resize

clear

empty

swap

五、测试代码

六、vector 与 list 的对比

关键总结：

七、为什么 list 的插入不会使迭代器失效，而删除仅影响当前迭代器？

1、list 插入不会使迭代器失效的原因

2、list 删除仅影响当前迭代器的原因

3、对比 vector 的迭代器失效

4、总结

---

一、需要实现的三个类及其成员函数接口

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>
#include <cassert>
#include <vector>namespace hmz 
{template<class T>struct _list_node{//构造函数_list_node(const T& val = T()):_val(val), _prev(nullptr), _next(nullptr){}//成员变量T _val;                 //数据域_list_node<T>* _next;   //后继指针_list_node<T>* _prev;   //前驱指针};//模拟实现list迭代器template<class T, class Ref, class Ptr>struct _list_iterator{typedef _list_node<T> node;typedef _list_iterator<T, Ref, Ptr> self;//构造函数_list_iterator(node* pnode):_pnode(pnode){}//各种运算符重载函数// 前置++self operator++(){_pnode = _pnode->_next; // 指针指向下一个结点return *this;          // 返回更新后的指针}//前置--self operator--(){_pnode = _pnode->_prev; //让结点指针指向前一个结点return *this; //返回自减后的结点指针}// 后置++self operator++(int){self tmp(*this);       // 保存当前指针状态_pnode = _pnode->_next; // 指针指向下一个结点return tmp;            // 返回之前的指针}//后置--self operator--(int){self tmp(*this); //记录当前结点指针的指向_pnode = _pnode->_prev; //让结点指针指向前一个结点return tmp; //返回自减前的结点指针}bool operator==(const self& s) const{return _pnode == s._pnode; //判断两个结点指针指向是否相同}bool operator!=(const self& s) const{return _pnode != s._pnode;  // 检查两个节点指针是否指向不同地址}Ref operator*(){return _pnode->_val; // 返回节点指针所指向节点的数据}Ptr operator->(){return &_pnode->_val; // 返回结点指针所指数据的地址}//成员变量node* _pnode; //一个指向结点的指针};//模拟实现listtemplate<class T>class list{public:typedef _list_node<T> node;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(const list<T>& lt){_head = new node; //申请一个头结点_head->_next = _head; //头结点的后继指针指向自己_head->_prev = _head; //头结点的前驱指针指向自己for (const auto& e : lt){push_back(e); //将容器lt当中的数据一个个尾插到新构造的容器后面}}//传统写法list<T>& operator=(const list<T>& lt){if (this != &lt) //避免自己给自己赋值{clear(); //清空容器for (const auto& e : lt){push_back(e); //将容器lt当中的数据一个个尾插到链表后面}}return *this; //支持连续赋值}// 析构函数~list(){clear();      // 清空容器delete _head; // 释放头节点_head = nullptr; // 重置头指针}//迭代器相关函数iterator begin(){// 返回头结点下一个结点构造的普通迭代器return iterator(_head->_next);}iterator end(){// 返回头结点构造的普通迭代器return iterator(_head);}const_iterator begin() const{// 返回头结点下一个结点构造的const迭代器return const_iterator(_head->_next);}const_iterator end() const{// 返回头结点构造的const迭代器return const_iterator(_head);}//访问容器相关函数T& front(){return *begin(); // 返回首元素的引用}T& back(){return *(--end()); // 返回末元素的引用}const T& front() const{return *begin(); // 返回首元素的const引用}const T& back() const{return *(--end()); // 返回末元素的const引用}//插入、删除函数//插入函数void insert(iterator pos, const T& x){assert(pos._pnode); //检测pos的合法性node* cur = pos._pnode; //迭代器pos处的结点指针node* prev = cur->_prev; //迭代器pos前一个位置的结点指针node* newnode = new node(x); //根据所给数据x构造一个待插入结点//建立newnode与cur之间的双向关系newnode->_next = cur;cur->_prev = newnode;//建立newnode与prev之间的双向关系newnode->_prev = prev;prev->_next = newnode;}//删除函数iterator erase(iterator pos){assert(pos._pnode); //检测pos的合法性assert(pos != end()); //删除的结点不能是头结点node* cur = pos._pnode; //迭代器pos处的结点指针node* prev = cur->_prev; //迭代器pos前一个位置的结点指针node* next = cur->_next; //迭代器pos后一个位置的结点指针delete cur; //释放cur结点//建立prev与next之间的双向关系prev->_next = next;next->_prev = prev;return iterator(next); //返回所给迭代器pos的下一个迭代器}// 尾插操作void push_back(const T& x){insert(end(), x); // 在尾节点位置插入新元素}// 尾删操作void pop_back(){erase(--end()); // 删除尾节点}// 头插操作void push_front(const T& x){insert(begin(), x); // 在链表头部插入新元素}// 头删操作void pop_front(){erase(begin()); // 删除链表首元素}//其他函数size_t size() const{size_t sz = 0; //统计有效数据个数const_iterator it = begin(); //获取第一个有效数据的迭代器while (it != end()) //通过遍历统计有效数据个数{sz++;it++;}return sz; //返回有效数据个数}void resize(size_t n, const T& val = T()){iterator i = begin(); //获取第一个有效数据的迭代器size_t len = 0; //记录当前所遍历的数据个数while (len < n && i != end()){len++;i++;}if (len == n) //说明容器当中的有效数据个数大于或是等于n{while (i != end()) //只保留前n个有效数据{i = erase(i); //每次删除后接收下一个数据的迭代器}}else //说明容器当中的有效数据个数小于n{while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n{push_back(val);len++;}}}void clear(){iterator it = begin();while (it != end())  // 逐个删除元素{it = erase(it);}}void swap(list<T>& lt){std::swap(_head, lt._head);  // 调用全局swap函数交换头指针}private:node* _head; //指向链表头结点的指针};
}

---

二、结点类的模拟实现

我们经常说list在底层实现时就是一个链表，更准确来说，list实际上是一个带头双向循环链表。

        因此，我们若要实现list，则首先需要实现一个结点类。而一个结点需要存储的信息有：数据、前一个结点的地址、后一个结点的地址，于是该结点类的成员变量也就出来了（数据、前驱指针、后继指针）。

        而对于该结点类的成员函数来说，我们只需实现一个构造函数即可。因为该结点类只需要根据数据来构造一个结点即可，而结点的释放则由list的析构函数来完成。

构造函数

        结点类的构造函数直接根据所给数据构造一个结点即可，构造出来的结点的数据域存储的就是所给数据，而前驱指针和后继指针均初始化为空指针即可。

//构造函数
_list_node(const T& val = T()):_val(val), _prev(nullptr), _next(nullptr)
{}

注意： 若构造结点时未传入数据，则默认以list容器所存储类型的默认构造函数所构造出来的值为传入数据。

---

三、迭代器类的模拟实现

1、迭代器类的作用

        在之前模拟实现string和vector时，我们并未专门实现迭代器类，那么为什么在实现list时需要单独设计迭代器类呢？

        原因在于string和vector的数据存储在连续的内存空间中，通过指针的自增、自减和解引用操作就能直接访问对应位置的数据，因此它们的迭代器可以直接使用原生指针。

        而list的情况不同：它的各个节点在内存中的分布是随机的，不连续的。仅靠节点指针的自增、自减和解引用操作无法正确访问数据。

        迭代器的核心价值在于：它让使用者无需了解容器的底层实现细节，只需通过统一简单的方式就能访问容器数据。

        由于list的节点指针无法直接满足迭代器的要求，我们需要对其进行封装，通过重载运算符来调整指针的行为。这样就能像使用string和vector的迭代器一样操作list的迭代器。例如，list迭代器的自增操作背后实际执行的是p = p->next语句，但使用者无需关心这个细节。

总结：list迭代器类本质上是对节点指针的封装，通过运算符重载使其行为与普通指针一致（比如自增操作会自动指向下一个节点）。

2、迭代器类模板参数说明

在迭代器类的模板参数列表中，为什么需要三个模板参数？

template<class T, class Ref, class Ptr>

在list的模拟实现中，我们定义了两个迭代器类型：

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;

可以看出，Ref和Ptr分别代表引用类型和指针类型。这样设计可以实现：

1. 使用普通迭代器时，编译器实例化普通迭代器对象
2. 使用const迭代器时，编译器实例化const迭代器对象

        如果只使用单一模板参数，就无法有效区分普通迭代器和const迭代器的不同行为。三个模板参数的设计提供了这种区分能力。

3、构造函数

        迭代器类实际上就是对结点指针进行了封装，其成员变量就只有一个，那就是结点指针，其构造函数直接根据所给结点指针构造一个迭代器对象即可。

//构造函数
_list_iterator(node* pnode):_pnode(pnode)
{}

4、前置++运算符重载

        前置++的原始功能是使数据自增并返回自增后的结果。为了让结点指针模拟普通指针的行为，我们需要先让结点指针指向下一个结点，然后返回更新后的指针。

// 前置++
self operator++()
{_pnode = _pnode->_next; // 指针指向下一个结点return *this;          // 返回更新后的指针
}

5、后置++运算符重载

        后置++的实现需要先保存当前指针状态，然后移动指针到下一个结点，最后返回之前保存的指针值。

// 后置++
self operator++(int)
{self tmp(*this);       // 保存当前指针状态_pnode = _pnode->_next; // 指针指向下一个结点return tmp;            // 返回之前的指针
}

注：self定义为当前迭代器类型的别名：typedef _list_iterator<T, Ref, Ptr> self;

6、前置 -- 运算符重载

对于前置 -- 运算，需要先将结点指针指向前一个结点，然后返回修改后的指针。

// 前置--
self operator--() 
{_pnode = _pnode->_prev;  // 移动指针到前一个结点return *this;            // 返回当前对象
}

7、后置 -- 运算符重载

对于后置 -- 运算，需要先保存当前指针状态，移动指针后再返回先前保存的值。

// 后置--
self operator--(int) 
{self tmp(*this);         // 保存当前状态_pnode = _pnode->_prev;  // 移动指针到前一个结点return tmp;              // 返回先前保存的值
}

8、==运算符重载

        当使用==运算符比较两个迭代器时，实际上需要判断它们是否指向相同位置，即比较两个迭代器所包含的结点指针是否相同。

bool operator==(const self& s) const
{return _pnode == s._pnode;  // 比较结点指针的指向
}

9、重载 != 运算符

!= 运算符的功能与 == 运算符相反，用于判断两个迭代器中的节点指针是否指向不同的位置。

bool operator!=(const self& s) const
{return _pnode != s._pnode;  // 检查两个节点指针是否指向不同地址
}

10、解引用运算符的重载

        解引用操作符用于获取指针指向位置的数据内容。因此，我们直接返回当前节点指针所指向节点的数据即可。这里需要使用引用返回类型，因为解引用操作后用户可能需要对数据进行修改。

Ref operator*()
{return _pnode->_val; // 返回节点指针所指向节点的数据
}

11、->运算符的重载

        在某些使用迭代器的场景中，我们可能需要通过->运算符来访问元素成员。例如当list容器存储的是自定义类型（如日期类）时，我们可以通过迭代器直接访问Date类的成员：

list<Date> lt;
Date d1(2021, 8, 10);
Date d2(1980, 4, 3);
Date d3(1931, 6, 29);
lt.push_back(d1);
lt.push_back(d2);
lt.push_back(d3);
list<Date>::iterator pos = lt.begin();
cout << pos->_year << endl; // 输出第一个日期的年份

注意：使用pos->_year这种访问方式时，需要将Date类的成员变量设为公有。

->运算符的重载实现很简单，直接返回结点存储数据的地址即可：（C++ 的 -> 运算符要求返回指针，编译器会自动处理 -> 的嵌套调用。）

Ptr operator->()
{return &_pnode->_val; // 返回结点指针所指数据的地址
}

        这里有一个需要注意的地方：按照重载方式，理论上使用迭代器访问成员变量时应该有两个->运算符。第一个箭头是pos->调用重载的operator->返回Date指针，第二个箭头是Date指针访问成员变量_year。但为了提升代码可读性，编译器会进行特殊处理，自动省略一个箭头。

---

四、List 模拟实现

1、默认成员函数

构造函数

        List 采用带头双向循环链表结构。在构造 list 对象时，会先申请一个头节点，并将该节点的前驱和后继指针都指向自身，形成初始循环结构。

// 构造函数
list()
{_head = new node;        // 创建头节点_head->_next = _head;    // 后继指针自指_head->_prev = _head;    // 前驱指针自指
}

拷贝构造函数

拷贝构造函数用于根据已有list容器创建一个新对象。其实现步骤如下：

1. 申请头结点并初始化其指针指向自身
2. 遍历原容器数据，逐个执行尾插操作

实现代码如下：

// 拷贝构造函数
list(const list<T>& lt)
{_head = new node;        // 申请头结点_head->_next = _head;    // 初始化后继指针_head->_prev = _head;    // 初始化前驱指针for (const auto& e : lt) // 遍历原容器{push_back(e);        // 执行尾插操作}
}

赋值运算符重载函数

传统写法

这种实现方式逻辑清晰直观：先清空原有容器，然后逐个插入新元素。

//传统写法
list<T>& operator=(const list<T>& lt)
{if (this != &lt) //避免自己给自己赋值{clear(); //清空容器for (const auto& e : lt){push_back(e); //将容器lt当中的数据一个个尾插到链表后面}}return *this; //支持连续赋值
}

现代写法

        现代实现方式代码更简洁：通过编译器机制，故意不使用引用传参，让编译器自动调用list的拷贝构造函数生成临时对象，然后调用swap函数完成原容器与临时对象的交换。

list<T>& operator=(list<T> lt) // 参数使用传值方式，自动调用拷贝构造
{swap(lt); // 交换容器内容return *this; // 支持链式赋值
}

        现代写法的优势在于：通过参数传值创建临时副本后交换内容，原容器数据会随着临时对象销毁而自动清理，代码更加简洁高效。

析构函数

在对象销毁时，首先调用 clear 函数清空容器数据，然后释放头节点，最后将头指针置空。

// 析构函数
~list()
{clear();      // 清空容器delete _head; // 释放头节点_head = nullptr; // 重置头指针
}

2、迭代器相关函数：begin和end

begin和end函数的功能如下：

• begin()返回指向第一个有效数据的迭代器
• end()返回指向最后一个有效数据下一个位置的迭代器

对于带头双向循环链表list来说：

• 第一个有效数据的迭代器是通过头结点下一个结点的地址构造的
• end()返回的迭代器是通过头结点地址构造的（因为最后一个结点的next指针指向头结点）

iterator begin()
{// 返回头结点下一个结点构造的普通迭代器return iterator(_head->_next);
}iterator end()
{// 返回头结点构造的普通迭代器return iterator(_head);
}

同时需要提供const版本的重载：

const_iterator begin() const
{// 返回头结点下一个结点构造的const迭代器return const_iterator(_head->_next);
}const_iterator end() const
{// 返回头结点构造的const迭代器return const_iterator(_head);
}

3、访问容器相关函数

front()和back()

        front()和back()函数分别用于获取容器中的首元素和末元素。实现时直接返回首元素和末元素的引用即可。

T& front()
{return *begin(); // 返回首元素的引用
}T& back()
{return *(--end()); // 返回末元素的引用
}

为保证const对象的正确访问，需要重载const版本：

const T& front() const
{return *begin(); // 返回首元素的const引用
}const T& back() const
{return *(--end()); // 返回末元素的const引用
}

4、插入与删除函数

insert函数

insert函数用于在指定迭代器位置前插入新节点。

函数流程：

1. 通过迭代器获取当前节点指针cur
2. 通过cur获取前驱节点指针prev
3. 根据输入值x创建新节点
4. 建立新节点与当前节点的双向链接
5. 建立新节点与前驱节点的双向链接

//插入函数
void insert(iterator pos, const T& x)
{assert(pos._pnode); //检测pos的合法性node* cur = pos._pnode; //迭代器pos处的结点指针node* prev = cur->_prev; //迭代器pos前一个位置的结点指针node* newnode = new node(x); //根据所给数据x构造一个待插入结点//建立newnode与cur之间的双向关系newnode->_next = cur;cur->_prev = newnode;//建立newnode与prev之间的双向关系newnode->_prev = prev;prev->_next = newnode;
}

erase 函数

erase 函数用于删除指定迭代器位置的节点。

该函数执行以下操作：

1. 获取目标节点指针 cur
2. 定位前驱节点 prev 和后继节点 next
3. 释放当前节点内存
4. 重建前后节点的双向链接关系

//删除函数
iterator erase(iterator pos)
{assert(pos._pnode); //检测pos的合法性assert(pos != end()); //删除的结点不能是头结点node* cur = pos._pnode; //迭代器pos处的结点指针node* prev = cur->_prev; //迭代器pos前一个位置的结点指针node* next = cur->_next; //迭代器pos后一个位置的结点指针delete cur; //释放cur结点//建立prev与next之间的双向关系prev->_next = next;next->_prev = prev;return iterator(next); //返回所给迭代器pos的下一个迭代器
}

push_back 和 pop_back 函数

    push_back 和 pop_back 函数分别用于在链表尾部进行插入和删除操作。通过复用已有的 insert 和 erase 函数，我们可以简洁地实现这两个功能：

• push_back 在头节点前插入新节点
• pop_back 删除头节点前的一个节点

// 尾插操作
void push_back(const T& x)
{insert(end(), x); // 在尾节点位置插入新元素
}// 尾删操作
void pop_back()
{erase(--end()); // 删除尾节点
}

push_front 和 pop_front 函数

同样地，我们可以复用 insert 和 erase 函数来实现头部的插入和删除操作：

• push_front 在第一个有效节点前插入新节点
• pop_front 删除第一个有效节点

// 头插操作
void push_front(const T& x)
{insert(begin(), x); // 在链表头部插入新元素
}// 头删操作
void pop_front()
{erase(begin()); // 删除链表首元素
}

5、其他函数

size

size函数用于获取容器中有效数据的个数。由于list是链表结构，需要通过遍历统计元素数量。

size_t size() const
{size_t sz = 0;  // 计数器初始化为0const_iterator it = begin();  // 获取起始迭代器while (it != end())  // 遍历整个链表{sz++;it++;}return sz;  // 返回元素总数
}

扩展：可以考虑添加一个成员变量size来记录当前元素数量，避免每次遍历。

resize

resize函数的实现规则：

1. 扩容处理：当容器当前有效数据量小于指定值n时，持续在尾部插入新节点，直至数据量达到n。
2. 缩容处理：当容器当前有效数据量大于n时，仅保留前n个有效数据，后续节点将被释放。

优化实现建议：

• 避免直接调用size函数获取当前数据量，防止重复遍历
• 采用遍历计数法：设置变量len记录已遍历节点数量
  • 当len≥n时终止遍历，释放后续节点
  • 当遍历完所有节点时（len<n），持续进行尾插操作直至数据量达到n

注意事项：

• 此方法确保只需单次遍历即可完成调整操作
• 有效平衡了执行效率和内存管理需求

void resize(size_t n, const T& val = T())
{iterator i = begin(); //获取第一个有效数据的迭代器size_t len = 0; //记录当前所遍历的数据个数while (len < n&&i != end()){len++;i++;}if (len == n) //说明容器当中的有效数据个数大于或是等于n{while (i != end()) //只保留前n个有效数据{i = erase(i); //每次删除后接收下一个数据的迭代器}}else //说明容器当中的有效数据个数小于n{while (len < n) //尾插数据为val的结点，直到容器当中的有效数据个数为n{push_back(val);len++;}}
}

clear

clear函数用于清空容器，我们通过遍历的方式，逐个删除结点，只保留头结点即可。

void clear()
{iterator it = begin();while (it != end())  // 逐个删除元素{it = erase(it);}
}

empty

        empty函数用于判断容器是否为空，我们直接判断该容器的begin函数和end函数所返回的迭代器，是否是同一个位置的迭代器即可。（此时说明容器当中只有一个头结点）

bool empty() const
{return begin() == end();  // 判断起始和结束迭代器是否相同
}

swap

        swap函数用于交换两个容器，list容器当中存储的实际上就只有链表的头指针，我们将这两个容器当中的头指针交换即可。

void swap(list<T>& lt)
{std::swap(_head, lt._head);  // 调用全局swap函数交换头指针
}

注意：使用std::显式指定调用std命名空间的swap函数，避免与成员函数冲突。

---

五、测试代码

void TestList() {// 测试默认构造函数和push_backhmz::list<int> l1;assert(l1.size() == 0);assert(l1.begin() == l1.end());l1.push_back(1);l1.push_back(2);l1.push_back(3);assert(l1.size() == 3);assert(*l1.begin() == 1);assert(*(--l1.end()) == 3);// 测试front和backassert(l1.front() == 1);assert(l1.back() == 3);// 测试迭代器遍历std::vector<int> v;for (auto it = l1.begin(); it != l1.end(); ++it) {v.push_back(*it);}assert(v == std::vector<int>({ 1, 2, 3 }));// 测试拷贝构造函数hmz::list<int> l2(l1);assert(l2.size() == 3);v.clear();for (auto it = l2.begin(); it != l2.end(); ++it) {v.push_back(*it);}assert(v == std::vector<int>({ 1, 2, 3 }));// 测试赋值运算符hmz::list<int> l3;l3 = l1;assert(l3.size() == 3);v.clear();for (auto it = l3.begin(); it != l3.end(); ++it) {v.push_back(*it);}assert(v == std::vector<int>({ 1, 2, 3 }));// 测试push_front和pop_frontl3.push_front(0);assert(l3.front() == 0);assert(l3.size() == 4);l3.pop_front();assert(l3.front() == 1);assert(l3.size() == 3);// 测试pop_backl3.pop_back();assert(l3.back() == 2);assert(l3.size() == 2);// 测试insertauto it = l3.begin();++it;l3.insert(it, 5);v.clear();for (auto num : l3) {v.push_back(num);}assert(v == std::vector<int>({ 1, 5, 2 }));// 测试eraseit = l3.begin();++it;it = l3.erase(it);assert(*it == 2);assert(l3.size() == 2);// 测试resize增大l3.resize(4, 10);assert(l3.size() == 4);v.clear();for (auto num : l3) {v.push_back(num);}assert(v == std::vector<int>({ 1, 2, 10, 10 }));// 测试resize缩小l3.resize(2);assert(l3.size() == 2);v.clear();for (auto num : l3) {v.push_back(num);}assert(v == std::vector<int>({ 1, 2 }));// 测试clearl3.clear();assert(l3.size() == 0);assert(l3.begin() == l3.end());// 测试swaphmz::list<int> l4;l4.push_back(7);l4.push_back(8);l4.push_back(9);l3.swap(l4);assert(l3.size() == 3);assert(l4.size() == 0);v.clear();for (auto num : l3) {v.push_back(num);}assert(v == std::vector<int>({ 7, 8, 9 }));// 测试const迭代器const hmz::list<int> l5(l3);v.clear();for (auto it = l5.begin(); it != l5.end(); ++it) {v.push_back(*it);}assert(v == std::vector<int>({ 7, 8, 9 }));std::cout << "All list tests passed!" << std::endl;
}int main() {TestList();return 0;
}

---

六、vector 与 list 的对比

对比项	vector	list
底层结构	动态顺序表（一段连续空间）	带头结点的双向循环链表
随机访问	支持，效率 O(1)	不支持，效率 O(N)
插入和删除	任意位置效率低（需搬移元素），时间复杂度 O(N)；增容可能导致额外开销	任意位置效率高（无需搬移元素），时间复杂度 O(1)
空间利用率	连续空间，内存碎片少，空间及缓存利用率高	节点动态开辟，易产生内存碎片，空间及缓存利用率低
迭代器类型	原生态指针（通常为指针或随机访问迭代器）	对节点指针的封装（双向迭代器）
迭代器失效	插入可能因扩容使所有迭代器失效；删除时当前迭代器需重新赋值	插入不失效；删除仅影响当前迭代器
使用场景	需高效存储、频繁随机访问，插入删除操作较少	需频繁插入删除，不依赖随机访问

关键总结：

• vector：适合随机访问密集、内存紧凑的场景，但插入/删除（尤其非尾部）性能较差。

• list：适合频繁插入/删除的场景，但随机访问效率低且内存开销较大。

---

七、为什么 list 的插入不会使迭代器失效，而删除仅影响当前迭代器？

        这是由于 list 的底层结构是双向链表，其内存管理和元素访问方式与 vector（动态数组）有本质区别。

1、list 插入不会使迭代器失效的原因

在 list 中，插入新元素时：

1. 不涉及内存重新分配：

   • vector 在插入时可能需要扩容（重新分配内存+拷贝元素），导致所有迭代器失效。

   • 但 list 的节点是 动态分配 的，插入新元素只需修改相邻节点的指针，不会影响其他节点的内存地址。

2. 插入操作仅修改局部指针：

   • 例如，在节点 A 和 B 之间插入 X，只需：

     A.next = &X;
     X.prev = &A;
     X.next = &B;
     B.prev = &X;

   • 其他节点的地址不变，因此所有现有迭代器仍然有效。

✅ 结论：list 插入操作不会导致任何迭代器失效（包括 end()）。

2、list 删除仅影响当前迭代器的原因

在 list 中，删除元素时：

1. 仅释放当前节点的内存：

   • 例如，删除节点 X（位于 A 和 B 之间）：

     A.next = &B;
     B.prev = &A;
     delete &X;  // 释放 X 的内存

   • 只有 X 的迭代器失效，其他节点（如 A、B）的迭代器不受影响。

2. 不涉及数据搬移：

   • vector 删除元素后，后面的元素会前移，导致后面的迭代器全部失效。

   • 但 list 是链表，删除一个节点 不会影响其他节点的位置。

❌ 错误示例（导致未定义行为）：

std::list<int> lst = {1, 2, 3, 4};
auto it = lst.begin();
++it; // it 指向 2
lst.erase(it); // 删除 2
std::cout << *it; // ❌ it 已失效，访问会导致未定义行为！

✅ 正确做法（返回新迭代器）：

it = lst.erase(it); // it 现在指向 3（删除后的下一个元素）

3、对比 vector 的迭代器失效

操作	vector	list
插入	可能扩容，所有迭代器失效	不会失效
删除	被删元素后的所有迭代器失效	仅当前迭代器失效

4、总结

• list 插入不失效：因为链表动态分配节点，插入只修改指针，不改变已有元素的内存地址。

• list 删除仅当前失效：因为只释放当前节点，其他节点不受影响。

• vector 插入/删除可能失效：由于内存重新分配或元素搬移，导致迭代器失效。

这种差异使得 list 在频繁插入/删除的场景下更安全，而 vector 在随机访问时更高效。