STL源码剖析（六）迭代器
STL源码剖析（六）迭代器
文章目录
- STL源码剖析（六）迭代器
- 一、什么是迭代器？
- 二、实现一个简单的容器
- 三、实现容器的迭代器
- 四、STL迭代器的规范
- 4.1 STL迭代器的规范
- 4.2 STL迭代器的分类
本文将带你学习什么是迭代器，以及STL的迭代器规范
一、什么是迭代器？
迭代器是一种有指针行为（->，*，++）的东西，它可以是原生指针，也可以是重载了``operator->、operator*、operator++等运算符的对象`
对于原生指针就很清楚了，因为本身就具备指针的功能
对于迭代器是一个对象，你可能就有点不清楚了，别急，下面我使用一个非常简单的例子，来告诉你
二、实现一个简单的容器
首先我们实现了非常非常简单的容器（容器是一个存储数据的对象）
template <class T>class MVector{public:MVector(){mStart = (T*)malloc(1024*1024);mEnd = mStart;}~MVector(){free(mStart);}void push(const T& value){*mEnd = value;++mEnd;}private:T* mStart;T* mEnd;};
这实现了一个非常简单的容器，容器内部可以看是一个数组，mStart指向数组开头，mEnd指向数组最后一个元素的下一个位置，此容器只提供一个方法，那就是通过push添加元素
可以通过以下代码使用这个容器
#include <iostream>#include <stdlib.h>int main(int argc, char* argv[]){MVector<int> mVt;for(int i = 0; i < 10; ++i)mVt.push(i);return 0;}
上述程序是简单的往容器中添加数据
想一下，我们现在如果要遍历容器内的所有元素，我们需要怎么做？
对于这个容器，我们当然可以通过某种方法，获取mStart和mEnd指针，然后通过它们来遍历所有的数组元素。
但在某些更加复杂的容器中（底层是链表或者红黑树）,在这些容器中，我们无法简单的通过指针来遍历所有元素，但是我们却想通过和指针一样的方式来访问容器中的元素，这时候就需要设计对象迭代器，然后重载运算符，将复杂的动作进行封装，提供和指针一样的功能
所以在STL中，大多数容器都提供了其对应的迭代器，下面我们就来为这个容器设计一个迭代器
三、实现容器的迭代器
首先说明一下，对于上述这个容器，其实它的迭代器只要是T*原生指针就行，但是为了演示复杂的迭代器是怎么设计的，这里将实现一个对象迭代器，如下
template <class T>class Iterator{public:Iterator(T* data) : mData(data){}Iterator& operator++(){++mData;return *this;}T operator*(){return *mData;}bool operator!=(const Iterator& it){return mData != it.mData;}private:T* mData;};
此迭代器内含一个对象指针，然后重载了operator++、operator*、operator!=运算符，这样子它就具有了指针的部分性质
有了迭代器之后，我们重新设计我们的容器，如下
template <class T>class MVector{public:/* add */typedef Iterator<T> iterator;MVector(){mStart = (T*)malloc(1024*1024);mEnd = mStart;}~MVector(){free(mStart);}void push(const T& value){*mEnd = value;++mEnd;}/* add */iterator begin(){return iterator(mStart);}/* add */iterator end(){return iterator(mEnd);}sprivate:T* mStart;T* mEnd;};
我们使用typedef Iterator<T> iterator对外提供了该容器的迭代器类型，然后提供了begin()和end()来获取首尾迭代器
有了这些，我们就可以遍历容器的元素了，如下
int main(int argc, char* argv[]){MVector<int> mVt;/* 添加元素 */for(int i = 0; i < 10; ++i)mVt.push(i);/* 遍历容器 */for(MVector<int>::iterator it = mVt.begin(); it != mVt.end(); ++it)std::cout<<*it<<" "; //访问元素std::cout<<std::endl;return 0;}
完整代码
#include <iostream>#include <stdlib.h>template <class T>class Iterator{public:Iterator(T* data) : mData(data){}Iterator& operator++(){++mData;return *this;}T operator*(){return *mData;}bool operator!=(const Iterator& it){return mData != it.mData;}private:T* mData;};template <class T>class MVector{public:typedef Iterator<T> iterator;MVector(){mStart = (T*)malloc(1024*1024);mEnd = mStart;}~MVector(){free(mStart);}iterator begin(){return iterator(mStart);}iterator end(){return iterator(mEnd);}void push(const T& value){*mEnd = value;++mEnd;}private:T* mStart;T* mEnd;};int main(int argc, char* argv[]){MVector<int> mVt;for(int i = 0; i < 10; ++i)mVt.push(i);/* 遍历容器 */for(MVector<int>::iterator it = mVt.begin(); it != mVt.end(); ++it)std::cout<<*it<<" ";std::cout<<std::endl;return 0;}
四、STL迭代器的规范
经过上述的讲解，想必你已经知道什么是迭代器了，但是我们上述实现的迭代器不符合STL的规范，所以对于STL的许多算法，我们并无法使用，下面来看一看STL中迭代器的设计规范
在stl_iterator.h文件中，定义了许多与迭代器相关的东西
4.1 STL迭代器的规范
首先我们来看一下，STL对迭代器的要求，STL要求迭代器至少需要能提供上述的5种类型，如下
template <class Category, class T, class Distance = ptrdiff_t,class Pointer = T*, class Reference = T&>struct iterator {typedef Category iterator_category; //迭代器类型typedef T value_type; //迭代器所指的类型typedef Distance difference_type; //两个迭代器之间的距离描述typedef Pointer pointer; //迭代器所指的类型的指针类型typedef Reference reference; //迭代器所指类型的引用类型};
为什么需要提供这些信息？
因为在STL的算法中，通常需要这些信息来定义相应的类型，或者根据这些信息来采取不同的措施，如果你设计的迭代器不满足这些要求，那么你在使用STL的算法的时候，非常有可能编译失败
关于其它字段，这里不做讨论了，下面好好讨论一个迭代器分类iterator_category
4.2 STL迭代器的分类
STL对迭代器分为5类，其定义如下
/* 输入式迭代器 */struct input_iterator_tag {};/* 输出式迭代器 */struct output_iterator_tag {};/* 单向迭代器 */struct forward_iterator_tag : public input_iterator_tag {};/* 双向迭代器 */struct bidirectional_iterator_tag : public forward_iterator_tag {};/* 随机访问迭代器 */struct random_access_iterator_tag : public bidirectional_iterator_tag {};
它们的关系如下
单向迭代器：表示往一个方向一格一格移动（单向链表）
双向迭代器：表示往前后方向一格一格移动（双向链表）
随机访问迭代器：可以随机访问（数组）
为什么需要迭代器分类？
主要目的是为了让算法可以采用不同的策略，下面举一个例子
在stl的算法中，有一个叫advance的算法，其作用是移动迭代器的指向，定义如下
inline void advance(InputIterator& i, Distance n)
设想一下，如果现在迭代器对应的容器底部是一个数组，那么移动5格，只需要+5就行，如果是链表的话，就需要一格一格地移动，很明显，这两者地效率差别是相当大
STL的实现如下
template <class InputIterator, class Distance>inline void advance(InputIterator& i, Distance n) {__advance(i, n, iterator_category(i));}
根据迭代器的iterator_category调用相应的__advance函数
对于随机访问的迭代器（random_access_iterator_tag）
template <class RandomAccessIterator, class Distance>inline void __advance(RandomAccessIterator& i, Distance n,random_access_iterator_tag) {i += n;}
对于双向迭代器
template <class BidirectionalIterator, class Distance>inline void __advance(BidirectionalIterator& i, Distance n,bidirectional_iterator_tag) {if (n >= 0)while (n--) ++i;elsewhile (n++) --i;}
对于普通的迭代器
template <class InputIterator, class Distance>inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {while (n--) ++i;}
本文到此也就结束了
╰+攻爆jí腚メ
Love The Way You Lie
深藏阁楼爱情的钟
小灰灰
分手后的思念是犯贱
还没有评论，来说两句吧...