list的使用和模拟

(一)list的了解

(1)简单了解

list的文档介绍

list是基于双向链表的序列式容器，支持双向迭代和任意位置的常数时间插入删除，相比 array、vector 等容器在这类操作上更高效，但不支持随机访问（访问需线性遍历）且因额外空间存储节点关联信息，与 forward_list（单链表）相比功能更全但略复杂。对双链表忘记的可以去查看博主的文章——双链表。

样子如下：（博主借用了老师的课件）

(2)常用接口

博主把解释直接写在图片中了。

(1) 构造函数

与之前的构造函数没什么区别就不再介绍了

(2) 迭代器

博主花了个简易版方便大家查看

注意

begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动
rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动

迭代器分类（按照功能分类，即性质（底层结构决定））

1.单向向迭代器

核心功能：只能从容器到尾单向移动，支持读取（部分支持修改）
支持的操作：++（前置 / 后置）、*（解引用读）、->；不支持--、+=n等
典型容器：forward_list（单链表）、unordered_map/unordered_set（哈希容器）

2.双向迭代器

核心功能：可双向移动（支持++和--），功能强于单向迭代器
支持的操作：继承单向向迭代器的所有操作，新增--（前置 / 后置）；不支持随机访问（+=n等）
典型容器：list（双向链表）、map/set（红黑树）

3.随机访问迭代器

核心功能：支持任意位置跳转（随机访问），功能最强
支持的操作：继承双向迭代器的所有操作，新增+=n、-=n、[]、</>等关系运算
典型容器：vector、deque、array

总结：

功能继承关系：随机访问迭代器 ⊇ 双向迭代器 ⊇ 单向迭代器。即功能强的迭代器支持功能弱的迭代器的所有操作。

迭代器的分类本质是对移动和访问能力的标准化，理解不同迭代器的功能边界，能帮助我们正确选择容器和算法，避免因迭代器功能不足导致的编译错误。

(3) 容量

因为他是链表，没有提前扩容，也就没有capacity了。

(4) 元素访问

(5) 一些重要的函数

与vector不同的是，list有头插和头删，vector没头插和头删因为效率太低但可以用insert和erase来进行头插和头删）

(6) 操作/运行

这些能帮助我们快速写一些题目

小细节：

1. splice 拼接

元素所有权转移：将元素从一个链表移到另一个链表，原链表中被移动的元素会被移除（并非复制）。
迭代器有效性：被移动元素的迭代器仍有效，但归属权转移到新链表。
自操作风险：若源链表和目标链表是同一个，需确保插入位置不在被移动元素范围内，否则可能导致循环引用。

2. remove / remove_if 移除

值语义依赖：remove 依赖==运算符重载，remove_if 依赖自定义条件的正确性。
迭代器失效：被删除元素的迭代器会失效，其他元素迭代器不受影响。
性能：会遍历整个链表，时间复杂度为 O (n)。

3. unique 去重

仅删除连续重复元素：需先通过sort使重复元素相邻，否则无法删除非连续的重复项。

4. merge 合并

前提条件：两个链表必须已排序（默认升序），否则合并后结果无序。
破坏性合并：合并后源链表会被清空（元素全部转移到目标链表）。

5. sort 排序

链表专属排序：list 不支持标准库std::sort（需随机访问迭代器），必须使用自身的sort成员函数。
稳定性：list::sort 是稳定排序（相同元素保持原有相对顺序）。
性能：时间复杂度为 O (n log n)，但因链表特性，实际效率略低于vector的排序。

6. reverse 逆置

仅反转顺序：不改变元素本身，仅调整节点间的指针关系，时间复杂度 O (n)。

使用：

