写这篇文章的目的,主要是想总结一下我看完SGI-STL
的迭代器部分代码之后的感悟,说一说自己的理解,这里还是要感谢侯捷老师的«STL源码剖析»一书对我带来的启蒙和引发.另外,需要注明的是本篇涉及到的代码都是笔者自己实现的一套代码,和原生SGI代码相比在类命名等问题上有一些不同.
迭代器需要哪些特征?
我们要设计一个迭代器,那么我们先从迭代器的使用需求上来看迭代器需要哪些特征? 什么是特征?我们看一个例子就知道了.
STL的distance算法
我们知道,distance算法是求两个迭代器的距离,那么我们可以想一下,由于这个是通用函数模板,输入的迭代器可以是vector容器的迭代器,也可以是list容器的迭代器,而我们根据vector和list的数据组织应该可以意识到这两个容器的迭代器的访问能力是不同的,一个是可以随机访问,即随便向前向后移动任意步数,但是另外一个只能每次向前移动一步(pos = pos->next
). 基于这个不同,我们的distance算法实现就应该有所不同.那么怎么告知distance函数这个问题呢? 就需要迭代器具有某个特征来说明这点.
通过上面的例子,我们可以看到迭代器确实需要一些特征来作为区别,SGI-STL中的迭代器有五大特征,我们可以通过SGI的标准Iterator基类可以一看究竟,这里需要说一下,SGI中所有的迭代器都继承与这个基类.
这里面唯一眼生的就是Category,这是标记迭代器的访问能力的一个特征,具体有五种类型分别定义如下:
迭代器萃取器
有了上面的介绍,我们知道迭代器有着五大特征,给你一个迭代器,如何判断其某个特征呢? 我们还是以distance为例.
那么我们怎么根据InputIterator来判断其Category呢? 这里就不得不提到Traits技术.
所以你只需要简单的traits_iterator<InputIterator>::iterator_category
就得到了其特征了,然后根据这个特征生成一个对象,根据这个iterator_category就找到具体的重载函数,就达到了不同iterator_category不同处理方式的目的了.
see? 这就把迭代器的特征,traits_iterator萃取技术和重载函数联系到一起了.
类型萃取器
我们现在已经有了traits_iterator,那么似乎一切都已足够了,但是我们考虑uninitialized_copy函数这个问题.
#### STL的uninitialized_copy函数
uninitialized_copy函数是将[result, end - begin)区间的值一一赋值给[begin, end)区间.这个函数需要根据迭代器指向的类型来做判断,而不是迭代器类型做判断. 因为我们想一下,同样是指向vector的迭代器,但是一个是指向vector<A>
,而另外一个是指向vector<B>
, A不需要深拷贝而B需要深拷贝,所以这种情形下处理vector<B>
就无法像处理vector<A>
一样了.
所以,我们需要类型萃取器.类型萃取器和迭代器萃取器如出一辙,具体实现如下:
准备好了类型萃取后,我们就可以这样实现uninitialized_copy了:
总结
SGI的迭代器设计思想就是所有的迭代器都有五大特征,然后通过traits_iterator来萃取出任一特征,再根据不同的特征调用不同的重载函数,以达到不同情况做不同处理的目的.我想这就是迭代器的设计精髓.
- EOF -
声明:本文采用BY-NC-SA协议进行授权.转载请注明: 浅谈对SGI-STL迭代器设计思想的理解
comments powered by