中国建设投资集团 网站首页,昆明企业免费建站,上海市 建设执业资格注册中心网站,在哪儿可以找到网站开发的需求#x1f440;樊梓慕#xff1a;个人主页 #x1f3a5;个人专栏#xff1a;《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》《算法》
#x1f31d;每一个不曾起舞的日子#xff0c;都是对生命的辜负 目录
前言
1.List迭代器
2.适…
樊梓慕个人主页 个人专栏《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》《算法》
每一个不曾起舞的日子都是对生命的辜负 目录
前言
1.List迭代器
2.适配器
3.迭代器失效
4.模拟实现源码 前言
本篇文章旨在记录博主在模拟实现vector容器中遇到的一些问题都是一些需要注意的细节问题希望与大家共勉。 欢迎大家收藏以便未来做题时可以快速找到思路巧妙的方法可以事半功倍。 GITEE相关代码fanfei_c的仓库 1.List迭代器
在之前模拟实现『 String和Vector』时我们都采用的『 原生指针』实现迭代器那么到List这里还可以么
这我们就要搞清楚『 迭代器存在的意义』。
我们希望可以通过迭代器来实现对某一容器的遍历访问例如对迭代器或-- 迭代器让使用者可以不必关心容器的底层实现可以用简单统一的方式对容器内的数据进行访问。 之前的String和Vector我们可以简单的利用原生指针实现迭代器是因为String和Vector底层的物理空间是连续的所以和--当然可以访问到对应的对象。
可到了List中List的底层是带头双向循环链表链表的物理空间并『 不连续』所以我们需要对迭代器进行一定的『 封装』让迭代器『 符合统一的迭代器使用规则』。
如何封装呢
提示比如重载各种运算符运算符的底层可以为链表的pp-next
注意end迭代器是最后一个元素的下一个位置所以end一般指向的是『 头节点』。
头节点不存储数据。 // List的节点类
templateclass T
struct ListNode
{ListNodeT* _next;ListNodeT* _prev;T _data;ListNode(const T val T()):_next(nullptr), _prev(nullptr), _data(val){}
};
//List的迭代器类
templateclass T, class Ref, class Ptr
class __list_iterator
{
public:typedef ListNodeT Node;typedef __list_iteratorT, Ref, Ptr Self;Node* _node;__list_iterator(Node* x):_node(x){}Ref operator*(){return _node-_data;}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){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
}; 2.适配器
我们知道迭代器一般需要两个形式一种为非const迭代器一种为const迭代器用来满足不同的使用场景但你有没有发现上面的代码似乎只有一种形式
其实并不是如果我们按照以前的写法应为
//非const迭代器类
templateclass T
class __list_iterator
{
public:typedef ListNodeT Node;typedef __list_iteratorT Self;Node* _node;__list_iterator(Node* x):_node(x){}T operator*(){return _node-_data;}T* 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){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
};
//const迭代器类
templateclass T
class __list_const_iterator
{
public:typedef ListNodeT Node;typedef __list_const_iteratorT self;Node* _node;__list_const_iterator(Node* x):_node(x){}const T operator*(){return _node-_data;}const T* 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){return _node ! s._node;}bool operator(const self s){return _node s._node;}
}; 但这样看起来代码非常冗余那么有没有什么方式来简化代码呢
其实模板的用法不仅有vectorint这类还可以这么使用 所以编译器可以通过模板自动推演出当前使用场景为const迭代器还是非const迭代器。
这种方式可以唤作为『 适配器』当然这部分后面还会有涉及。 3.迭代器失效
在之前学习vector时我们发现了迭代器失效的问题对于vector来讲迭代器失效往往发生在扩容之后那么对于List来讲是不需要扩容的那么List会不会发生迭代器失效的问题呢
List可能会在『 erase』操作之后迭代器失效。
我们来分析一下
vector迭代器失效的原因是因为扩容导致迭代器使用前后底层指针位置发生了改变换句话说就是开辟了新的空间指针指向了新的地址而迭代器没有更新从而导致迭代器失效。
而List并不会扩容也不会开辟新的连续的空间所以对于插入来说无从谈起迭代器失效而erase是会导致迭代器失效的因为删除了该位置的对象迭代器底层指针成为野指针但并不会影响其他迭代器只需要重新赋值即可比如设计为删除当前迭代器位置对象并指向下一位置
// 删除pos位置的节点返回该节点的下一个位置
iterator erase(iterator pos)
{assert(pos ! end());//list是带头双向循环链表当pos是end()位置时证明没有可删除的节点了Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return next;
} 4.-操作符的重写
-操作符的重写是一个特例大家只需要记住即可因为这是STL设计者故意设计为这样的。
Ptr operator-()//为什么返回的是地址
{return _node-_data;
}
那放在实际的场景中我们使用一下看看
struct AA
{int _a1;int _a2;AA(int a1 1, int a2 1):_a1(a1), _a2(a2){}
};void test_list5()
{listAA lt;AA aa1;lt.push_back(aa1);lt.push_back(AA());AA aa2(2, 2);lt.push_back(aa2);lt.push_back(AA(2, 2));listAA::iterator it lt.begin();while (it ! lt.end()){cout it-_a1 : it-_a2 endl;//这里打印的是_a2的内容并不是_a2的地址it;}cout endl;
}
正常来讲这里本来是应该有两个-的第一个箭头是it-去调用重载的operator-返回AA* 的指针第二个箭头是AA* 的指针去访问对象当中的成员变量_a2。
cout it.operator-()-_a1 : it.operator-()-_a2 endl;//实际但是为了程序可读性所以编译器做了特殊识别处理省略了一个箭头。 5.模拟实现源码
#pragma once#includeiostream
#includeassert.hnamespace F
{// List的节点类templateclass Tstruct ListNode{ListNodeT* _next;ListNodeT* _prev;T _data;ListNode(const T val T()):_next(nullptr),_prev(nullptr),_data(val){}};//List的迭代器类templateclass T, class Ref, class Ptrclass __list_iterator{public:typedef ListNodeT Node;typedef __list_iteratorT, Ref, Ptr Self;Node* _node;__list_iterator(Node* x):_node(x){}Ref operator*(){return _node-_data;}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){return _node ! s._node;}bool operator(const Self s){return _node s._node;}};//list类templateclass Tclass list{typedef ListNodeT Node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;public:///// List的构造void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}list(){empty_init();}list(int n, const T value T()){empty_init();while (n--){push_back(value);}}list(const listT l){empty_init();for (const auto e : l){push_back(e);}}listT operator(listT l){swap(l);return *this;}~list(){clear();delete _head;_head nullptr;}///// List Iteratoriterator begin(){return _head-_next;}iterator end(){return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}///// List Capacitysize_t size()const{size_t count 0;const_iterator it begin();while (it ! end()){count;it;}return count;}bool empty()const{return _head-_next _head;}// List AccessT front(){return *begin();}const T front()const{return *begin();}T back(){return *(--end());}const T back()const{return *(--end());}// List Modifyvoid push_back(const T val) { insert(end(), val); } void pop_back() { erase(--end()); }void push_front(const T val) { insert(begin(), val); }void pop_front() { erase(begin()); }// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);prev-_next newnode;newnode-_next cur;newnode-_prev prev;cur-_prev newnode;//return iterator(newnode);return newnode;//单参数的构造函数支持隐式类型转换}// 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){assert(pos ! end());//list是带头双向循环链表当pos是end()位置时证明没有可删除的节点了Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return next;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}void swap(listT l){std::swap(_head, l._head);}private:Node* _head;};
}; 模拟实现的主要目的在于学习优秀的代码比如这里适配器的使用、优秀的框架设计。
注意为了迭代器统一使用
typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_iterator;
这样我们就可以不需要知道迭代器的底层是如何实现的只需要调用迭代器的接口就可以了从而实现了通用的目的。 如果你对该系列文章有兴趣的话欢迎持续关注博主动态博主会持续输出优质内容
博主很需要大家的支持你的支持是我创作的不竭动力
~ 点赞收藏关注 ~