#include <iostream>
#include <list>
using namespace std;void Print(const list<int>& lt)
{auto it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}void test_splice(list<int> l1, list<int> l2)
{cout << "l1 splice后：";l1.splice(l1.begin(), l2);Print(l1);cout << "此时l2后：";Print(l2);
}void test_remove(list<int> l1)
{cout << "l1 remove后：";l1.remove(5);Print(l1);
}void test_remove_if(list<int> l1)
{cout << "l1 删除所有偶数后：";l1.remove_if([](int x) { return x % 2 == 0; });Print(l1);
}void test_unique(list<int> l2)
{cout << "l2 去掉重复后：";l2.unique();Print(l2);
}void test_reverse(list<int> l1)
{cout << "l1 reverse后：";l1.reverse();Print(l1);
}void test_merge(list<int> l1, list<int> l2)
{cout << "l1和l2排序后合并：";l1.sort(), l2.sort();l1.merge(l2);Print(l1);}int main() {list<int> l1 = { 1,4,6,9,2 };list<int> l2 = { 3,7,8,7,8,5,10 };cout << "原l1：：";Print(l1);cout << "原l2：：";Print(l2);test_splice(l1, l2);test_remove(l1); test_remove_if(l1);test_unique(l2); test_reverse(l1);test_merge(l1, l2);return 0;
}

运行结果：

(二)list的模拟

如上几篇文章的模拟一样，首先需要定义一个专属命名空间。这次的准备工作博主就不细写了。

(1) list的节点的实现

由上面了解可知list为带头双向循环列表，那我们先来处理一下他的节点代码吧。每个节点有两个指针，一个指向上一个节点，一个指向下一个节点，然后还要储存该节点空间。又因为不知道节点类型是什么所以我们使用类模板，类模板需要初始化。

template <class T>
struct list_node
{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}
};

小细节：

struct list_node：
C++ 中 struct 默认成员访问权限为 public，而 class 默认是 private
且节点的指针（_next、_prev）和数据（_val）需要被链表类（list）直接访问，虽然这里节点主要被 list 类使用，但用 struct 可以省去显式声明 public 的步骤，使代码更简洁

list_node(const T& val = T())：

const T& val：使用 const 引用接收参数，避免传递大型对象时的拷贝开销，同时保证参数不会被修改
默认参数 T()：当不提供初始值时，会调用 T 类型的默认构造函数生成一个临时对象作为初始值（对于内置类型如 int，T() 会生成 0）

(2) list的链表的实现

知道节点后我们就可以模拟list链表了，我们又由上几篇模拟可知，代码如下：

