贵州省城乡建设部网站首页,wordpress怎么链接,wordpress充值会员,自助建站seo目录
list的使用#xff1a;
构造与赋值
元素访问
修改操作
容量查询
链表特有操作
拼接#xff08;Splice#xff09;
C11 新增方法
注意#xff1a; stl_list的模拟实现#xff1a;
一、链表节点设计的艺术
1.1 结构体 vs 类的选择
二、迭代器实现的精髓
2…目录
list的使用
构造与赋值
元素访问
修改操作
容量查询
链表特有操作
拼接Splice
C11 新增方法
注意 stl_list的模拟实现
一、链表节点设计的艺术
1.1 结构体 vs 类的选择
二、迭代器实现的精髓
2.1 为什么需要自定义迭代器迭代器在本文章后面还会更新
2.2 运算符重载的细节实现
三、链表类的完整实现
3.1 构造函数与哨兵节点
3.2 迭代器范围获取
3.3 核心操作实现解析
插入操作:insert()
尾插push_back()
头插push_front()
删除操作:erase()
尾删pop_back()
头删pop_front()
辅助函数实现size()、empty()
析构函数销毁链表x~list()、清除数据clear()
拷贝构造list(const list lt)
赋值list operator()、swap()
为什么参数要「按值传递」
运作原理
优势
四、关键问题深度探讨 自定义类型更新原iterator类编辑
3.方法三重载 operator-()
内存布局可视化
PrintList()、const_iterator
方法二方法一使代码冗余我们需要学习一种方法能够解决这个问题。
完整代码 本文章主要简要讲解list容器的使用与详细讲解list模拟实现以及相关问题上所用到完整代码在文章末尾
list的使用
构造与赋值 构造函数 listint lt; // 空链表
listint lt2(5, 10); // 5 个元素每个初始化为 10
listint lt3(lt2.begin(), lt2.end()); // 通过迭代器范围构造
listint lt4 {1, 2, 3}; // 初始化列表C11 赋值操作 lt lt2; // 深拷贝赋值
lt.assign(3, 100); // 替换内容为 3 个 100
lt.assign(lt2.begin(), lt2.end()); // 通过迭代器赋值 元素访问 首尾元素front()、back() int front lt.front(); // 首元素不可修改空链表
int back lt.back(); // 尾元素不可修改空链表 迭代器begin()、rbegin() listint::iterator it lt.begin(); // 正向迭代器
listint::reverse_iterator rit lt.rbegin(); // 反向迭代器 修改操作 插入 lt.push_front(0); // 头部插入
lt.push_back(4); // 尾部插入auto pos lt.begin();
lt.insert(pos, 99); // 在迭代器位置前插入
lt.insert(pos, 3, 88); // 插入 3 个 88 删除 lt.pop_front(); // 删除头部元素
lt.pop_back(); // 删除尾部元素lt.erase(pos); // 删除迭代器位置元素
lt.erase(pos, lt.end()); // 删除迭代器范围lt.remove(4); // 删除所有值为 4 的节点 清空链表clear lt.clear(); // 清空所有元素 容量查询
bool isEmpty lt.empty(); // 是否为空
size_t size lt.size(); // 元素个数O(n) 时间复杂度
lt.resize(10); // 调整链表大小 链表特有操作 拼接Splice // 将 lt2 的全部内容移动到 lt 的 pos 位置前
lt.splice(pos, lt2); // lt2 会被清空// 移动单个元素
auto it2 lt2.begin();
//pos为目标位置it2为需要移动的单个元素拿走it2再尾差pos改变节点的指向
lt.splice(pos, lt2, it2);// 移动范围
lt.splice(pos, lt2, lt2.begin(), lt2.end()); 注意被转移的节点会被清空 合并Merge // 前提lt 和 lt2 必须已按相同顺序排序升序或降序
lt.sort(); // 默认升序
lt2.sort();
lt.merge(lt2); // 合并后 lt2 为空 排序Sort lt.sort(); // 默认升序
lt.sort(greaterint()); // 降序需包含 functional 去重Unique lt.sort(); // 必须先排序
lt.unique(); // 删除连续重复元素 反转Reverse lt.reverse(); // 反转链表顺序 C11 新增方法 原地构造Emplace lt.emplace_front(10); // 在头部直接构造对象避免拷贝
lt.emplace_back(20); // 尾部构造
lt.emplace(pos, 30); // 指定位置构造 移动语义 listint lt5 std::move(lt); // 移动构造高效转移资源 注意 merge 前必须排序 // 错误示例lt 是降序lt1 是升序
lt.sort(greaterint()); // 降序
lt1.sort(); // 升序
lt.merge(lt1); // 未定义行为// 正确做法统一顺序
lt.sort(); // 升序
lt1.sort();
lt.merge(lt1); unique 必须配合 sort // 错误用法未排序时去重
lt.unique(); // 只能删除连续重复// 正确用法
lt.sort();
lt.unique(); // 删除所有重复 迭代器失效 在插入/删除操作后指向被修改位置的迭代器会失效需重新获取。 stl_list的模拟实现
一、链表节点设计的艺术
1.1 结构体 vs 类的选择
templateclass T
struct ListNode {ListNodeT* _next; // 后继指针ListNodeT* _prev; // 前驱指针T _data; // 存储数据// 默认构造函数初始化三要素ListNode(const T x T()):_next(nullptr),_prev(nullptr),_data(x){}
};
设计要点分析 使用struct而非class的深层考量 默认public访问权限便于链表类直接操作节点指针 符合C标准库实现惯例增强代码可读性 节点本身无需封装属于链表内部实现细节 三指针设计哲学 _next和_prev构成双向链接的基石 _data采用模板类型支持任意数据类型存储 默认构造函数的巧妙设计同时支持无参构造和值初始化 内存布局可视化 ------ ------ ------
| prev |--| prev |--| prev |
| data | | data | | data |
| next |---| next |---| next |
------ ------ ------ 二、迭代器实现的精髓
2.1 为什么需要自定义迭代器迭代器在本文章后面还会更新
templateclass T
struct ListIterator {typedef ListNodeT Node;typedef ListIteratorT Self;Node* _node; // 核心封装节点指针// 构造函数实现指针到迭代器的转换ListIterator(Node* node):_node(node){}
}; 关键问题解答 原生指针的局限性 无法直接通过操作跳转到下一个节点 解引用操作不符合链表数据访问需求 无法正确比较链表节点的位置关系 迭代器设计模式的优势 统一容器访问接口 隐藏底层数据结构差异 支持算法泛型编程 2.2 运算符重载的细节实现
// 前置直接修改自身
Self operator() {_node _node-_next; // 关键跳转逻辑return *this;
}// 后置返回临时对象
Self operator(int) {Self tmp(*this); // 拷贝当前状态_node _node-_next;return tmp; // 返回旧值
}//1. --it
Self operator--()
{_node _node-_prev;return *this;
}
//2. it--
Self operator--(int)
{Self tmp(*this);_node _node-_prev;return tmp;
}// 解引用访问节点数据
T operator*() {return _node-_data; // 返回引用支持修改
}//两个迭代器是否相等
bool operator!(const Self it)
{//即比较节点的指针节点的指针相同他们就相同return _node ! it._node;
}// 相等性比较的本质
bool operator(const Self it) {return _node it._node; // 指针地址比较
} 实现细节剖析 前置与后置的差异 性能考量避免不必要的拷贝 语法区分int参数占位符 解引用操作的注意事项 返回引用以实现左值操作 与const迭代器的兼容性设计 比较大小是否需要重载不需要一个类是否要重载一个运算符需要看他是否有意义节点后面的地址不能保证比前面的地址大所以没什么意义。不需要重载 三、链表类的完整实现
3.1 构造函数与哨兵节点
重新定义类型名称便于阅读
templateclass Tclass list {typedef ListNodeT Node;public://在这里定义好类型typedef ListIteratorT iterator;};list() {_head new Node; // 创建哨兵节点_head-_next _head; // 自环初始化_head-_prev _head;_size 0; // 尺寸计数器
} 哨兵节点的精妙之处 统一空链表和非空链表的操作 简化边界条件处理 保证迭代器end()的有效性 内存布局示意图 [HEAD] - [NODE1] - [NODE2] - [HEAD] 3.2 迭代器范围获取 iterator begin()
{// 1.有名对象//iterator it(_head-_next);//return it;// 2.隐式类型转换(单参数的构造函数支持隐式类型的转换)//return _head-_next;// 3.匿名对象 return iterator(_head-_next); // 隐式转换
}iterator end() {return iterator(_head); // 哨兵即终点
} 统一使用匿名对象构造迭代器 begin()指向首元节点end()指向哨兵节点 支持C11范围for循环的关键 3.3 核心操作实现解析
插入操作:insert() 选定位置插入insert()
//在pos位置插入data
void insert(iterator pos, const T data) {Node* current pos._node;Node* newnode new Node(data); // 内存申请// 四步链接法Node* prev current-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next current;current-_prev newnode;_size; // 维护尺寸
}
尾插push_back()
void push_back(const T x)
{//1.还未写insert()时写的push_back()//Node* newnode new Node(x);//Node* tail _head-_prev; //指定被插的节点//tail-_next newnode;//newnode-_prev tail;//newnode-_next _head;//_head-_prev newnode;//2.写了insert()后写的push_back()insert(end(), x);
}
头插push_front()
void push_front(const T x)
{insert(begin(), x);
}
四步链接法示意图
Before: [PREV] - [CURRENT]
After: [PREV] - [NEWNODE] - [CURRENT] 删除操作:erase() 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; // 更新尺寸return iterator(next); // 返回有效迭代器
} 迭代器失效问题 删除操作使当前迭代器失效 返回新迭代器的必要性 正确使用模式示例 auto it lst.begin();
while(it ! lst.end()) {if(condition) {it lst.erase(it); // 接收返回值} else {it;}
} 尾删pop_back() //尾删 要--,不然删的是head(哨兵位)
void pop_back()
{erase(--end());
}头删pop_front() //头删
void pop_front()
{erase(begin());
} 辅助函数实现size()、empty() size_t size() const { return _size; } // O(1)时间复杂度bool empty() { return _size 0; } // 高效判空性能优化点 使用_size变量避免遍历计数 empty()的常数时间复杂度 clear()的通用实现方式 析构函数销毁链表x~list()、清除数据clear()
//清除掉所有数据有没有清除掉头结点并没有在析构函数中清除
void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}~list()
{clear();delete _head;_head nullptr;
}
拷贝构造list(const listT lt) 为了拷贝构造的实现方便我们将空链表的制作做了一个成员函数因此默认的无参构造函数可以直接使用这个成员函数 void empty_init(){//创建一个头结点_head new Node;_head-_next _head;_head-_prev _head;_size 0;x}//构造函数 list(){empty_init();} 拷贝构造,默认拷贝构造是浅拷贝所以需要我们自己实现一个深拷贝防止指向同一个空间析构两次同一空间导致错误 //lt2(lt1)
list(const listT lt)
{//首先在这里我们先创建空链表//也就是lt2.empty_init()直接给lt2创建一个空链表即创建一个哨兵位头结点empty_init();//直接遍历一遍lt1尾插for (auto e : lt)//这里一定要加引用因为如果T是string就浅拷贝了{push_back(e);}
} 赋值listT operator()、swap()
调用库里的swapalgorithm
void swap(listT lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}//赋值
//lt1 lt3
listT operator(listT lt) //lt lt3;
{swap(lt);
} 为什么参数要「按值传递」 我的代码中赋值运算符的实现如下 listT operator(listT lt) { // 参数按值传递swap(lt);return *this;
} 运作原理 按值传递参数调用 operator 时lt 是传入对象的副本触发拷贝构造函数。 交换资源通过 swap 将当前对象的 _head 和 _size 与副本 lt 交换。 自动析构副本函数结束时临时副本 lt 被析构释放原对象的旧资源。 优势 天然处理自我赋值即使 lt1 lt1;参数 lt 是原对象的副本交换后旧资源由副本释放。 异常安全拷贝过程生成 lt在交换前完成若拷贝失败不会影响原对象。 小技巧需要析构就需要自己写深拷贝不需要析构默认浅拷贝
四、关键问题深度探讨 自定义类型更新原iterator类 出现报错的原因是内置类型才支持流插入提取而A是自定义类型所以在这里不支持需要自己写运算符重载。 1.方法一改变提取方式 cout (*it)._a1 : (*it)._a2 endl;2.方法二写流插入 省略 3.方法三重载 operator-() //it-T* operator-(){return _node-_data;//返回的是_data的地址} 实际上用箭头会方便很多。 编译器为了可读性省略了一个→ cout it-_a1 : it-_a2 endl;实现原理 编译器隐藏了一个箭头实际上是: it--_a1 (it.operator-())-_a1, (it.operator-())返回的是data的地址即T*在这里就是我们的自定义类型 A*有了A*此时就可以访问直接访问结构体成员_a1_a2。从而得到他们的值。这里将it的行为当成A* 。 内存布局可视化 ---------------------
| ListIterator对象 |
| _node: 0x1000 |
---------------------|v
--------------------- ---------------------
| ListNodeA节点 | | A结构体实例 |
| _prev: 0x2000 | | _a1: 1 |
| _next: 0x3000 | | _a2: 5 |
| _data: 0x4000 |------------------------
--------------------- 当调用 it-_a1 时 通过 _node 找到数据节点 获取 _data 的内存地址0x4000 通过指针访问结构体成员 _a1 PrintList()、const_iterator 因为现在的clt是一个const成员变量而begin()、end()还未加const
加完const后编译通过权限可以缩小但是不能扩大非const成员可以调用const成员const成员不能调用非const成员 iterator begin() const{return iterator(_head-_next);}iterator end() const{return iterator(_head);}
这样真的就没有问题了吗
按理来说普通迭代器是能够修改的但这里是const,是不能修改的 实际上我们测试了一下被修改了说明代码有问题
原因出在这里由于这里可以让非const对象访问访问后返回的是普通迭代器普通迭代器是支持被修改的 所以我们需要再重载const版本的,返回值也要记得修改
//const版本
const_iterator begin() const
{return const_iterator(_head-_next);
}const_iterator end() const
{return const_iterator(_head);
}
const迭代器需要的不是是迭代器不能被修改而是迭代器指向的的内容不能被修改所以不能用const iterator因为它是避免迭代器被修改。
方法一需要重新定义一个ListConstIterator的类且在链表前面定义类型的时候加上const_iterator
对于ListConstIterator类实际上只有的这里的逻辑和ListIterator不同*it 10会显示报错了 图示 方法二方法一使代码冗余我们需要学习一种方法能够解决这个问题。 而我们知道凡是类型不同就可以用模版来解决 Ref--reference,引用 Ptr --Pointer
如图本质相当于我们写了一个类模版编译器实例化生成了两个类 最后达到目的。 完整代码
#pragma once
#includeassert.h
#includeiostream
//#includevector
//#includelist
#includealgorithmusing namespace std;
namespace bit
{templateclass T//注意一下这里用的struct数据想要全部公有的时候用structstruct ListNode{ListNodeT* _next;ListNodeT* _prev;T _data;ListNode(const T x T()):_next(nullptr),_prev(nullptr),_data(x){}private:};//普通迭代器templateclass T ,class Ref , class Ptrstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;Node* _node;//从本源来说迭代器还是一个节点的指针ListIterator(Node* node):_node(node){}//我们最想实现的是对于指针的即运算符的重载//1.itSelf operator(){//是怎么到下一个节点的即交换值_node _node-_next;return *this;}//2.itSelf operator(int){//1.调用拷贝构造这里是一个浅拷贝把一个迭代器给另外一个迭代器it1,it2都指向一个节点Self tmp(*this);_node _node-_next;//2.迭代器是否需要写析构不需要因为资源是属于链表的return tmp;}//1. --itSelf operator--(){_node _node-_prev;return *this;}//2. it--Self operator--(int){Self tmp(*this);_node _node-_prev;return tmp;}//解引用*it 返回的是_data//T operator*()Ref operator*(){return _node-_data;}//it-//T* operator-()Ptr operator-(){return _node-_data;//返回的是_data的地址}//两个迭代器是否相等bool operator!(const Self it){//即比较节点的指针节点的指针相同他们就相同return _node ! it._node;}bool operator(const Self it){return _node it._node;}//比较大小是否需要重载不需要一个类是否要重载一个运算符需要看他是否有意义//节点后面的地址不能保证比前面的地址大所以没什么意义。不需要重载//迭代器的重点指针用类似指针的方式来访问容器//begin()和end()谁能提供链表};//迭代器//templateclass T//struct ListConstIterator//{// typedef ListNodeT Node;// typedef ListConstIteratorT Self;// Node* _node;// //从本源来说迭代器还是一个节点的指针// ListConstIterator(Node* node)// :_node(node)// {// }// //我们最想实现的是对于指针的即运算符的重载// //1.it// Self operator()// {// //是怎么到下一个节点的即交换值// _node _node-_next;// return *this;// }// //2.it// Self operator(int)// {// //1.调用拷贝构造这里是一个浅拷贝把一个迭代器给另外一个迭代器it1,it2都指向一个节点// Self tmp(*this);// _node _node-_next;// //2.迭代器是否需要写析构不需要因为资源是属于链表的// return tmp;// }// //1. --it// Self operator--()// {// _node _node-_prev;// return *this;// }// //2. it--// Self operator--(int)// {// Self tmp(*this);// _node _node-_prev;// return tmp;// }// //如何控制*it不能被修改即在这里加const// const T operator*()// {// return _node-_data;// }// //如何控制it-不能被修改即在这里加const // const T* operator-()// {// return _node-_data;//返回的是_data的地址// }// //两个迭代器是否相等// bool operator!(const Self it)// {// //即比较节点的指针节点的指针相同他们就相同// return _node ! it._node;// }// bool operator(const Self it)// {// return _node it._node;// }// //比较大小是否需要重载不需要一个类是否要重载一个运算符需要看他是否有意义// //节点后面的地址不能保证比前面的地址大所以没什么意义。不需要重载// //迭代器的重点指针用类似指针的方式来访问容器// //begin()和end()谁能提供链表//};templateclass Tclass list {typedef ListNodeT Node;public://在这里定义好类型//typedef ListIteratorT iterator;//typedef ListConstIteratorT const_iterator;typedef ListIteratorT, T, T* iterator;typedef ListIteratorT,const T,const T* const_iterator;void empty_init(){//创建空链表_head new Node;_head-_next _head;_head-_prev _head;_size 0;}//构造函数 list(){empty_init();}//清除掉所有数据有没有清除掉头结点并没有在析构函数中清除void clear(){iterator it begin();while (it ! end()){it erase(it);}}//析构函数~list(){clear();delete _head;_head nullptr;}//lt2(lt1)//拷贝构造,默认拷贝构造是浅拷贝所以需要我们自己实现一个list(const listT lt){//首先在这里我们先创建空链表//也就是lt2.empty_init()直接给lt2创建一个空链表empty_init();//直接遍历一遍lt1尾插for (auto e : lt)//这里一定要加引用因为如果T是string就浅拷贝了{push_back(e);}}void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//赋值,按值传递//lt1 lt3listT operator(listT lt) //lt lt3;{swap(lt);return *this;}//迭代器//1.原生指针能不能充当迭代器不可以这是建立在物理空间连续的情况下画图解释//2.Node*能不能加到下一个节点节点的解引用能取到当前节点的数据吗不能//并且新new出来的地址和原来的地址也不会相同头插和中间插入怎么保证在物理空间连续从功能上未解决//因此我们在此重新封装一个类(内嵌类、typedef(在类域))想一想日期类可以日期相加做各种操作的是合理的,使用封装的类//来重载运算符重载运算符后我就可以自定义这些运算符的行为//普通版本iterator begin() {// 1.有名对象//iterator it(_head-_next);//return it;// 2.隐式类型转换(单参数的构造函数支持隐式类型的转换)//return _head-_next;// 3.匿名对象return iterator(_head-_next);}//end()是最后一个数据的下一个位置iterator end() {return iterator(_head);}//const版本const_iterator begin() const{// 1.有名对象//iterator it(_head-_next);//return it;// 2.隐式类型转换(单参数的构造函数支持隐式类型的转换)//return _head-_next;// 3.匿名对象return const_iterator(_head-_next);}//end()是最后一个数据的下一个位置const_iterator end() const{return const_iterator(_head);}//注意这里我们都应该通过begin()、end()控制迭代器而不是控制节点了//尾插void push_back(const T x){//1.还未写insert()时写的push_back()//Node* newnode new Node(x);//Node* tail _head-_prev; //指定被插的节点//tail-_next newnode;//newnode-_prev tail;//newnode-_next _head;//_head-_prev newnode;//2.写了insert()后写的push_back()insert(end(), x);}//头插void push_front(const T x){insert(begin(), x);}//尾删 要--,不然删的是head(哨兵位)void pop_back(){erase(--end()); }//头删void pop_front(){erase(begin());}//在pos位置插入datavoid insert(iterator pos, const T data){Node* current pos._node; Node* newnode new Node(data);Node* prev current-_prev;//prev newnode current prev-_next newnode;newnode-_prev prev;newnode-_next current;current-_prev newnode;_size;}//删除pos位置iterator erase(iterator pos) //请注意这里的pos位置迭代器会失效为什么可以看我的上篇vector中目录的更新erase(){//拿到当前位置Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;//prev cur nextprev-_next next;next-_prev prev;delete cur;--_size;return iterator(next);//解决办法就是返回下一个位置的迭代器}size_t size() const{库里面:1. 遍历一遍计数//for ()//{//}//2. 我们通过构造函数来初始化,给insert、erase加上_size便于计数return _size;}bool empty(){return _size 0;}//resize()不常用我们这里不做模拟没有扩容的概念比我当前的_size大就尾插入比当前的_size小就尾删private:Node* _head;size_t _size;};void test_list1(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);//迭代器测试代码//这里需要遍历数据所以要用到迭代器于是现在我们写迭代器代码listint::iterator it lt.begin();cout *it endl;while (it ! lt.end()){cout *it ;it;}cout endl;lt.push_front(10);lt.push_front(20);lt.push_front(30);for (auto e : lt){cout e ;}cout endl;lt.pop_back();lt.pop_front();for (auto e : lt){cout e ;}cout endl;}//迭代器进一步优化struct A{int _a1;int _a2;A(int a1 0, int a2 0):_a1(a1),_a2(a2){}};void test_list2(){listA lt;//如果这里有自定义类型AA aa1(1, 5);A aa2 { 1,1 };lt.push_back(aa1);lt.push_back(A(2, 3));lt.push_back({ 4,5 });lt.push_back(aa2);listA::iterator it lt.begin();while (it ! lt.end()){cout it-_a1 : it-_a2 endl;it;}} void PrintList(const listint clt){listint::const_iterator it clt.begin();while (it ! clt.end()){//*it 10;cout *it ;it;}}void test_list3(){listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);PrintList(lt1);cout endl;//拷贝构造listint lt2(lt1);PrintList(lt2);cout endl;listint lt3 lt1;PrintList(lt3);}} 结语 随着这篇关于题目解析的博客接近尾声我衷心希望我所分享的内容能为你带来一些启发和帮助。学习和理解的过程往往充满挑战但正是这些挑战让我们不断成长和进步。我在准备这篇文章时也深刻体会到了学习与分享的乐趣。 在此我要特别感谢每一位阅读到这里的你。是你的关注和支持给予了我持续写作和分享的动力。我深知无论我在某个领域有多少见解都离不开大家的鼓励与指正。因此如果你在阅读过程中有任何疑问、建议或是发现了文章中的不足之处都欢迎你慷慨赐教。 你的每一条反馈都是我前进路上的宝贵财富。同时我也非常期待能够得到你的点赞、收藏关注这将是对我莫大的支持和鼓励。当然我更期待的是能够持续为你带来有价值的内容让我们在知识的道路上共同前行。
