STL设计思想之Traits技术
上一篇 / 下一篇 2011-08-15 13:18:43 / 个人分类:C++
<P>STL是一个杰出的工业作品,可以很好的满足C++程序员的程序逻辑需求,包括对数据结构的需求,以及数据结构之上的算法需求,既是对与软件复用的很好实例.</P>
<P>STL的设计理念之一是它所追求的效率(这也是C++的目标),STL无处不在追求最佳化的效率,比如uninitialized_copy函数,通过 traits技术来达到最佳的效率,当然这样的目的永远是无止境,而且要求是特别高的,就SGI的版本来说uninitilzed_copy在操作内置数 据类型的时候,可以达到很好的效率,但是当类类型的时候,恐怕就无能为力了,traits技术也无力回天,只能按部就班。</P>
<P>STL的另一个重要设计目标是软件复用,而且这一点我认为已经发挥到了极致,是非常伟大的工业作品。软件复用的基石容易让人想到OO,STL也有利用OO技术,一个C++代码怎么可能不利用OO这样优秀的结构呢?<BR>但是真正起到中流砥柱作用的确实范型编程,template class,范型的概念似乎在C++里面不是那么响亮,也许久是一个模板罢了~~~,当然这些所谓的范型(Generic)只不过就是一个名词吧了,它叫 什么并没有关系,从根本上讲就是编译时绑定,对应于OO的多态(有一个概念的东西)就是所谓的动态绑定,而OO的多态或许也可以叫运行时绑定。软件领域一 直有这样的嗜好,就是把一项新技术的名词起的多么抽象,集大成者可数微软了,函数指针、句柄、钩子,到句柄的时候我们还好画一段时间理解,恩,简单的讲就 是一个函数指针(甚至说就是一个指针),然后句柄(handle)那么也好说,想到以一个对象的把手,对的一个对象的指针就是它的把手嘛。然后是钩子,就 彻底晕了,这是什么东西呢?于是查了无数资料,发现就是函数指针,对于操作系统来说就是一个ID。这也许由于软件从业者的不合作精神,然后故意把一个东西 搞的故弄玄虚。那么我们再来看范型这个东西,不要被人们成天说这个东西而吓跑,其实范型可以很简单,一个template class也可以说是范型概念,不过template class可不是范型的全部,至于范型的定义,我也懒得去理了,那只是人们用来说的一个名字(他的确只是个名字),忘记它吧,记住的只要怎么写出复用的设 计,这才是一切的一切,STL到处都是template class,然后加上偏特化(partical specializtion),构成了令人炫目的代码。当然也很眩晕。STL内部的实现也无处不体现这复用,比如数据结构(STL中的容器)和算法的分 离,这样一个vector和list可以公用一个sort算法,是不是很酷呢?这里面又不得不说另一个名词了适配器(adapter),说的简单点就是 sort通过适配器对vector或者list进行操作,是的,适配器就是干这活的,说的再简单点,sort所操作的是一个区间,将vector和 list抽象成一个区间,sort其实是很专一的,他只对区间感兴趣,那么vector和list怎么来投其所好呢?这个时候就要有个适配器了,将 vector或者list装配成一个区间以适应sort。要怎么做呢?其实就是一个指针,分别指向区间的头和尾的下一个内存区域。就是贯穿于成个STL的 左闭右开[....)区间。可以问题在于这个指针的设计难度,关系到它的解引操作,于是又一项贯穿于STL的技术产生了,traits技 术,__traits_type。这就是偏特化大限身手的地方,traits贯穿于STL的每个角落,不过这个还只能说是一项技术,还不能称得上是一种概 念(conpenct)引用。</P>
<P>下面我们来截取一段STL断面分析之</P>
<P>//STL 算法库中的find算法<BR>1template <class _RandomAccessIter, class _Tp><BR> 2_RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,<BR> 3 const _Tp& __val,<BR> 4 random_access_iterator_tag)<BR> 5{<BR> 6 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count //traits技术<BR> 7 = (__last - __first) >> 2;<BR> 8<BR> 9 for ( ; __trip_count > 0 ; --__trip_count) {<BR>10 if (*__first == __val) return __first;<BR>11 ++__first;<BR>12<BR>13 if (*__first == __val) return __first;<BR>14 ++__first;<BR>15<BR>16 if (*__first == __val) return __first;<BR>17 ++__first;<BR>18<BR>19 if (*__first == __val) return __first;<BR>20 ++__first;<BR>21 }<BR>22<BR>23 switch(__last - __first) {<BR>24 case 3:<BR>25 if (*__first == __val) return __first;<BR>26 ++__first;<BR>27 case 2:<BR>28 if (*__first == __val) return __first;<BR>29 ++__first;<BR>30 case 1:<BR>31 if (*__first == __val) return __first;<BR>32 ++__first;<BR>33 case 0:<BR>34 default:<BR>35 return __last;<BR>36 }<BR>37} <BR>为了引用的完整性,很长的一段代码,暂且不管其算法,关注标红的那段代码,这端代码是用来解决这样的问题的</P>
<P><BR>template <class T,class Iterator><BR>T find(Iterator first,Iterator last,T t)<BR>{<BR> while(first!=last && T!=*first) first++;<BR>} <BR>假如设计这样的类,用来查找区间[first last)内元素是否和T相当的。注意这里的T!=*first操作,只是注意下,这个设计还是不错的,如果你要查找一个int[],这个设计是很不错 的,当然还是建议用vector。那么first是一个int*,last指向数组的越界,T此处是一个int,是的这是一个很好的设计,可以用来 long[],还可以double[],可是他不能用来在STL里面使用,问题在域Iterator的类型,学过数据结构的都知道list里面的其实不单 单是T,而是一个node,对T的一个简单封装(node* next),那么你的Iterator就是一个node*类型,因为对于list来说,迭代的其实是结点。问题的一个*Iterator得到的是一个 node,T!=node这样是没有意义的。这只是一个问题的雏形,反应出的问题是迭代器不知道他里面到底有什么(node不知道T的类型),有的时候在 知道迭代器类型的情况下还要知道迭代器所指的类型,比如想象一下max含说,接受两个迭代器类型的形参,返回一个T。客户端这么写int imax=(max(vector<int>::begin,vecvot<int>end)这个max实现的时候必须要知道T 的类型才可,但是编译器的template机制对于函数返回值是无能为力的,我们当然也可以将责任退到编译器厂商身上,但是在问题没有解决之前,只能自己 解决了。而STL的的解决方案是在Iterator的内部存储T的类型,比如上面的红色代码,而我们传入max函数的迭代器应该有这样的代码:<BR>template<class T> class myIterator{<BR>typedef T value_type;<BR>//............};<BR>而max可以这么写 <BR>template<class Iterator><BR>typename iterator_traits<I>::value_type //返回值,iterator_traits取出对应迭代器的所指类型,下面有代码<BR>max(Iterator first,Iterator end);</P>
<P><BR>template <class _Iterator><BR>struct iterator_traits {<BR> typedef typename _Iterator::iterator_category iterator_category;<BR> typedef typename _Iterator::value_type value_type;<BR> typedef typename _Iterator::difference_type difference_type;<BR> typedef typename _Iterator::pointer pointer;<BR> typedef typename _Iterator::reference reference;<BR>}; </P>
<P>这样max就可以借由传入的迭代器知道它所指向的类型了,其实事情就是这么简单,整个traits技术不过如此,呵呵。<BR>当然如果考虑的再可复用一点,那么traits似乎就没这么简单了,所谓的偏特化从此诞生!应为并不是所有的Iterator都是类类型,比如那个对于数 组操作的find,其Iterator就是一个指针,但是怎么定义一个指针::vlaue_type呢?int*::value_type?不可能,死心 吧。解决办法是对iterator_traits做点手脚。</P>
<P><BR>//偏特化<BR>template <class _Tp><BR>struct iterator_traits<_Tp*> {<BR> typedef random_access_iterator_tag iterator_category;<BR> typedef _Tp value_type;<BR> typedef ptrdiff_t difference_type;<BR> typedef _Tp* pointer;<BR> typedef _Tp& reference;<BR>}; <BR>当然整个traits机制还有const类型的偏特化,不在累述。</P>
<P>上面还提到用traits技术对于uninitialized_copy的优化,使用的是一个type_traits类,个人认为实在对不起这个名字,按 照设计初衷,可以判断出类型是否有默认构造函数,析构函数,赋值构造函数,operator =,是否是一个POD,这么5个traits,其实根本无法判断,只是对于内置数据类型判断结果都是没有,对于类类型都是有,够弱智的~~~~ <BR>文章出处:飞诺网:http://www.diybl.com/course/3_program/c++/cppsl/2008513/115798.html
<P>STL的设计理念之一是它所追求的效率(这也是C++的目标),STL无处不在追求最佳化的效率,比如uninitialized_copy函数,通过 traits技术来达到最佳的效率,当然这样的目的永远是无止境,而且要求是特别高的,就SGI的版本来说uninitilzed_copy在操作内置数 据类型的时候,可以达到很好的效率,但是当类类型的时候,恐怕就无能为力了,traits技术也无力回天,只能按部就班。</P>
<P>STL的另一个重要设计目标是软件复用,而且这一点我认为已经发挥到了极致,是非常伟大的工业作品。软件复用的基石容易让人想到OO,STL也有利用OO技术,一个C++代码怎么可能不利用OO这样优秀的结构呢?<BR>但是真正起到中流砥柱作用的确实范型编程,template class,范型的概念似乎在C++里面不是那么响亮,也许久是一个模板罢了~~~,当然这些所谓的范型(Generic)只不过就是一个名词吧了,它叫 什么并没有关系,从根本上讲就是编译时绑定,对应于OO的多态(有一个概念的东西)就是所谓的动态绑定,而OO的多态或许也可以叫运行时绑定。软件领域一 直有这样的嗜好,就是把一项新技术的名词起的多么抽象,集大成者可数微软了,函数指针、句柄、钩子,到句柄的时候我们还好画一段时间理解,恩,简单的讲就 是一个函数指针(甚至说就是一个指针),然后句柄(handle)那么也好说,想到以一个对象的把手,对的一个对象的指针就是它的把手嘛。然后是钩子,就 彻底晕了,这是什么东西呢?于是查了无数资料,发现就是函数指针,对于操作系统来说就是一个ID。这也许由于软件从业者的不合作精神,然后故意把一个东西 搞的故弄玄虚。那么我们再来看范型这个东西,不要被人们成天说这个东西而吓跑,其实范型可以很简单,一个template class也可以说是范型概念,不过template class可不是范型的全部,至于范型的定义,我也懒得去理了,那只是人们用来说的一个名字(他的确只是个名字),忘记它吧,记住的只要怎么写出复用的设 计,这才是一切的一切,STL到处都是template class,然后加上偏特化(partical specializtion),构成了令人炫目的代码。当然也很眩晕。STL内部的实现也无处不体现这复用,比如数据结构(STL中的容器)和算法的分 离,这样一个vector和list可以公用一个sort算法,是不是很酷呢?这里面又不得不说另一个名词了适配器(adapter),说的简单点就是 sort通过适配器对vector或者list进行操作,是的,适配器就是干这活的,说的再简单点,sort所操作的是一个区间,将vector和 list抽象成一个区间,sort其实是很专一的,他只对区间感兴趣,那么vector和list怎么来投其所好呢?这个时候就要有个适配器了,将 vector或者list装配成一个区间以适应sort。要怎么做呢?其实就是一个指针,分别指向区间的头和尾的下一个内存区域。就是贯穿于成个STL的 左闭右开[....)区间。可以问题在于这个指针的设计难度,关系到它的解引操作,于是又一项贯穿于STL的技术产生了,traits技 术,__traits_type。这就是偏特化大限身手的地方,traits贯穿于STL的每个角落,不过这个还只能说是一项技术,还不能称得上是一种概 念(conpenct)引用。</P>
<P>下面我们来截取一段STL断面分析之</P>
<P>//STL 算法库中的find算法<BR>1template <class _RandomAccessIter, class _Tp><BR> 2_RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,<BR> 3 const _Tp& __val,<BR> 4 random_access_iterator_tag)<BR> 5{<BR> 6 typename iterator_traits<_RandomAccessIter>::difference_type __trip_count //traits技术<BR> 7 = (__last - __first) >> 2;<BR> 8<BR> 9 for ( ; __trip_count > 0 ; --__trip_count) {<BR>10 if (*__first == __val) return __first;<BR>11 ++__first;<BR>12<BR>13 if (*__first == __val) return __first;<BR>14 ++__first;<BR>15<BR>16 if (*__first == __val) return __first;<BR>17 ++__first;<BR>18<BR>19 if (*__first == __val) return __first;<BR>20 ++__first;<BR>21 }<BR>22<BR>23 switch(__last - __first) {<BR>24 case 3:<BR>25 if (*__first == __val) return __first;<BR>26 ++__first;<BR>27 case 2:<BR>28 if (*__first == __val) return __first;<BR>29 ++__first;<BR>30 case 1:<BR>31 if (*__first == __val) return __first;<BR>32 ++__first;<BR>33 case 0:<BR>34 default:<BR>35 return __last;<BR>36 }<BR>37} <BR>为了引用的完整性,很长的一段代码,暂且不管其算法,关注标红的那段代码,这端代码是用来解决这样的问题的</P>
<P><BR>template <class T,class Iterator><BR>T find(Iterator first,Iterator last,T t)<BR>{<BR> while(first!=last && T!=*first) first++;<BR>} <BR>假如设计这样的类,用来查找区间[first last)内元素是否和T相当的。注意这里的T!=*first操作,只是注意下,这个设计还是不错的,如果你要查找一个int[],这个设计是很不错 的,当然还是建议用vector。那么first是一个int*,last指向数组的越界,T此处是一个int,是的这是一个很好的设计,可以用来 long[],还可以double[],可是他不能用来在STL里面使用,问题在域Iterator的类型,学过数据结构的都知道list里面的其实不单 单是T,而是一个node,对T的一个简单封装(node* next),那么你的Iterator就是一个node*类型,因为对于list来说,迭代的其实是结点。问题的一个*Iterator得到的是一个 node,T!=node这样是没有意义的。这只是一个问题的雏形,反应出的问题是迭代器不知道他里面到底有什么(node不知道T的类型),有的时候在 知道迭代器类型的情况下还要知道迭代器所指的类型,比如想象一下max含说,接受两个迭代器类型的形参,返回一个T。客户端这么写int imax=(max(vector<int>::begin,vecvot<int>end)这个max实现的时候必须要知道T 的类型才可,但是编译器的template机制对于函数返回值是无能为力的,我们当然也可以将责任退到编译器厂商身上,但是在问题没有解决之前,只能自己 解决了。而STL的的解决方案是在Iterator的内部存储T的类型,比如上面的红色代码,而我们传入max函数的迭代器应该有这样的代码:<BR>template<class T> class myIterator{<BR>typedef T value_type;<BR>//............};<BR>而max可以这么写 <BR>template<class Iterator><BR>typename iterator_traits<I>::value_type //返回值,iterator_traits取出对应迭代器的所指类型,下面有代码<BR>max(Iterator first,Iterator end);</P>
<P><BR>template <class _Iterator><BR>struct iterator_traits {<BR> typedef typename _Iterator::iterator_category iterator_category;<BR> typedef typename _Iterator::value_type value_type;<BR> typedef typename _Iterator::difference_type difference_type;<BR> typedef typename _Iterator::pointer pointer;<BR> typedef typename _Iterator::reference reference;<BR>}; </P>
<P>这样max就可以借由传入的迭代器知道它所指向的类型了,其实事情就是这么简单,整个traits技术不过如此,呵呵。<BR>当然如果考虑的再可复用一点,那么traits似乎就没这么简单了,所谓的偏特化从此诞生!应为并不是所有的Iterator都是类类型,比如那个对于数 组操作的find,其Iterator就是一个指针,但是怎么定义一个指针::vlaue_type呢?int*::value_type?不可能,死心 吧。解决办法是对iterator_traits做点手脚。</P>
<P><BR>//偏特化<BR>template <class _Tp><BR>struct iterator_traits<_Tp*> {<BR> typedef random_access_iterator_tag iterator_category;<BR> typedef _Tp value_type;<BR> typedef ptrdiff_t difference_type;<BR> typedef _Tp* pointer;<BR> typedef _Tp& reference;<BR>}; <BR>当然整个traits机制还有const类型的偏特化,不在累述。</P>
<P>上面还提到用traits技术对于uninitialized_copy的优化,使用的是一个type_traits类,个人认为实在对不起这个名字,按 照设计初衷,可以判断出类型是否有默认构造函数,析构函数,赋值构造函数,operator =,是否是一个POD,这么5个traits,其实根本无法判断,只是对于内置数据类型判断结果都是没有,对于类类型都是有,够弱智的~~~~ <BR>文章出处:飞诺网:http://www.diybl.com/course/3_program/c++/cppsl/2008513/115798.html
TAG:
希望自己天天进步
标题搜索
日历
|
|||||||||
日 | 一 | 二 | 三 | 四 | 五 | 六 | |||
1 | 2 | 3 | 4 | ||||||
5 | 6 | 7 | 8 | 9 | 10 | 11 | |||
12 | 13 | 14 | 15 | 16 | 17 | 18 | |||
19 | 20 | 21 | 22 | 23 | 24 | 25 | |||
26 | 27 | 28 | 29 | 30 | 31 |
我的存档
数据统计
- 访问量: 67049
- 日志数: 79
- 书签数: 1
- 建立时间: 2010-08-29
- 更新时间: 2013-04-06