namespace Yu
{template <class T>struct list_node{//博主省空间这代码就是上面的代码};template <class T>class list{typedef list_node<T> Node;public://list实现内容private:Node* _head;size_t _size;};}

小细节：

size_t _size：

方便快速获取链表中有效元素的个数，避免每次需要获取长度时都要遍历整个链表。

(3) 构造函数

list()
{_head = new Node;          // 创建哨兵位头节点，并初始化_head->_next = _head;      _head->_prev = _head;      _size = 0;                 // 初始化元素个数为0
}

(4) 迭代器

在链表（如list）中，我们无法像数组（如vector）那样通过原生指针的++直接移动到下一个元素，因为链表的节点在内存中是非连续存储的，节点之间通过指针（_next、_prev）关联。此时，迭代器的作用就是模拟指针的行为，让用户可以用统一的方式（如*it访问元素、++it移动位置）遍历链表，而无需关心底层的存储结构。细节解释：

1.原生指针的局限性

链表的节点是分散存储的，原生指针的++操作只会按固定字节（如 4/8 字节）移动，无法根据链表的_next指针找到下一个节点，因此内置类型的指针无法直接作为链表的迭代器。

2.迭代器的封装思想

迭代器本质是一个封装了节点指针的自定义类型（如list_iterator），它内部存储了指向链表节点的指针（_node），通过重载运算符（*、->、++、--等），将链表节点的访问和移动逻辑 “隐藏” 在运算符中

简言之，迭代器是 “行为类似指针的自定义类型”，通过封装节点指针和重载运算符，将链表的底层指针操作转化为直观的 “指针式” 接口，既适配了链表的非连续存储特性，又保证了容器操作的统一性。C++可以用一个类去封装这个内置类型，然后去重载运算符，就可以控制他的行为，达到我们的要求。

1.普通迭代器

template<class T>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T> Self;Node  _node;list_iterator(Node* node):_node(node){}T& operator*(){return _node->_val;}T* operator->(){return &_node->val;}//前置++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;}bool operator!=(const Self& x)const{return _node != x._node;}bool operator==(const Self& x)const{return _node == x._node;}};

小细节：

T& operator*()

满足*it通过解引用运算符，返回节点中储存的数据（val）。模拟指针访问值的行为

Self& operator++()

利用节点的_next指针（_node = _node->_next）移动到下一个节点，模拟指针向后移动的行为

Self& operator--()

利用_prev指针实现向前移动，适配双向链表的特性。

这种设计让链表的遍历方式与数组、vector 等连续容器保持一致（都可以用for (auto it = begin(); it != end(); ++it)），符合 C++ 的 “泛型编程” 思想 —— 用户无需区分容器类型，只需通过迭代器接口即可操作不同容器，降低了使用成本。

此时list类里面的调用：
//放在list类中
typedef list_iterator<T> iterator;//迭代器
iterator begin()
{return iterator(_head->_next);
}iterator end()
{return iterator(_head);
}
小细节：

return iterator(_head->_next);节点为何能返回迭代器？

直接调用迭代器的构造函数创建临时对象并返回

iterator 是 list_iterator<T> 的别名，因此 iterator(_head->_next) 是显式调用 list_iterator<T> 的构造函数，创建一个临时的迭代器对象。
构造函数的参数 _head->_next 是 Node* 类型（即 list_node<T>*），而 list_iterator 的构造函数正好接受 Node* 作为参数：

2. const迭代器

既然知道普通的迭代器，那是不是应该在考虑一下const成员的迭代器，因为普通迭代器调用const成员会权限放大，导致报错，那const迭代器怎么写了？

有人可能想到这样

const list_iterator<T> const_iterator

这样是不对的，我们先来了解一下const的两种改变：

1. const T* ptr1：

const 修饰 T（在 * 左侧），表示 ptr1 指向的 T 类型对象内容不可修改（*ptr1 = value 会报错），但指针本身可以移动（ptr1++ 合法）。这是 “指向常量的指针”。

2. T* const ptr2：

const 修饰 ptr2（在 * 右侧），表示指针本身不可修改（ptr2++ 会报错），但指向的对象内容可以修改（*ptr2 = value 合法）。这是 “常量指针”。

即const在*之前为指向内容不变，*之后为指向对象不可变

而const 迭代器的核心需求是：迭代器可以移动（类似 ptr1++），但通过迭代器访问的内容不可修改（类似 *ptr1 为 const）。这正是与形式 1 更符合。

故正确的方法是：（跟普通迭代器类似就有几个地方要改）

//这里博主就列出了改变的
struct __list_const_iterator
{typedef __list_const_iterator<T> Self;__list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_val;}const T* operator->(){return &_node->_val;}// 下面为一样内容
}

在list里面调用：

//在list类里面
typedef __list_const_iterator<T> const_iterator; //迭代器
const_iterator begin() const 
{return const_iterator(_head->_next);
}const_iterator end() const
{return const_iterator(_head);
}

3. 迭代器

我们发现普通迭代器和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){}Ref operator*() const{return _node->_val;}Ptr operator->() const{return &_node->_val;}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;}bool operator!=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}
};

小细节：

template<class T, class Ref, class Ptr>

T：节点中存储的元素类型（基础类型）。
Ref：迭代器解引用（operator*）的返回类型（引用类型）。
Ptr：迭代器箭头运算符（operator->）的返回类型（指针类型）。

通过这三个参数，可灵活控制迭代器访问元素的权限（是否为 const）。

在list里面调用：
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
后面的begin和end就如上面一样

(5) push_back

博主为了方便测试上面迭代器是否对，使用先写了一个push_back，其中这个可以在后面用insert复用的。后续的插入和删除可以参考博主的数据结构的双链表里面有图片解释。

void push_back(const T& val)
{Node* newNode = new Node(val);Node* _tail = _head->_prev;_head->_prev = newNode;newNode->_next = _head;_tail->_next = newNode;newNode->_prev = _tail;_size++;
}

测试结果：

