注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

逍遥子 曰:

得失失得 何必患得患失 舍得得舍 不妨不舍不得

 
 
 

日志

 
 

STL源码学习之迭代器[原]  

2012-05-09 21:12:26|  分类: STL |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

STL源码之迭代器

 

【本文由天地任我游总结,转载请包含链接:http://houjixin.blog.163.com/

1、迭代器是什么?为什么要引入迭代器?

 

STL是将容器与算法分离开的,我们用到的类模板和函数模板即是用于实现这两个东西,其中类模板用于实现容器,函数模板用于实现算法,在使用的时候需要一个将两者联系起来的东西,这个东西就是迭代器。

例如段代码1所示:算法find 需要访问容器ivec中的每一个元素之后才能确定该容器中是否有目标元素10,在这里find需要使用了类型为vector<int>::iterator的两个变量iter_begin(指向容器的开始)和iter_end(指向容器的末尾)来访问容器ivec;在实际的使用中容器中放置的元素可以使任何类型(即vector<int>int可以替换成任何一种类型)。

STL源码学习之迭代器 - 天地任我游 - 天地任我游

                                                代码段1

通过上面这一大段的描述,可以看到,所谓的迭代器就是一个指针,或者就是一个实现的指针功能的东西(例如智能指针)。从功能上来讲,也可以认为迭代器实现了一种让用户访问容器元素的方法。

 

2、迭代器核心之Traits

 

通过前面的介绍,可以看到迭代器就是一种实现了类似于指针功能的东西,仅仅如此吗?答案肯定为否定!既然如此,那迭代器还有哪些神奇的功能呢?

 

1)内嵌类型

 

来看一个新的需求:我们需要通过迭代器来得到该迭代器所指元素的类型,并且将该类型用做函数的返回值,如果觉得这句话很绕口来一起分析一个小程序片段(下面这段仿写自侯捷的《STL源码分析》)。这个小程序中定义了一个函数TestFunc,其功能是返回入参所指向的元素的值。

STL源码学习之迭代器 - 天地任我游 - 天地任我游

                                                  代码段2

分析一下上面这段代码:

首先自定义了一个迭代器(虽然它还不是真正意义上的迭代器,我们姑且这么喊它),它类似一个智能指针,构造该迭代器对象时需要传递给它一个指针,使用时就可以像指针一样使用它了,区别之处在于多了一个红框1框起来的代码“typedef T value_type”。

自定义了一个函数TestFunc(红框2)该函数的返回值比较特殊:typename I::value_type,其意思为告诉编译器I::value_type这个东西是个类型,就像intdouble一样,可以定义的、实实在在的类型;在函数编译时将会根据传入的参数类型来获取实际的类型。

在本例main函数中传入了一个TestIter<float>类型的参数,在编译时就会得到I::value_type实际上就是类型TestIter中定义的T,也即TestIter<float>中的float.

是不是在函数TestFunc中只根据传入的迭代器类型TestIter<float>就得到了迭代器所指元素的类型float,并且将该类型用做了函数的返回值?应该算是实现了我们前面提到的需求。

 

2traits机制

 

回头看一下代码段2是否实现了我们在(1)中的需求:“通过迭代器来得到该迭代器所指元素(对象)的类型,并且将该类型用做函数的返回值”?如果你想不到哪里没有实现,请看下面的内容:

我们在设计函数TestFunc时希望其入参不仅可以是类类型(例如基本类型int/float等,当然也包括自定义的class类型),也可以是原生指针(例如int*,float*),换一种说法:我们想给函数TestFunc传入一个int型的指针,然后让该函数返回该指针所指向的int型元素;这时再回头看代码段2会得到什么?还能通过typename I::value_type获得入参int*的所指的int类型的元素吗?肯定得不到了,因为我们只为自己设计的迭代器TestIter中提供了类型定义“typedef T value_type”,而int*又不是我们定义的,它里面肯定没有这个类型定义呀!!!!怎么办?

看看STL是如何来解决该问题?这里会用到模板的偏特化(即为模板提供一个特例化的版本),如果你不懂这个概念请百度或谷歌一下。

既然定义函数TestFunc时,通过(1)中介绍的方法无法解决指针作为参数的问题,STL中便引入了一个中介traits,通过该中介的来屏蔽实际参数的变化,进而保证函数TestFunc定义不变。

其实这种思路并不算陌生,在程序设计中我们经常用到这样的方法,如图1的(a)图,当应用比较多时,服务层为了处理各种不同的应用需要增加很多东西,为了减轻服务层的负担从而让其专职于服务提供,这时引入了中间层,如图1的(b)图,应用层不与服务层直接打交道,这时应用再怎么变化,只要中间层与之对应的变化即可,服务层不需要做任何变化。

STL源码学习之迭代器 - 天地任我游 - 天地任我游STL源码学习之迭代器 - 天地任我游 - 天地任我游

                                    (a)服务层直接提供服务       b)引入中间层

1

再回头看一下STL怎么通过引入中介traits来不同的类型,如代码段3所示,函数的返回值被修改为“typename test_traits<I>::value_type”。

例如:当给函数TestFunc传入一个基本类float时,返回值“test_traits<I>::value_type”就会调用test_traits的类型版本(代码段4中的红1所标识),从而得到最终的返回类型float;当给函数TestFunc传入一个指针类型int*时,返回值“test_traits<I>::value_type”就会调用traits针对指针的偏特化版本(如代码段4中的红2所标识),从而得到类型int,如代码段3所示。

 

STL源码学习之迭代器 - 天地任我游 - 天地任我游

                                                 代码段3

 

