😎【博客主页：你最爱的小傻瓜】😎

🤔【本文内容：C++ list容器 😍】🤔

---------------------------------------------------------------------------------------------------------------------------------

在 C++ 的数据江湖里，list 仿若一位灵动迅捷的暗卫。

它凭双向链表的隐秘锁链串联元素，从无空间局促的烦忧 —— 新增元素时，只需借由 push_front 或 push_back 施展暗劲，新的节点便如暗桩般悄然嵌入。那些静卧的元素，似暗格里的密信静待调阅，借迭代器轻轻游走，就能探寻到某一环的机密。

当你持迭代器之匕穿梭其中，恰似指尖拂过暗卫的锁链，每个元素皆有序排布，等你细究。若要对这锁链重构序列，sort 函数就是绝佳的秘使，瞬间就能让杂乱的节点规整得有条不紊。

无论是整数的密令、字符的暗语，还是自定义对象的机密情报，它都能妥善收纳，宛如一座随需而设的秘库，让各类数据在其中各就其位，等候编程者去调取探寻。

---------------------------------------------------------------------------------------------------------------------------------

1.list的介绍：

在之前，我们学习了vector这个容器，我们复习一下。它的优点是尾插尾删效率高，支持随机访问。更详细的看我之前的博客链接：vector

今天我要分享的是list，它是以链表形式来实现的，并是环形双向链表（想要了解：顺序表和链表）。

因为是链表所以不支持随机访问，只能是通过已知的位置迭代到想访问的位置。但在插入和删除这两个方面效率更高，由于它是指针的形式来去储存数据的，只要将邻近的指针跟它相链接就行，删除也类似。

forward_list 是单链表的形式，只能朝前迭代。

// list()
list<int> l;

// list (size_type n, const value_type& val = value_type())
list<int> l(5, 10);

// list (const list& x);
list<int> l1{1, 2, 3};
list<int> l2(l1);

// list (InputIterator first, InputIterator last);
// 示例1：用数组迭代器构造
int arr[] = {1, 2, 3, 4, 5};
list<int> l(arr, arr + 5);// 示例2：用其他 list 的迭代器构造
list<int> l1{1, 2, 3, 4, 5};
list<int> l2(l1.begin(), l1.end());

begin()：返回指向容器第一个元素的可修改迭代器（iterator）

end()：返回指向容器最后一个元素后一位的可修改迭代器

用途：正向遍历并可修改元素

list<int> l{1,2,3};
for (auto it = l.begin(); it != l.end(); ++it) {*it += 10; // 修改元素：1→11，2→12，3→13
}

rbegin()：返回指向容器最后一个元素的反向迭代器（reverse_iterator）

rend()：返回指向容器第一个元素前一位的反向迭代器

用途：反向遍历并可修改元素

list<int> l{1,2,3};
for (auto rit = l.rbegin(); rit != l.rend(); ++rit) {*rit *= 2; // 反向修改：3→6，2→4，1→2
}

3.列表元素访问：

front() / back()：获取头部 / 尾部元素：

list<int> l{1,2,3};
l.front() = 10; // 头部改为10：[10,2,3]
l.back() = 30;  // 尾部改为30：[10,2,30]

4.容量访问：

empty()：判断容器是否为空（无元素），返回 bool 值（true 表示空，false 表示非空）

list<int> l1; // 空列表
list<int> l2{1,2,3}; // 非空列表cout << (l1.empty() ? "l1为空" : "l1非空"); // 输出：l1为空
cout << (l2.empty() ? "l2为空" : "l2非空"); // 输出：l2非空

size()：返回元素个数：

list<int> l{1,2,3};
cout << l.size(); // 输出：3

5.列表元素修改：

push_front(val)：在头部添加元素

list<int> l{2,3};
l.push_front(1); // 结果：[1,2,3]

push_back(val)：在尾部添加元素

list<int> l{1,2};
l.push_back(3); // 结果：[1,2,3]

insert(pos, val)：在迭代器pos位置插入元素

list<int> l{1,3};
auto it = ++l.begin(); // 指向3的位置
l.insert(it, 2); // 结果：[1,2,3]

pop_front()：删除头部元素

list<int> l{1,2,3};
l.pop_front(); // 结果：[2,3]

pop_back()：删除尾部元素

list<int> l{1,2,3};
l.pop_back(); // 结果：[1,2]

remove(val)：删除所有值为val的元素

list<int> l{1,2,2,3};
l.remove(2); // 结果：[1,3]

erase(pos)：删除迭代器pos指向的元素

list<int> l{1,2,3};
auto it = ++l.begin(); // 指向2
l.erase(it); // 结果：[1,3]

clear()：清空所有元素

list<int> l{1,2,3};
l.clear(); // 结果：空列表

6.操作：