void test1()
{Yu::list<int> l1;l1.push_back(10);l1.push_back(20);l1.push_back(30);l1.push_back(40);for (auto it = l1.begin(); it != l1.end(); ++it){cout << *it << " ";}cout << endl;}
//测试结果：10 20 30 40

(5) 拷贝构造

因为拷贝构造是将一个list复制到另一个list，使用先得初始化一下另一个list发现重复了，于是我们可以将初始化单独列一个函数

void empty_Init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}

此时构造函数和拷贝函数

//构造函数
list()
{empty_Init();
}//拷贝构造
list(const list<T>& lt)
{empty_Init();for (auto& e : lt){push_back(e);}
}

小细节：

for (auto& e : lt)

1. 避免不必要的拷贝，提高效率
lt 是源链表中的元素集合，当遍历 lt 时：

如果用 auto e，每次迭代都会对元素进行值拷贝（创建一个与原元素值相同的新对象）。如果元素类型是复杂类型（如自定义类、大型结构体），值拷贝可能会调用拷贝构造函数，产生额外的内存分配和数据复制开销，降低效率。
而使用 auto& e 时，e 是原元素的引用（别名），不会创建新对象，直接访问原元素，避免了不必要的拷贝操作，尤其对于大型数据或复杂类型，能显著提升性能。

2. 保证 const 正确性（配合 const 引用更严谨）

在拷贝构造函数中，lt 是 const list<T>& 类型（常量引用），表示源链表不能被修改。
更规范的写法其实是 for (const auto& e : lt)，其中 const 修饰确保不会通过 e 意外修改源链表的元素，符合 "只读取不修改" 的拷贝语义。如果写成 auto e，虽然也能完成拷贝，但缺少 const 约束，理论上可以通过修改 e 影响原元素（虽然这里 e 是拷贝，实际不影响，但逻辑上不严谨）。

总结
auto& e（通常更推荐 const auto& e）的核心作用是：在保证不修改源数据的前提下，避免元素拷贝带来的性能损耗，同时符合 const 正确性原则。

这是 C++ 中遍历容器时的最佳实践，尤其适用于拷贝成本高的元素类型。

(6) insert

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

小细节：

return newNode;

insert函数返回新插入元素的迭代器，这是 C++ 标准库中链表（std::list）的设计规范

主要有以下几个原因：

1. 符合迭代器失效规则

插入操作不会导致其他迭代器失效，但用户可能需要继续操作新插入的元素。返回新节点的迭代器可以直接获取这个位置，避免用户重新遍历查找。

为什么不会导致迭代器失效？

先了解链表的存储特点和迭代器的本质
链表的存储特点：

链表的节点在内存中是离散存储的，节点之间通过指针（_next和_prev）关联，而非像数组那样连续占用一块内存。插入新节点时，只需要修改相邻节点的指针指向，不会移动其他已有节点的位置。

迭代器的本质：

链表的迭代器本质上是指向节点的指针封装（代码中_node成员就是节点指针）。只要迭代器指向的是某个具体节点，只要这个节点没被删除，指针就始终有效。

而插入操作的影响范围
插入新节点时，只会修改插入位置前后两个节点的指针（前节点的_next和后节点的_prev），但这两个节点本身并没有被移动或删除：原迭代器如果指向这两个节点，仍然有效（只是它们的指针成员被修改了）其他节点的指针和迭代器完全不受影响

故insert操作仅通过局部指针调整完成插入，既不影响已有节点的存在，也不破坏原有迭代器与节点的对应关系，因此不会导致任何已有迭代器失效，且能通过返回值直接获取新元素的迭代器

2. 支持链式操作
允许连续插入操作，例如：

auto it = l.insert(pos, 1);
l.insert(it, 2);  // 在刚插入的元素前再插入

3. 与标准库行为一致
遵循 C++ 标准容器的设计习惯，这样用户切换容器时不需要修改使用习惯。

(7) 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;--_size;return next;
}

小细节：

return next;

erase函数返回新插入元素的迭代器，这是 C++ 标准库中链表（std::list）的设计规范

主要有以下几个原因：

1. 被删除节点的迭代器已失效

