培训机构网站,青岛网站建设服务器,软件开发文档包括什么内容,秸秆可以发酵吗网站建设吗C#xff1a;迭代器的封装思想 list迭代器实现反向迭代器实现 本博客将通过实现list的迭代器#xff0c;以及它的反向迭代器#xff0c;来帮助大家理解迭代器的底层逻辑#xff0c;以及封装思想。 list迭代器实现
迭代器是一个遍历容器的工具#xff0c;其可以通过自增自… C迭代器的封装思想 list迭代器实现反向迭代器实现 本博客将通过实现list的迭代器以及它的反向迭代器来帮助大家理解迭代器的底层逻辑以及封装思想。 list迭代器实现
迭代器是一个遍历容器的工具其可以通过自增自减来改变位置通过解引用来访问节点也就是模仿指针的行为。这为算法库提供了统一的方式来访问容器也降低了用户的学习成本可以用相同的方式来访问不同的容器。
那么迭代器是如何做到模仿指针行为的 这还要归功于运算符重载这一设计在类中我们可以通过运算符重载来决定一个类在面对不同运算符时的行为那么我们是否可以将迭代器封装为一个类然后利用运算符重载使得迭代器可以使用–*这样的操作符从而模仿指针的行为呢 STL的底层迭代器就是利用这样的方式实现的。
我们先来看到list的基本结构
list节点
template class T
struct list_node
{list_nodeT* _next;list_nodeT* _prev;T _data;
};这是一个list的节点list_node其有三个成员_prev指向上一个节点_next指向下一个节点_data存储当前节点的数据。
template class Tclass list{typedef list_nodeT node;private:node* _head;};这是一个list类其将节点list_nodeT重命名为了node方便后续使用。 唯一一个成员变量是哨兵位头节点指针_head。
接下来我们就讨论要如何设计这个list的迭代器 毫无疑问我们需要把这个迭代器封装为一个类而这个类的内部我们需要什么才能让迭代器访问不同的节点呢 想要访问不同的节点毫无疑问就需要不同节点的指针所以我们的迭代器需要把一个指向节点的指针给封装起来然后利用运算符重载改变这个指针的行为从而实现迭代器。
现在我们将这个迭代器命名为__list_iterator先看看基础结构
template class T
struct __list_iterator
{typedef list_nodeT node;node* _node;
};为了方便我们使用节点的指针我们重命名list_nodeT为node而迭代器内部指向节点的指针名为_node。 构造函数 代码如下
__list_iterator(node* n): _node(n)
{}这就是一个很简单的初始化过程这里不过多赘述了那么我们要如何使用这个迭代器呢
看看list类中获取迭代器的函数
typedef __list_iteratorT iterator;iterator begin()
{return iterator(_head-_next);
}iterator end()
{return iterator(_head);
}先将我们的迭代器重命名为iterator方便后续使用。 可以看到我们的begin()函数就是返回了哨兵位节点的后一个节点也就是第一个节点的指针但是普通的指针的–操作不符合我们的要求于是我们利用iterator(_head-_next)这个方式利用这个指针来构造一个匿名对象也就是迭代器的匿名对象此时我们就完成了指针的封装得到的指针就是被我们修改了行为后的迭代器了。
end()函数同理iterator(_head)构造一个迭代器将指针进行封装修改其行为。
接下来我们回到迭代器的实现 operator 我们希望我们的迭代器可以在的时候到达下一个节点的位置也就是_node _node-_next这样的行为。 所以我们的需求就明确了当迭代器的时候实际发生的是_node _node-_next而不是简单的指针偏移。
先看到我们的实现
__list_iteratorT operator()
{_node _node-_next;return *this;
}是要进行返回的将自增后的节点作为返回值所以最后我们还要return *this;将修改后的节点作为返回值。
后置同理
__list_iteratorT operator(int)
{__list_iteratorT tmp(*this);_node _node-_next;return tmp;
}由于后置需要将自增前的值作为返回值所以我们要先拷贝一份原先的值tmp自增完成后将原先的值tmp返回。
为了简化代码我们可以将__list_iteratorT重命名为self代表迭代器自己的类型。
最后代码如下
typedef __list_iteratorT self;self operator()
{_node _node-_next;return *this;
}self operator(int)
{self tmp(*this);_node _node-_next;return tmp;
}这样一来我们的迭代器表面上和指针自增一样但是底层却是_node _node-_next到达下一个节点的位置了。 operator– 迭代器–同理我们需要实现迭代器到达上一个节点其实就是_node _node-_prev。 实现如下
self operator--()
{_node _node-_prev;return *this;
}self operator--(int)
{self tmp(*this);_node _node-_prev;return tmp;
}迭代器判断相等 想要判断两个迭代器是否相等其实就是判断其内部封装的指针_node是否相等。
代码如下
bool operator!(const self s)
{return _node ! s._node;
}bool operator(const self s)
{return _node s._node;
}这个比较简单不做赘述了。 operator*
*是迭代器中十分重要的操作符指针就是利用解引用来访问指向内容的迭代器就模仿指针也通过解引用来访问节点值。 迭代器内部的成员_node是指向节点的指针那么访问这个节点的值就是_node-_data了。
所以解引用代码如下
T operator*()
{return _node-_data;
}但是这个代码有一个问题那就是如果我们的list被const修饰了怎么办 这样的话由于我们返回的是T而这个_data就有可能会被修改这就不符合const的行为了。
是否我们要写一个重载比如这样
T operator*()
{return _node-_data;
}const T operator*()
{return _node-_data;
}这是不行的因为两个函数只有返回值不同并不构成重载。 我们只希望返回值的类型不同这要怎么办
注意我们的迭代器是利用模板生成的而模板最大的用处就是泛型编程可以无视类型的限制我们完全可以给模板多传一个参数让第二个参数作为operator*的返回值。
//-----迭代器-----
template class T, class Ref
struct __list_iterator
{typedef __list_iteratorT, Ref self;Ref operator*(){return _node-_data;}
};这样当我们需要普通迭代器第二个参数Ref就传入T如果需要const迭代器那么第二个参数就传入const T。 不过要注意的是刚刚我们重命名了一个self 即typedef __list_iteratorT self此时由于模板参数改变这个重命名也要一起改变typedef __list_iteratorT, Ref self。
现在我们就可以在list中加入const迭代器了接下来让类中定义的迭代器一起改变
template class T
class list
{typedef __list_iteratorT, T iterator;typedef __list_iteratorT, const T const_iterator;//普通迭代器iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}//const迭代器const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}
};看到两行typedef
typedef __list_iteratorT, T iterator;
typedef __list_iteratorT, const T const_iterator;当我们传入的第二个模板参数为T那么解引用的返回值就是可以修改的此时就是一般的迭代器iterator。 当我们传入的第二个模板参数为const T那么解引用的返回值就是不可以修改的此时就是const迭代器const_iterator。
相比于开始我们现在多了一个迭代器const_iterator;我们的this指针被const修饰时说明此时需要调用const迭代器那么我们就返回const_iterator类型的迭代器。
const_iterator begin() const
{return const_iterator(_head-_next);
}const_iterator end() const
{return const_iterator(_head);
}operator- 接下面我们看到最后一个问题那就是类的嵌套问题假设我们的list内部是一个A类
class A
{
public:int num;
};那么如果我们想要通过迭代器访问A类的num成员要怎么做
假设我们有一个list的迭代器it接下来我用it尝试访问这个A的成员num。
(*it).num先解引用迭代器(*it)此时就得到了list内部的A类然后再利用.来访问内部的num成员。
这样访问是没有问题的但是我们的迭代器是模仿指针的行为我们会对一个指针先解引用再用点操作符访问成员吗 我们完全可以指针 - 成员这样访问。
也就是说我们还要对迭代器重载一个-操作符实现这种直接访问的方式
代码
T* operator-()
{return _node-_data;
}我们的返回值是_data的地址而_data就是A类所以我们可以就得到了一个A类的指针此时T*就是其实就是A*。 那么我们看看现在要如何访问
list.operator-()-num你也许不是很能理解以上代码我们拆解一下 list.operator-()返回了一个A*类型的指针而A*类型的指针可以直接访问num
A* ptr;
ptr-num所以以上代码list.operator-()-num就可以访问到num这个成员了。 而.operator-()其实就是-操作符所以可以变形为以下代码 list--num 连用--不太美观也容易让人费解但是编译器会将两个-优化为一个-所以此时我们已经可以直接像指针一样访问成员了
list-num我们再回顾一遍推导过程 list.operator-()-num list--num list-num 这个访问和刚刚的operator*会遇到同样的问题那就是const问题所以我们要传入第三个模板参数Ptr来控制operator-的返回值
template class T, class Ref, class Ptr
struct __list_iterator
{Ptr operator-(){return _node-_data;}
};在list中
typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_iterator;至此我们就实现了一个list的迭代器了。 代码展示
template class T, class Ref, class Ptr
struct __list_iterator
{typedef list_nodeT node;typedef __list_iteratorT, Ref, Ptr self;node* _node;__list_iterator(node* n): _node(n){}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;}
};反向迭代器实现
那么我们要如何实现反向迭代器呢
一开始我们实现正向迭代器的时候遇到的问题就是原生指针的行为不符合我们的要求于是我们将原生指针进行了封装利用运算符重载来修改其行为。
那么我们的反向迭代器还需要封装一个原生指针吗 其实我们可以换一个思路现在我们有正向迭代器而正向迭代器并不符合反向迭代器的预期行为我们不妨对正向迭代器进行一次封装让其变成––变成这不就是一个反向迭代器了吗
结构如下
template class Iterator, class Ref, class Ptr
struct ReverseIterator
{Iterator _cur;
};我们定义了一个反向迭代器的类ReverseIterator在内部封装了一个迭代器Iterator _cur接下来我们就重载这个反向迭代器让其行为符合预期
先看看我们在list中是如何定义反向迭代器的 template class Tclass list{typedef ReverseIteratoriterator, T, T* reverse_iterator;//反向迭代器reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}};首先我们重命名了反向迭代器typedef ReverseIteratoriterator, T, T* reverse_iterator;其第一个模板参数为iterator也就是我们封装的正向迭代器。 随后在rbegin()中我们直接将end()返回的末尾迭代器作为我们反向迭代器的起始迭代器rbegin() 将begin()返回的正向迭代器的起始迭代器作为我们反向迭代器的末尾迭代器。
注意end()返回的是最后一个元素的后面一个位置所以我们在后续,–操作时要进行其他的操作来矫正这个位置的偏差。 operator 现在由于我们是反向迭代器我们的反向迭代器其实就是正向迭代器的–。
代码如下
self operator()
{--_cur;return *this;
}operator*
由于我们的迭代器位置是往后偏一位的所以我们要返回前一个位置的迭代器而不是当前位置的迭代器
Ref operator*()
{Iterator tmp _cur;--tmp;return *tmp;
}我们用tmp拷贝了一份当前的迭代器随后--tmp将其往前走一个位置再返回tmp位置的迭代器这样就可以矫正我们起初的位置偏差了。 而其它的操作符重载几乎没有太大的差别基本就围绕以上两种类型的改动此处我们直接展示代码了 template class Iterator, class Ref, class Ptrstruct ReverseIterator{typedef ReverseIteratorIterator, Ref, Ptr self;Iterator _cur;ReverseIterator(Iterator it):_cur(it){}Ref operator*(){Iterator tmp _cur;--tmp;return *tmp;}Ptr operator-(){Iterator tmp _cur;--tmp;return tmp-_data;}self operator(){--_cur;return *this;}self operator(int){self tmp(*this);--_cur;return tmp;}self operator--(){_cur;return *this;}self operator--(int){self tmp(*this);_cur;return tmp;}bool operator!(const self s){return _cur ! s._cur;}bool operator(const self s){return _cur s._cur;}};这个反向迭代器的实现可以作用于任何正向迭代器也就是说不论是listvector等等各种容器都可以使用这一套反向迭代器来封装原本的迭代器从而获得反向迭代器