splice（转移）：

 list<int> l1 = {1, 2, 3};list<int> l2 = {4, 5, 6};auto it = l1.begin();advance(it, 1); // 让 it 指向 l1 中元素 2l1.splice(it, l2); // 将 l2 中所有元素转移到 l1 中 it 指向的位置前for (auto num : l1) {cout << num << " ";}cout << endl;// 此时 l1: 1, 4, 5, 6, 2, 3；l2 为空

remove/remove_if

list<int> l = {1, 2, 2, 3};l.remove(2); // 移除值为 2 的元素for (auto num : l) {cout << num << " ";}cout << endl; // 输出：1 3list<int> l = {1, 2, 3, 4, 5};// 移除大于 3 的元素l.remove_if(bind(greater<int>(), placeholders::_1, 3));for (auto num : l) {cout << num << " ";}cout << endl; // 输出：1 2 3

unique

 list<int> l = {1, 1, 2, 2, 3, 3};l.unique(); // 移除相邻的重复元素for (auto num : l) {cout << num << " ";}cout << endl; // 输出：1 2 3

merge

list<int> l1 = {1, 3, 5};list<int> l2 = {2, 4, 6};l1.merge(l2); // 合并两个已排序的 listfor (auto num : l1) {cout << num << " ";}cout << endl; // 输出：1 2 3 4 5 6

sort

list<int> l = {3, 1, 2};l.sort(); // 对 list 中的元素进行排序for (auto num : l) {cout << num << " ";}cout << endl; // 输出：1 2 3

reverse

 list<int> l = {1, 2, 3};l.reverse(); // 反转 list 中元素的顺序for (auto num : l) {cout << num << " ";}cout << endl; // 输出：3 2 1

一些小知识：

双向迭代器：可双向移动（支持++和--），功能强于单向迭代器，继承单向迭代器操作，新增--（前置 / 后置），不支持随机访问（如+=n），典型容器像list、map/set。

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

单向迭代器：仅能从容器到尾单向移动，支持读取（部分可修改），操作有++（前置 / 后置）、*（解引用读）、->，不支持--、+=n等，典型容器如forward_list、unordered_map/unordered_set。

迭代器分类是对移动和访问能力的标准化，理解其功能边界，能助力正确选择容器和算法，避免因迭代器功能不足引发编译错误。

list的模拟实现（记得看注释）:

接下来我将手把手教你们实现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)
};

第二步：我们要实现list类：

template<class T>
class list
{
public:typedef list_node<T> Node;//简化名字
private:Node* _head;//哨兵位size_t _size;//计算list里面的数据个数};

第三步：完善我们的list类：

1.我们要初始化，可以写一个函数来初始化，再将它放入构造函数里面：

void empty_node()
{_head = new Node; //申请一个结点_head->next = _head;//因为只有一个哨兵位，双向链表里的方向指针，只能指向自身。_head->prev = _head;_size = 0;//记入数据多少
}
list()
{empty_node();
}

2.拷贝构造函数：要实现它，需对 list 进行插入、遍历等操作，但由此会产生一个问题：list 的这些功能能否和 vector 一样呢？答案显然是否定的。因为 vector 基于数组，是连续的内存空间；而 list 底层是双向链表，内存空间不连续。此时，迭代器就发挥作用了。这里用到的是双向迭代器，它能让我们更便捷地操作 list。双向迭代器本质上是一个封装好的类，专门用于对链表的结点（即操作对象）进行各类操作。