删除操作中，delete cur会释放被删除节点的内存，因此传入的参数pos（指向cur的迭代器）会变成野指针，彻底失效。如果不返回新的迭代器，用户后续无法基于原位置继续操作（比如继续遍历链表）。

为什么会导致迭代器失效？

在链表的删除操作（erase）中，只有被删除节点的迭代器会失效，其他迭代器通常不会失效。
1. 为什么被删除节点的迭代器会失效？

链表的迭代器本质是对节点指针的封装（如pos._node指向具体节点）。删除操作中，被删除的节点（cur）会被delete释放内存，此时指向该节点的迭代器（pos）所关联的指针就变成了野指针（指向已释放的内存）。野指针无法安全访问，也不允许被使用（如解引用、递增），因此这个迭代器彻底失效。

注意：
删除操作后，被删除节点的迭代器（pos）绝对不能再使用（如继续解引用或递增），否则会导致未定义行为（程序崩溃、数据错误等）。

因此，erase函数会返回被删除节点的下一个节点的迭代器（next），用于替代失效的pos，保证后续操作的安全性（如继续遍历）。

后面两点如上支持链式操作和与标准库行为一致

小复用：

//尾插
void push_back(const T& val)
{insert(end(), val);
}//头插
void push_front(const T& val)
{insert(begin(), val);
}//尾删
void pop_back()
{erase(--end());
}//头删
void pop_front()
{erase(begin());
}

这样可以提高效率

测试结果：

void test2()
{Yu::list<int> l;l.push_back(1);l.push_back(2);l.push_back(3);auto it = l.begin();++it; l.insert(it, 4);cout << "插入后: ";for (auto e : l) {cout << e << " ";}cout << endl;it = l.begin();++it;++it; l.erase(it); cout << "删除后: ";for (auto e : l) {cout << e << " ";}cout << endl;
}//运行结果：
//插入后: 1 4 2 3
//删除后: 1 4 3

(8) 析构函数

链表的节点是独立分配的离散内存块，必须逐个释放，所以我们先写一个clear函数

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

作用：删除链表中所有有效数据节点（不包括哨兵位头节点_head），使链表回到 “空链表但可复用” 的状态。

再写一个链表是否为空的函数empty

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

作用：快速判断链表中是否包含有效数据节点（不含哨兵位）。

最后的析构函数

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

三者配合确保了链表在 “清空 - 复用 - 销毁” 全生命周期中的内存安全，逻辑严谨且高效。

(9) operator=

我们继续采用现代写法因为他很方便

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

小细节：

list<T>& operator=(list<T> lt)和list& operator=(list lt)

这两个都可以使用

list<T>& operator=(list<T> lt)

为完整写法，显式指定模板参数，这种写法更完整和明确，博主还认为更好理解

list& operator=(list lt)

简写形式，省略模板参数，这里省略了<T>，直接使用list。在模板类的成员函数中，编译器会自动将list解析为list<T>（当前模板实例化的类型）。这是 C++ 的语法简化，在模板类内部可以省略模板参数，编译器会根据上下文自动推导。

还有一些代码没有介绍，完整代码——gitee

(三) list与wvctor的比较

特性	vector	list
随机访问	支持（`[]`或`at()`，时间复杂度O(1)）	不支持（需从头 / 尾遍历，时间复杂度O(n)）
插入 / 删除效率	头部 / 中间插入 / 删除：O(n)（需移动后续元素）尾部插入 / 删除：O(1)（未扩容时）	任意位置插入 / 删除：O(1)（只需修改指针，无需移动元素）
内存占用	额外内存少（仅需存储元素和少量管理信息），但可能有内存浪费（扩容预留空间）	额外内存多（每个节点需存储两个指针），无预留空间浪费
迭代器稳定性	插入 / 删除元素可能导致迭代器失效（如扩容后原指针指向旧内存）	插入元素时迭代器不失效（仅修改指针）；删除元素时，只有被删除节点的迭代器失效
遍历效率	高（连续内存，缓存友好，CPU 缓存命中率高）	低（分散内存，缓存不友好，频繁换页）
扩容成本	可能触发扩容（复制元素，时间复杂度O(n)）	无扩容概念（按需分配节点）