成都网站建设 四川冠辰科技公司,企业宣传视频模板免费下载,wordpress photoshop,科技公司 网站 石家庄List中的迭代器实现【C】 一. list的结构二. 迭代器的区别三. 迭代器的实现i. 类的设计ii. 重载iii. !重载iiii. begin()iiiii. end()iiiii. operator* 四.测试五. const迭代器的实现i. 实现ii 优化实现 六. 整体代码 一. list的结构
其实按照习惯来说#xff0c;应该要专门出… List中的迭代器实现【C】 一. list的结构二. 迭代器的区别三. 迭代器的实现i. 类的设计ii. 重载iii. !重载iiii. begin()iiiii. end()iiiii. operator* 四.测试五. const迭代器的实现i. 实现ii 优化实现 六. 整体代码 一. list的结构
其实按照习惯来说应该要专门出一篇博客来写
list的模拟实现但是其实list与vector以及string的主要区别在于迭代器的设计。
所以就偷个懒直接写迭代器的部分了。
这里先声明以下我这里就是进行一下模拟实现STL中的list的iterator虽然并不是这样实现的但是实现逻辑和结构都大差不差
这里就先贴上list类的结构
namespace list
{templateclass Tstruct list_node{list_nodeT* _prev;list_nodeT* _next;T _val;//节点的构造函数list_node(const T val T()):_prev(nullptr), _next(nullptr), _val(val){}};templateclass Tclass list{public:list(){//链表的默认构造list_nodeT* head new list_nodeT;//初始化哨兵位_head head;_head-_next _head;_head-_prev _head;_size 0;}~list(){}private:list_nodeT* _head;};
}这个其实和我们之前写的双向带头循环链表一样。
二. 迭代器的区别
迭代器的区别落到实质问题上 还是容器与容器的区别也就是vector与list的区别
vector中的iterator是这样去实现的。
首先
typedef T* iterator;这里先重命名
iterator begin(){return _start;}iterator end(){return _finish;}随后直接设计end与begin的函数。
之后就能发现范围for与迭代器能直接进行使用了。
因为我们实现vector指针的方法是直接将内置类型指针进行改名。
而内置类型指针支持所以可以直接运行程序了。 但我们想想list肯定就不支持这样的操作了
vector能这这样是因为数据存储在内存空间中连续时正好可以进行使用。
但是list的问题是内存空间是不连续的 这样的话再用指针内部支持的算法就不太合适了。
所以我们今天就是为了来模拟实现list的迭代器的实现。
首先的目标就是实现下面这个代码的跑动。 list::listint::iterator it l1.begin();while (it ! l1.end()){std::cout *it;it;}三. 迭代器的实现
我们首先来看我们最难解决的问题就是it的前置 因为vector和list最重要的问题就是运算的方式不一样。
那我们想要用我们自己的方式进行。 这个时候就应该想到了我们模拟实现类的时候最常用的东西重载运算符
重载运算符在哪里能用自定义类型 所以我们这个时候应该自然而然的想到自己写一个类来充当iterator 从而实现我们想要的方式。
i. 类的设计 templateclass Tstruct __list_iterator{list_nodeT* _node;__list_iterator(list_nodeT* node):_node(node){}};基本上大致结构是这样。
其中list_node就是双链表的节点结构。上面写过
这里添加个typedef templateclass Tclass list{public:typedef __list_iteratorT iterator;这个typedef和vefctor的使用没有什么大区别了。
现在来专注实现上面代码的所有的重载即可
ii. 重载 __list_iteratorT operator(){_node _node-_next;return *this;}
这个就是我们以前写的双链表和单链表的部分了。
iii. !重载 bool operator!(const __list_iteratorT node){return _node ! node._node;}iiii. begin()
注意这里的end和begin都是在list中的
因为迭代器执行时会在list中寻找begin和end iterator begin(){return iterator(_head-_next);}这里我们需要返回的是迭代器的类型
所以需要调用一下迭代器的构造函数
iiiii. end() iterator end(){return _head;}
我们发现begin需要调用构造函数
但是这边end却没有调用
因为单参数的构造函数返回时 如果返回的类型和需要返回的类型不同 就会主动调用需要返回类型的构造函数进行转换
iiiii. operator* T operator*(){return _node-_val;}四.测试
这里就直接写一个push_back的方法 void push_back(const T val){insert(end(), val);}void insert(iterator pos, const T val){list_nodeT* new_node new list_nodeT(val);_size;pos._node-_prev-_next new_node;new_node-_prev pos._node-_prev;new_node-_next pos._node;pos._node-_prev new_node;}接下来进行测试即可 list::listint l1;l1.push_back(1);l1.push_back(1);l1.push_back(1);l1.push_back(1);l1.push_back(1);list::listint::iterator it l1.begin();while (it ! l1.end()){std::cout *it;it;} 这里能发现程序完美执行了。
五. const迭代器的实现
我们在使用STL中自带的迭代器时
应该经常能用到const迭代器。
const_iterator
这里我们首先要清楚const_iterator实现的是什么
我们清楚效果是指向的内容不能修改但是迭代器本身可以修改。
所以实现的类型就是const T* ptr
而不是T* const ptr
那我们要达成这种效果。 可以从函数的返回值上入手
平常使用函数时基本上都是通过重载符* 来进行对应值的修改 const T operator*(){return _node-_val;}那我们这样不就可以了吗。。
i. 实现
typedef __list_iteratorTconst_iterator;这里在list中重命名一下。 templateclass Tstruct __list_const_iterator{list_nodeT* _node;__list_const_iterator(list_nodeT* node):_node(node){}const T operator*(){return _node-_val;}__list_const_iteratorT operator(){_node _node-_next;return *this;}bool operator!(const __list_const_iteratorT node){return _node ! node._node;}};之后再把这个类丢进去。
但是这样会发现实现的太过繁杂了。
这里就来个优化版本。
ii 优化实现
这里先直接上结果
list中的重命名 typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T*const_iterator;具体实现 templateclass T, class refstruct __list_iterator{list_nodeT* _node;__list_iterator(list_nodeT* node):_node(node){}ref operator*(){return _node-_val;}__list_iteratorT, ref, ptr operator(){_node _node-_next;return *this;}bool operator!(const __list_iteratorT, ref, ptr node){return _node ! node._node;}};这里是给模板新添加了一个参数。
从而实现const与普通的两种类型迭代器的实现。
六. 整体代码
//迭代器部分templateclass T,class refstruct __list_iterator{list_nodeT* _node;__list_iterator(list_nodeT* node):_node(node)ref operator*(){return _node-_val;}__list_iteratorT,ref operator(){_node _node-_next;return *this;}__list_iteratorT, ref operator(int){__list_iteratorT, ref(*this);_node _node-_next;return *this;}__list_iteratorT, ref operator--(){_node _node-_prev;return *this;}__list_iteratorT, ref operator--(int){__list_iteratorT, ref(*this);_node _node-_prev;return *this;}bool operator!(const __list_iteratorT, ref node){return _node ! node._node;}};//list中的public命名部分
typedef __list_iteratorT,T,T* iterator;
typedef __list_iteratorT, const T,const T*const_iterator;