  1.初始的迭代器：对于const修饰的数据无法处理(处理这个两种方式就是用模板，还有就是再写一个const版的迭代器)

//1.通常版
template<class T>
//template<class T, class Ref, class Ptr>
struct list_iterator
{typedef list_node<T> Node;//简化名称typedef list_iterator<T> self;//简化名称Node* _node;//创建一个结点，来链接迭代器与结点之间的联系list_iterator(Node* node)//为一些结点转化为迭代器类类型，好操作结点，实现我们好用的方式:_node(node){}//解引用的实现：1.避免拷贝 2.支持修改操作，在一些数据里不是指针或引用，就是临时的不会影响原数据。T& operator*(){return _node->_val;}//->访问形式的实现：->就是对指针的。T* operator->(){return &(_node->_val);}//下面的返回值，以及代码实现，是有一些小心思的：
//self& self 这是因为第一个前置无需担心原数据的修改，另一个是后置要担心原数据的修改，因为我们先要
//用到未++前的数据情况，而后再++。
//self tmp(*this)之前我们说过的迭代器初始化，在这里有体现，我们将原先的赋值拷贝给一个临时的，再++，返回的是临时的，这样就实现了后置。//前置++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类型，这里传的是迭代器引用（防拷贝），并且用了const修饰，最后的 const 表明这个成员函数不会修改当前对象的状态。判断两个迭代器是否指向同一个节点bool operator!=(const self& x)const{return _node != x._node;}bool operator==(const self& x)const{return _node == x._node;}
};
//2.为了是应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){}//解引用的实现：1.避免拷贝 2.支持修改操作，在一些数据里不是指针或引用，就是临时的不会影响原数据。Ref operator*(){return _node->_val;}//->访问形式的实现：->就是对指针的。Ptr operator->(){return &(_node->_val);}//......上面的内容，没有改变};

2.迭代器的访问：
 

template<class T>
class list
{
public:typedef list_node<T> Node;//简化名字typedef list_iterator<T, T&, T*> iterator;//模板实例化typedef list_iterator<const T, const T&, const T*> const_iterator;//模板实例化
//iterator()这个是为了改为迭代器类类型好访问iterator begin(){return iterator(_head->next);}const_iterator begin()const{return const_iterator(_head->next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}//................
}

3.拷贝构造函数的实现：

list(const list<T>& it)
{empty_node();//初始化for (auto& e : it)//一个个插入数据{push_back(e);//尾插}
}void push_back(const T& x)
{insert(end(), x);//用insert来实现尾插
}iterator insert(iterator pos, const T& x)//第一个参数迭代器类类型，用来访问。
{//申请前（prev）中（prev）以及新结点 三个结点 而插入就是再prev与cur中间。修改他们的前后指针指向。Node* cur = pos._node;Node* prev = cur->prev;Node* newnode = new Node(x);prev->next = newnode;cur->prev = newnode;newnode->next = cur;newnode->prev = prev;++_size;//计入增加大小return newnode;//返回值是迭代器，指向新建的结点。方便后续操作。以及避免迭代器失效的问题
}

第四步：

erase函数以及插入，删除函数和重载=和析构函数：

在链表的删除操作（erase）中，会导致迭代器失效，具体情况如下：

• 被删除节点的迭代器失效原因：链表迭代器是对节点指针的封装，删除操作里，被删除节点会被delete释放内存，指向该节点的迭代器所关联的指针就成了野指针（指向已释放内存），野指针无法安全访问和使用，所以这个迭代器彻底失效。
• 注意事项：删除操作后，被删除节点的迭代器绝对不能再使用（如解引用、递增等），否则会引发未定义行为（程序崩溃、数据错误等）。
• erase函数的应对：erase函数会返回被删除节点的下一个节点的迭代器，以此替代失效的迭代器，保障后续操作（如继续遍历）的安全性。

void swap(list<T>& it)//用库里面的swap函数进行交换，传的是list类的引用
{std::swap(_head, it._head);std::swap(_size, it._size);
}
//重载赋值就是将list的类里面的成员变量给赋值过去
list<T>& operator=(list<T> it)
{swap(it);return *this;
}
//销毁就是要前（prev）中（我们要删的）后（next）三个指针，我们销毁就是将原先指向cur的给改成prev和next之间的关系，返回的是下一个结点
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;
}void push_front(const T& x)
{insert(begin(), x);
}
//为什么要-- 这是因为尾删的数据在哨兵位的前面（end（）返回的是哨兵位）
void pop_back()
{erase(--end());
}void pop_front()
{erase(begin());
}//通过迭代器的遍历来进行，由于erase的是返回下一个结点的，所以不需要像我们之前的++遍历下去
void clear()
{iterator it = begin();while (it != end()){it = erase(it);}_size = 0;
}~list()
{clear();delete _head;_head = nullptr;
}
//计算数据多少
size_t size()const
{return _size;
}

终于结束了！！！

list模拟完整代码：

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace xin
{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)};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*(){return _node->_val;}Ptr 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;}};template<class T>class list{public:typedef list_node<T> Node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<const T, const T&, const T*> const_iterator;iterator begin(){return iterator(_head->next);}const_iterator begin()const{return const_iterator(_head->next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}void empty_node(){_head = new Node;_head->next = _head;_head->prev = _head;_size = 0;}list(){empty_node();}void swap(list<T>& it){std::swap(_head, it._head);std::swap(_size, it._size);}list<T>& operator=(list<T> it){swap(it);return *this;}list(const list<T>& it){empty_node();for (auto& e : it){push_back(e);}}void push_back(const T& x){insert(end(), x);}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->prev;Node* newnode = new Node(x);prev->next = newnode;cur->prev = newnode;newnode->next = cur;newnode->prev = prev;++_size;return 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;--_size;return next;}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}~list(){clear();delete _head;_head = nullptr;}size_t size()const{return _size;}private:Node* _head;size_t _size;};
}

list与vector的对比：

❤️总结

相信坚持下来的你一定有了满满的收获。那么也请老铁们多多支持一下，点点关注，收藏，点赞。❤️