(3) traits所定义的类型

 

包括上述基本类型和指针类型,STL中迭代器和traits都定义了如下5个常用类型,这5种类型及其含义如下:

iterator_category:迭代器的类型,共有只读、只写等5种类型,后续会有涉及。

value_type:迭代器所指元素的类型。

distance_type:两个迭代器之间的距离。

pointer:左值,即迭代器所指元素可以被改变,允许赋值操作。

reference:表示能够传回一个pointer,指向迭代器所指之物。

STLtraits又针对指针和const指针定义了偏特化版本,因此,在STL的算法中无论传入的是一个类型、还是一个指针、还是一个const指针,通过traits之后都能过得到真正要使用的类型(例如如果想要通过一个int指针int*获取到所指对象的类型int,这时无论传入的参数是int还是int*还是const int *,这时候都能过通过traits得到真正的int)。

注意:在STL中,任何一种容器(例如vectormap等)都必须包含上述5个类型,这样才能被STLtraits获取到相应的类型。因此,如果你想自定义一种能被STL所兼容的容器,那么该容器就必须包含上述5中类型,以便STL能够通过traits获取到相应的类型

 

3traits在迭代器中的应用

 

1)迭代器的种类

 

在第2节的第(3)部分中提到任何一种类型的容器都必须包含 iterator_category类型,该类型表示迭代器的种类,在STL中迭代器共有以下5中类型(注意与上面提到的5traits所定义的类型做区分呦):

InputIterator:只读迭代器,且只支持operator++

OutputIterator:只写迭代器,且只支持operator++

ForwardIterator:读写都允许的迭代器,且只支持operator++

BidirectionalIterator:可双向移动的迭代器,同时支持operator++operator--

RandomAccessIterator:可随机访问迭代器,同时支持operator++operator—p+np-np[n]p1-p2p1<p2

5种迭代器之间的关系如图2所示,为什么要分这么多类型?当然是为了效率,STL中处处都体现了对效率的要求,后续你会看到在内存空间分配上也是如此,在使用时根据需要选择最符合的迭代器类型。

STL源码学习之迭代器 - 天地任我游 - 天地任我游

 图2 各类型迭代器之间的关系

 

2traits的应用之一iterator_category

 

下面以iterator_category在函数advanced()中的应用为例说明traitsiterator中的应用,该函数的功能是将迭代器前进n步,由于迭代器的类型有5中,需要为每个类型定义一个版本(这里只为InputIteratorOutputIteratorForwardIterator定义了一个InputIterator版本,ForwardIteratorInputIterator的派生类,因此它可以使用其父类InputIterator的版本):

STL源码学习之迭代器 - 天地任我游 - 天地任我游

 STL源码学习之迭代器 - 天地任我游 - 天地任我游

  

代码段4

考虑一下上述代码段4方式的缺陷,上述advanced函数只有到执行的时候才能知道到底用哪个版本的__advanced_xx函数,效率比较低,效率降低是STL所不可忍受的;另外上述三个函数非常类似,似乎可以使用重载,问题是他们又都是有两个类型未定的参数,重载不起来!!!!

下面的方法通过一个类型标签来使用重载,这种方法值得借鉴,具体做法参考代码段5

STL源码学习之迭代器 - 天地任我游 - 天地任我游

 STL源码学习之迭代器 - 天地任我游 - 天地任我游

 代码段5

下面对上述代码段5进行分析:

首先,在代码段5上面的红框中定义了5迭代器标识类型,这些类型中一个元素和操作都没有,它的作用就是在重载函数__advanced()中标识迭代器的类型,从而激发重载。

第二,定义三种重载的函数分别用于“只读、双向、随即”这三种迭代器,重载函数中最后一个参数为迭代器标识类型,不同的迭代器,其标识类型不同,因而也就符合了重载的要求。

第三,在函数advanced中有一行代码为“__advanced(iter,n,...);”这里的省略号中需要这样的功能:根据当前传入的迭代器InputIter生成一个迭代器标识类型的临时对象,然后通过该临时对象选择相应的重载函数。非常精巧的设计!!!!!!借鉴意义非常大~~~,可是如何来完成这样的功能呢?答案是:交给triats,别忘了前面所述的traits就是来屏蔽变化的。

为完成该功能traits进行了如下的定义,如代码段6所示,

STL源码学习之迭代器 - 天地任我游 - 天地任我游

 代码段6

STL中,迭代器的类型永远落在该迭代器所属类型中(上面提到的那5种!),最强化的那个,例如int*即是random_access_iterator_tag类型又是bidirectional_iterator_tag类型,同时也是forward_iterator_tag类型,也是input_iterator_tag那么它的类型应该是我们定义的random_access_iterator_tag

有了traits的帮助,advanced函数中的省略号就可以这么来做了:

STL源码学习之迭代器 - 天地任我游 - 天地任我游

 代码段7

这里“test_traits<InputIter>::iterator_category()”就像int()会产生一个临时的int对象一样,根据参数InputIter的不同产生一个不同的临时迭代器标识对象。


 

3、总结

 

通过对STL源码的迭代器部分的学习,重点学到了两种解决思路:1traits方式,通过引入了一个中间的traits就屏蔽掉了各种变化,使得算法不用管容器中存放的是什么东西,都可以用统一的方式来处理;2)使用类型标识来促成重载,这种方法在以前的编程中很少用到,很有借鉴意义。

【本文由天地任我游总结,转载请包含链接:http://houjixin.blog.163.com/

 

参考文献:

1、侯捷《STL源码分析》

  评论这张
 
阅读(1469)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018