【C++学习笔记】【基础】6.list
·
| 🍕 阿i索 | 个人主页 |
|---|---|
| 《C语言专栏》 | 《C++专栏》 |
| 《数据结构专栏》 | 《LaTeX专栏》 |
| 《软件配置问题》 | 《Linux 专栏》 |
| 待更新... | |
前言.
本篇介绍C++ 标准库（STL）中的list容器。
一、list
list 是 C++ STL 序列容器，头文件 <list>，模板 list<T>，用于存储同类型数据，底层为双向循环链表。内存不连续，每个元素是独立节点，节点包含三块内容：当前元素、前驱节点指针、后继节点指针；节点分散在堆中，靠指针串联，不存在整块连续内存。
二、list的使用
1. 迭代器
迭代器分类：
- 单向迭代器：仅支持自增
++，只能从前向后遍历，不能反向走； - 双向迭代器：支持
++（向后）、--（向前），正反都能遍历； - 随机访问迭代器：除了
++/--，还支持+、-、+=、-=、下标偏移（it+n），可以任意跳转，直接跳到指定位置。
list 底层是双向循环链表，每个节点只存前后指针，只能一步一步前后移动，无法直接跳跃偏移，因此它的迭代器是双向迭代器，只支持++、--，不支持it + 5这种随机跳转操作，不支持下标[]访问。
2. 基础遍历
list<int> lt2 = { 1,2,3,4,5 };
// 1. 迭代器while遍历
list<int>::iterator it2 = lt2.begin();
while (it2 != lt2.end())
{
cout << *it2 << " ";
++it2;
}
// 2. C++11范围for遍历（简洁常用）
for (auto e : lt2)
{
cout << e << " ";
}
要点：
begin()：首元素迭代器；end()：末尾无效位置，循环终止条件- list 无随机访问，不能用
lt2[i]下标访问
3. 插入 insert & 删除 erase 与迭代器失效规则
auto pos = find(lt2.begin(), lt2.end(), 3);
if (pos != lt2.end())
{
lt2.insert(pos, 30); // 在pos前插入元素，pos迭代器不失效
lt2.erase(pos); // 删除pos指向节点，pos立刻失效，后续不能解引用
}
失效：
insert插入：所有原有迭代器、指针全部有效erase删除：仅被删除节点对应的迭代器失效，其余迭代器不受影响
4. 排序 sort
- 全局算法
sort(lt.begin(), lt.end())不可用：全局 sort 要求随机访问迭代器，list 只有双向迭代器 - 必须使用 list内置成员排序函数：
lt2.sort(); // 默认升序，底层链表归并排序
5. 排序 + 去重 unique
unique() 仅能去除相邻重复元素，使用前必须先排序
list<int> lt3 = { 1,2,2,2,3,3,2,3,4,5 };
lt3.sort(); // 1,2,2,2,2,3,3,3,4,5
lt3.unique(); // 清除相邻重复，结果：1,2,3,4,5
5. splice 链表迁移
作用：把另一个 list（或自身）的节点移动到目标位置，无拷贝，仅修改指针，效率极高
三参数格式：目标链表.splice(插入位置, 源链表, 待移动元素迭代器)
list<int> lt4 = { 1,2,3,4,5 };
auto pos2 = find(lt4.begin(), lt4.end(), 4);
// 将lt4中pos2指向的元素，移动到lt4头部
lt4.splice(lt4.begin(),lt4,pos2);
// 执行后结果：4 1 2 3 5
关键特点：
- 移动节点，不拷贝数据，性能远高于 insert+erase
- 移动后原链表对应节点消失，迭代器跟随节点转移依然有效
三、list 优缺点总结
优点
- 头部、中间、尾部增删元素均为 O (1)，仅修改指针
- 插入操作不会导致迭代器失效
- splice 实现链表节点无损迁移
缺点
- 无随机访问，查找、遍历效率低，O (n)
- 每个节点额外存储前后指针，内存开销大
- 不支持全局 sort，缓存命中率低，大批量遍历慢
适用场景
频繁在任意位置插入、删除数据，很少随机读取；不适合大量遍历查询场景。
| 容器 | 适用场景 |
|---|---|
| vector |
1. 需要下标随机访问、频繁读取元素 2. 仅在尾部做插入删除操作 3. 需要使用全局 sort 整体排序 4. 大批量顺序遍历，追求读取速度 |
| list |
1. 频繁头插、头删，或中间任意位置增删元素 2. 需要链表拆分合并（splice） 3. 需要长期保存迭代器，避免频繁失效 |
四、list的模拟实现
模块 1 list_node 节点结构体（存储单元）
1.1 为什么用 struct 不用 class
template<class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& x)
:_next(nullptr), _prev(nullptr), _data(x)
{}
};
class 成员默认私有，链表、迭代器没法直接读写前后指针和数据；要访问就得额外写一堆 get/set 函数，代码冗余。
struct 成员默认公有，节点只用来存数据和指针，不需要封装保护，直接访问更省事。
1.2 构造无缺省参数编译报错问题
问题代码
list_node(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
// 报错调用
_head = new Node;
问题原因：写了带参构造，编译器不会自动生成无参构造，创建节点必须传参数。
哨兵头只是占位空节点，没有业务数据可传，无参创建参数不匹配，编译报错。
方案 1：构造加匿名对象缺省参数
//节点类：双向循环链表存储单元
template<class T>
struct list_node
{
list_node<T>* _next; // 后继节点指针
list_node<T>* _prev; // 前驱节点指针
T _data; // 存储的数据
//节点构造函数
//list_node(const T& x=T())//调用时有参数，解决1：匿名对象做缺省参数
list_node(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};方案 2：构造不设缺省，创建哨兵手动传匿名对象
// 初始化空链表：创建哨兵头节点，完成双向循环闭环
void empty_init()
{
// //调用时有参数，解决2：调用时手动传匿名对象做参数
_head = new Node(T());
_head->_next = _head; // 空链表：头节点后继指向自己
_head->_prev = _head; // 空链表：头节点前驱指向自己
}1.3 节点单独写在外部，不嵌套进 list 类
- 迭代器代码要提前识别 list_node 类型，如果节点写在 list 内部，编译器读到迭代器时找不到节点定义，直接报错。
- 分工分开：节点只存指针和数据，list 只管理整条链表增删、内存，改一块代码不会误改另一块，bug 更好找。
- 插入元素需要随时
new Node(x)创建节点，独立结构体不受 list 类作用域限制，创建更方便。
模块 2 list_iterator 迭代器（遍历游标）
2.1 必须实现 const 迭代器的原因
被 const 修饰的 list 对象，只能调用带 const 的成员函数。
- 没有 const 迭代器，
const list<int> lt无法遍历； - 普通迭代器返回
T&，能修改常量容器数据，破坏只读规则；const 迭代器返回const T&，语法上禁止修改元素。
Ref operator*()
{
return _node->_data;
}
// const对象专属遍历接口
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
2.2如何实现普通迭代器和const迭代器
方案一： 一个模板生成普通 /const 两种迭代器
// 两套类绝大部分代码完全一样，仅返回值不同
// 普通迭代器
template<class T>
struct list_iterator
{
using Node = list_node<T>;
Node* _node;
list_iterator(Node* node) :_node(node) {}
T& operator*() { return _node->_data; }
T* operator->() { return &_node->_data; }
// 前置++、后置++、--、==、!= 一堆重载
};
// const迭代器，95%代码完全重复，只有*、->返回值不同
template<class T>
struct list_const_iterator
{
using Node = list_node<T>;
Node* _node;
list_const_iterator(Node* node) :_node(node) {}
const T& operator*() { return _node->_data; }
const T* operator->() { return &_node->_data; }
// 和上面一模一样的 ++ -- == != 重载，复制粘贴一遍
};
//list双向循环链表容器类
template<class T>
class list
{
using Node = list_node<T>; // 节点类型别名
public:
//迭代器
// 方案一：手写两个迭代器类：
using iterator = list_iterator<T>;
using const_iterator = list_const_iterator<T>;//重新定义一个const迭代器类
...
}方案二：一套模板同时实现普通迭代器、const 迭代器
两套迭代器只有*it、it->返回值不一样，其余遍历逻辑完全重复。 增加 Ref、Ptr 模板参数控制返回类型，编译器自动生成两份迭代器代码，不用手动复制粘贴，修改遍历逻辑只改一处。
//一个模板类由编译器自动实例化出普通迭代器、const迭代器两种类型
template<class T, class Ref, class Ptr>
struct list_iterator
{
using Self = list_iterator<T, Ref, Ptr>;
using Node = list_node<T>;
Node* _node;
list_iterator(Node* node)
:_node(node)
{}
// 解引用返回类型由模板参数Ref控制
Ref operator*()
{
return _node->_data;
}
// 箭头返回类型由模板参数Ptr控制
Ptr operator->()
{
return &_node->_data;
}
// ++、--、==、!= 全部只写一遍，两套迭代器共用逻辑
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& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
// list内部定义两种迭代器
using iterator = list_iterator<T, T&,T*>;
using const_iterator = list_iterator<T,const T&,const T*>;
（1）模板参数作用：
T：链表存储的数据类型；Ref：控制*it返回的引用类型；Ptr：控制it->返回的指针类型。
（2）编译器会根据传入的模板参数，自动生成两份独立代码：
list_iterator<int, int&, int*>→ 普通 iterator；list_iterator<int, const int&, const int*>→ const_iterator；
（3）遍历移动（++/--/ 判断相等）共用同一套逻辑，只写一次；
（4）解引用区分读写：
- 普通迭代器
*it返回T&，可以修改元素*it = 100； - const 迭代器
*it返回const T&，只能读取，不能赋值修改；
2.3 后置 ++ 不能返回引用，否则野引用崩溃
错误代码
Self& operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
正确代码
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
后置 ++ 逻辑为先返回原值再移动指针，必须创建局部临时 tmp 保存初始状态。 tmp 是函数内局部变量，函数结束内存销毁，如果返回 tmp 的引用，后续使用这个引用会访问已销毁内存，程序崩溃；值拷贝返回临时对象无风险。
2.4 迭代器不需要自定义析构
迭代器里只有节点指针，仅记录节点地址，不管理堆内存；所有节点都是 list 统一 new、统一 delete。
如果给迭代器写析构delete _node，多个迭代器指向同一个节点会多次释放内存，循环临时迭代器还会误删链表有效节点，程序崩溃，默认析构足够使用。
2.5 迭代器单独封装，不写进 list 内部
我们代码的书写顺序：先写节点，再写迭代器，最后写链表。迭代器里面要用到节点，链表里面要用到迭代器。
情况 1：迭代器写在 list 里面编译器，开始读 list 代码，刚读到里面嵌套的迭代器，list 都还没完整读完。后面 list 的 begin、end 函数要用到这个迭代器，但此时这个迭代器还没被编译器完整识别，两边互相等着对方定义，编译器识别不出类型，直接报错。
情况 2：迭代器写在外面编译器，先读完节点，再完整读完迭代器，最后才读链表。链表使用的是已经提前定义好的迭代器，不存在互相等对方的情况，编译器能正常识别，不会报错。
模块 3 list 初始化、构造相关
3.1 empty_init 初始化空双向循环带头链表
void empty_init()
{
_head = new Node(T());
_head->_next = _head;
_head->_prev = _head;
}
链表带哨兵头节点，不存有效数据；空链表头节点前后指针都指向自己形成闭环。
好处：多处代码都需要创建空链表，重复写相同初始化代码会冗余。拷贝构造、普通构造、区间构造、初始化列表构造，全都需要先把链表初始为空。如果不抽成 empty_init，每个构造函数都要重复写创建哨兵头、头尾自指向、初始化 size 的代码，改逻辑要多处同步修改。
3.2 initializer_list 构造，支持花括号初始化
list(std::initializer_list<T> il)
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
}
支持list<int> lt{1,2,3,4}写法，编译器自动把大括号元素打包传入函数，循环尾插完成初始化，贴合标准容器用法。使用前需要包含#include <initializer_list>。
3.3 迭代器区间模板构造
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while(first!=last)
{
push_back(*first);
++first;
}
}
作用
接收一段数据的开头、结尾游标，把这段数据全部复制，生成新链表。
InputIterator 通用输入迭代器，不限制只能使用 list 自身迭代器，只要支持 * 取值、++ 向后移动、!= 判断结束的游标都能传入。
能接收哪些数据
- 另一个 list 的首尾迭代器，复制整条链表；
- 其他 STL 容器的迭代器：所有标准容器的
begin()、end()都能传入： vector、string、deque、set、map、unordered_set、unordered_map - 普通数组首尾指针：数组名是首元素指针，指针支持
*、++、!=，满足输入迭代器要求。 - 自定义自定义容器 / 自定义迭代器：只要自己写的游标满足三个操作：解引用
*it、自增++it、判等it != end，就能传入这个区间构造。
模块 4 拷贝构造、赋值重载（深浅拷贝）
传统写法
// 拷贝构造
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
push_back(e);
}
// 赋值重载
list<T>& operator=(const list<T>& lt)
{
if(this != <)
{
clear();
for(auto& e : lt)
push_back(e);
}
return *this;
}
现代写法
// 拷贝构造
list(const list<T>& lt)
{
empty_init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
// 赋值重载
list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
解释
- 编译器默认拷贝是浅拷贝，只复制头指针，两个对象共用节点，析构时重复释放内存崩溃，必须手动深拷贝新建节点；
- 传统写法拷贝、赋值重复循环代码，赋值需要手动判断自赋值；
- swap 优化：临时对象自动完成深拷贝，仅交换头指针和 size，交换操作 O (1) 极快；临时对象出作用域自动释放旧节点，不用手动清理。
模块 5 增删接口 insert erase push pop
5.1 push/pop 全部复用 insert/erase，减少重复代码
写法1（不复用）：
void push_back(const T& x)
{
Node* newnode = new Node(x);
Node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
写法2：
void push_back(const T& x){ insert(end(), x); }
void push_front(const T& x){ insert(begin(), x); }
void pop_back(){ erase(--end()); }
void pop_front(){ erase(begin()); }
头尾增删本质都是节点指针重链接，只是位置不同。单独写四套指针逻辑，修改时要同步改四处，容易漏写出 bug；复用核心 insert、erase，只维护一套链接代码。
5.2 insert 插入，所有迭代器不失效
void insert(iterator pos, const T& x)
{
Node* cur = pos._node; // pos指向的节点
Node* prev = cur->_prev; // pos节点的前驱节点
Node* newnode = new Node(x); // 新建待插入节点
// 双向指针重新链接：prev <-> newnode <-> cur
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size; // 有效节点数量+1
}insert 只在两个原有节点中间新增节点，原有节点内存地址不变，所有指向旧节点的迭代器依然有效。对比 vector 插入会移动元素，全部迭代器失效。
5.3 erase 删除，仅被删位置迭代器失效，必须接收返回值
错误循环写法
while(it != end())
{
erase(it); // it指向已释放节点，变成野指针，循环崩溃
}
正确代码
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
// 跳过待删除节点，前后节点直接相连
prev->_next = next;
next->_prev = prev;
delete cur; // 释放被删除节点堆内存
--_size; // 有效节点数量-1
return iterator(next); // 返回下一个节点的迭代器，解决迭代器失效问题
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
erase 会 delete 当前节点，原迭代器变成野指针；函数提前记录下一个有效节点并返回，循环用 it 接收返回值，保证每次迭代器合法。只有被删除位置迭代器失效，其余不受影响。
模块 6 clear、析构、size 效率优化
6.1 不手动释放堆节点会内存泄漏
void clear()
{
iterator it = begin();
while (it!= end())
it = erase(it);
}
~list()
{
clear();
delete _head;
_head = nullptr;
_size = 0;
}
有效节点、哨兵头节点都在堆上开辟，堆内存不会自动回收。clear 循环释放全部数据节点，析构额外释放哨兵头，完整释放所有堆内存，无内存泄漏。
6.2 维护_size 成员，O (1) 获取链表长度
写法1（低效）：
size_t size()const
{
size_t n = 0;
for (auto& e : *this)
++n;
return n;
}
写法2：
size_t size()const
{
return _size;
}
写法1每次获取长度都要遍历整条链表，数据量大速度慢；
优化：每次插入++_size、删除--_size实时记录数量，直接返回变量无需遍历，查询效率极高。
模块七：list的模拟实现
list.h
#pragma once
#include <initializer_list>
#include <iostream>
namespace asuo
{
//节点类：双向循环链表存储单元
template<class T>
//使用struct，struct所有成员默认public，不需要封装访问接口
struct list_node
{
list_node<T>* _next; // 后继节点指针
list_node<T>* _prev; // 前驱节点指针
T _data; // 存储的数据
//节点构造函数
//list_node(const T& x=T())//调用时有参数，解决1：匿名对象做缺省参数
list_node(const T& x)
:_next(nullptr)
, _prev(nullptr)
, _data(x)
{}
};
//迭代器模板类
//分开写普通迭代器、const迭代器两个独立类，运算符重载代码大部分重复，维护成本极高
//解决：增加两个模板参数Ref、Ptr，一个模板类由编译器自动实例化出普通迭代器、const迭代器两种类型
template<class T, class Ref, class Ptr>
struct list_iterator
{
using Self = list_iterator<T, Ref, Ptr>; // 类型别名，简化当前迭代器类型书写
using Node = list_node<T>; // 节点类型别名
Node* _node; // 迭代器本质：存储一个节点指针，充当链表遍历的“游标”
//迭代器构造：接收节点指针，绑定游标位置
list_iterator(Node* node)
:_node(node)
{
}
//迭代器为什么不需要手动写析构函数？
//底层原理：迭代器只保存节点地址，只是借用指针，不拥有堆内存所有权；所有节点都是list容器通过new创建、delete释放
//如果手动写析构执行delete _node，会出现两种致命bug：
//1、多个迭代器同时指向同一个节点，迭代器销毁时重复delete，双重释放内存，程序直接崩溃
//2、for循环内临时迭代器出作用域自动销毁，误删除链表有效节点，链表结构彻底损坏
//结论：编译器默认生成的析构足够使用，无需自定义析构
//运算符重载
// *it=1，解引用运算符 *it
//模板参数Ref作用区分读写：普通迭代器传T&，const迭代器传const T&
//const迭代器解引用返回只读常引用，语法层面禁止修改容器元素，保证const对象只读语义
Ref operator*()
{
return _node->_data; // 返回节点数据的引用
}
//箭头运算符 it->
//模板参数Ptr区分指针类型：普通迭代器T*，const迭代器const T*
Ptr operator->()
{
return &_node->_data; // 返回数据的地址，支持结构体成员访问
}
//前置++ ++it
Self& operator++()
{
_node = _node->_next; // 游标移动到下一个节点
return *this; // 返回自身，支持连续++操作
}
//后置++ it++
//如果错误写成返回值Self&，返回局部临时对象引用，函数结束临时对象销毁，产生野引用，访问直接崩溃
//解决：后置自增以值拷贝返回临时对象，前置返回自身引用
Self operator++(int)
{
Self tmp(*this); // 先保存当前迭代器快照
_node = _node->_next; // 游标后移
return tmp; // 返回未移动前的旧迭代器副本
}
//前置-- --it
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置-- it--
//和后置++一样，不能返回引用，只能返回值
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
//判断迭代器不相等
bool operator!=(const Self& s) const
{
return _node != s._node; // 只对比内部存储的节点地址
}
//判断迭代器相等
bool operator==(const Self& s) const
{
return _node == s._node;
}
};
////const迭代器类
//template<class T>
//struct list_const_iterator
//{
// using Self = list_const_iterator<T>;
// using Node = list_node<T>;
// Node* _node;
// //构造
// list_const_iterator(Node* node)
// :_node(node)
// {
// }
// //迭代器不需要写析构
// //运算符重载
// // *it=1
// const T& operator*()//返回const别名，能读不能修改
// {
// return _node->_data;
// }
// // ++it
// Self& operator++()
// {
// _node = _node->_next;
// return *this;
// }
// // it++
// Self& operator++(int)
// {
// Self tmp(*this);
// _node = _node->_next;
// return tmp;
// }
// // --it
// Self& operator--()
// {
// _node = _node->_prev;
// return *this;
// }
// // it--
// Self& operator--(int)
// {
// Self tmp(*this);
// _node = _node->_prev;
// return *tmp;
// }
// bool operator!=(const Self& s) const
// {
// return _node != s._node;
// }
// bool operator==(const Self& s) const
// {
// return _node == s._node;
// }
//};
//list双向循环链表容器类
template<class T>
class list
{
using Node = list_node<T>; // 节点类型别名
public:
////迭代器
// 方案一：手写两个迭代器类：
//using iterator = list_iterator<T>;
//using const_iterator = list_const_iterator<T>;//重新定义一个const迭代器类
// 方案二：利用同一个迭代器模板，定义两种迭代器
// 普通迭代器：可读可写元素
using iterator = list_iterator<T, T&, T*>;
// const迭代器：仅读取，禁止修改元素
using const_iterator = list_iterator<T, const T&, const T*>;
// 普通list对象调用begin()，返回可修改迭代器
iterator begin()
{
return iterator(_head->_next); // 第一个有效节点是哨兵头的下一个
}
iterator end()
{
return iterator(_head); // end代表哨兵头节点，遍历结束标志
}
// 带const修饰的list对象只能调用本版本begin/end
// 如果不写const重载的begin/end，const list无法遍历；或者拿到可修改迭代器，篡改常量容器数据，违背C++ const语法规则
const_iterator begin()const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
// 初始化空链表：创建哨兵头节点，完成双向循环闭环
void empty_init()
{
// //调用时有参数，解决2：这里用匿名对象做参数
_head = new Node(T());
_head->_next = _head; // 空链表：头节点后继指向自己
_head->_prev = _head; // 空链表：头节点前驱指向自己
}
// 无参构造：创建空链表
list()
{
empty_init();
}
// initializer_list构造：支持花括号直接初始化 list<int> lt{1,2,3,4}
list(std::initializer_list<T> i1)
{
empty_init();
for (auto& e : i1)
{
push_back(e);
}
}
//迭代器区间构造：把其他容器 / 数组一段区间的数据拷贝到当前 list 中
template <class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while (first != last)
{
push_back(*first);
++first;
}
}
// n个相同值构造：创建n个val元素的链表
list(size_t n, T val = T())
{
empty_init();
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
// 析构函数
// 所有节点、哨兵头节点都是new在堆上开辟，不手动释放会永久占用内存，造成内存泄漏
// 解决方案：先clear释放全部有效数据节点，再单独释放哨兵头节点_head
~list()
{
clear();
delete _head;
_head = nullptr;
_size = 0;
}
////传统拷贝构造
////缺陷1：代码重复，赋值重载需要再写一遍循环插入逻辑
////缺陷2：没有利用临时对象自动析构，内存管理繁琐
//list(const list<T>& lt)
//{
// empty_init();
// for (auto& e : lt)
// {
// push_back(e);
// }
//}
////传统赋值重载
////缺陷1：必须手动判断自赋值 if(this != <)，忘记写会内存出错
////缺陷2：逻辑和拷贝构造高度重复，维护麻烦
//list<T>& operator=(const list<T>& lt)
//{
// if (this != <)
// {
// clear();
// for (auto& e : lt)
// {
// push_back(e);
// }
// }
// return *this;
//}
//现代写法：拷贝构造
//编译器默认生成的拷贝构造是浅拷贝，只复制_head指针，两个list共用同一批堆节点，析构时重复delete，程序崩溃
//解决：创建临时对象tmp完成深拷贝，swap交换当前对象与tmp底层资源，tmp出作用域自动释放旧数据
list(const list<T>& lt)
{
empty_init();
list<T> tmp(lt.begin(), lt.end()); // tmp深拷贝原链表所有元素
swap(tmp); // 交换头节点指针、size变量
}
//现代赋值重载lt1=lt3：参数传值自动生成临时对象，无需手动判断自赋值
list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}
//交换两个list底层资源，只交换指针和size，O(1)时间复杂度，效率高
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//清空所有有效数据节点，保留哨兵头节点
void clear()
{
iterator it = begin();
while (it != end())
{
//erase删除节点后原it指向已释放内存，变成野指针，如果直接写erase(it)，下一轮循环访问it程序崩溃
//解决：erase会返回下一个合法迭代器，循环必须用it接收返回值 it = erase(it);
it = erase(it);
}
}
////缺陷：push_back/push_front/pop_back/pop_front都要手写一套双向指针链接代码，大量重复代码
//void push_back(const T& x)
//{
// Node* newnode = new Node(x);
// Node* tail = _head->_prev;
// tail->_next = newnode;
// newnode->_prev = tail;
// newnode->_next = _head;
// _head->_prev = newnode;
//}
//尾插，复用insert核心逻辑，消除重复指针操作代码
void push_back(const T& x)
{
insert(end(), x);
}
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
//尾删
void pop_back()
{
erase(--end());
}
//头删
void pop_front()
{
erase(begin());
}
//在pos迭代器指向节点的前面插入新元素
//list插入不会造成任何迭代器失效，只会新增节点，原有所有节点内存地址不变
void insert(iterator pos, const T& x)
{
Node* cur = pos._node; // pos指向的节点
Node* prev = cur->_prev; // pos节点的前驱节点
Node* newnode = new Node(x); // 新建待插入节点
// 双向指针重新链接：prev <-> newnode <-> cur
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
++_size; // 有效节点数量+1
}
//删除pos迭代器指向的节点，返回下一个有效迭代器
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
// 跳过待删除节点，前后节点直接相连
prev->_next = next;
next->_prev = prev;
delete cur; // 释放被删除节点堆内存
--_size; // 有效节点数量-1
return iterator(next); // 返回下一个节点的迭代器，解决迭代器失效问题
}
//获取链表有效元素个数
size_t size()const
{
////低效写法：每次调用size都要遍历整条链表统计数量，时间复杂度O(n)
//size_t n = 0;
//for (auto& e : *this)
//{
// ++n;
//}
//return n;
return _size; // 维护成员变量，O(1)直接返回长度
}
private:
Node* _head; // 双向循环链表哨兵头节点，不存储有效数据
size_t _size = 0;// 记录当前有效节点总数
};
}test.cpp测试文件
#define _CRT_SECURE_NO_WARNINGS
#include"list.h"
#include<iostream>
using namespace std;
// 测试1：尾插、普通迭代器遍历、范围for循环
void test_list1()
{
cout << "========== test_list1 尾插+迭代器+范围for ==========\n";
asuo::list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
// 1、普通while迭代器遍历（可读可修改）
asuo::list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 2、支持迭代器就自动支持范围for循环（编译器底层替换成迭代器遍历）
for (auto e : lt)
{
cout << e << " ";
}
cout << "\n\n";
}
// 测试2：头插、头删、尾删、size()获取长度
void test_list2()
{
cout << "========== test_list2 头插/头删/尾删/size ==========\n";
asuo::list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_front(-1);
lt.push_front(-2);
cout << "头插后链表：";
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.pop_back();
lt.pop_back();
lt.pop_front();
lt.pop_front();
cout << "两次尾删+两次头删后链表：";
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
cout << "当前有效元素个数size：" << lt.size() << "\n\n";
}
// 工具函数：接收const list，测试const_iterator只读迭代器
void Print(const asuo::list<int>& lt)
{
// 传入const引用，只能使用const_iterator，解引用无法修改数据
asuo::list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
// 测试3：initializer_list花括号初始化、拷贝构造、赋值重载、const迭代器
void test_list3()
{
cout << "========== test_list3 花括号初始化/拷贝构造/赋值重载 ==========\n";
// 花括号初始化，调用initializer_list构造函数
asuo::list<int> lt1 = { 1,2,3,4,5,6 };
cout << "lt1 初始化结果：";
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
// 拷贝构造（现代swap深拷贝写法）
asuo::list<int> lt2(lt1);
cout << "lt2 拷贝lt1结果：";
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
// 赋值运算符重载
asuo::list<int> lt3 = { 10,20,30 };
lt1 = lt3;
cout << "lt1 = lt3赋值后lt1：";
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
// 调用Print，测试const_iterator只读遍历
cout << "Print函数const迭代器遍历lt1：";
Print(lt1);
cout << "\n";
}
// 自定义结构体，测试operator->箭头运算符重载
struct A
{
int _a1;
int _a2;
A(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{
}
};
void test_list4()
{
cout << "========== test_list4 自定义结构体 + operator->箭头重载 ==========\n";
asuo::list<A> lt;
// 花括号隐式构造A对象插入链表
lt.push_back({ 1,1 });
lt.push_back({ 2,2 });
lt.push_back({ 3,3 });
asuo::list<A>::iterator it = lt.begin();
while (it != lt.end())
{
// 两种写法等价：(*it)._a1 / it->_a1
//cout << (*it)._a1 << ":" << (*it)._a2 << endl;
cout << it->_a1 << ":" << it->_a2 << endl;
++it;
}
cout << "\n";
}
int main()
{
// 依次放开对应函数测试不同功能
test_list1();
test_list2();
test_list3();
test_list4();
return 0;
}更多推荐
7
0- 0
已为社区贡献4条内容
所有评论(0)