STL设计思想之Traits技术

上一篇 / 下一篇 2011-08-15 13:18:43 / 个人分类：C++

STL是一个杰出的工业作品，可以很好的满足C++程序员的程序逻辑需求，包括对数据结构的需求,以及数据结构之上的算法需求，既是对与软件复用的很好实例.
STL的设计理念之一是它所追求的效率(这也是C++的目标)，STL无处不在追求最佳化的效率，比如uninitialized_copy函数，通过 traits技术来达到最佳的效率，当然这样的目的永远是无止境，而且要求是特别高的，就SGI的版本来说uninitilzed_copy在操作内置数据类型的时候,可以达到很好的效率，但是当类类型的时候，恐怕就无能为力了，traits技术也无力回天，只能按部就班。
STL的另一个重要设计目标是软件复用，而且这一点我认为已经发挥到了极致，是非常伟大的工业作品。软件复用的基石容易让人想到OO，STL也有利用OO技术，一个C++代码怎么可能不利用OO这样优秀的结构呢？ 但是真正起到中流砥柱作用的确实范型编程，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）引用。
下面我们来截取一段STL断面分析之
//STL 算法库中的find算法 1template <class _RandomAccessIter, class _Tp>  2_RandomAccessIter find(_RandomAccessIter __first, _RandomAccessIter __last,  3                       const _Tp& __val,  4                       random_access_iterator_tag)  5{  6  typename iterator_traits<_RandomAccessIter>::difference_type __trip_count //traits技术  7    = (__last - __first) >> 2;  8  9  for ( ; __trip_count > 0 ; --__trip_count) { 10    if (*__first == __val) return __first; 11    ++__first; 12 13    if (*__first == __val) return __first; 14    ++__first; 15 16    if (*__first == __val) return __first; 17    ++__first; 18 19    if (*__first == __val) return __first; 20    ++__first; 21  } 22 23  switch(__last - __first) { 24  case 3: 25    if (*__first == __val) return __first; 26    ++__first; 27  case 2: 28    if (*__first == __val) return __first; 29    ++__first; 30  case 1: 31    if (*__first == __val) return __first; 32    ++__first; 33  case 0: 34  default: 35    return __last; 36  } 37} 为了引用的完整性，很长的一段代码，暂且不管其算法，关注标红的那段代码，这端代码是用来解决这样的问题的
 template <class T,class Iterator> T find(Iterator first,Iterator last,T t) {     while(first!=last && T!=*first) first++; } 假如设计这样的类，用来查找区间[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函数的迭代器应该有这样的代码： template<class T> class myIterator{ typedef T value_type; //............}; 而max可以这么写 template<class Iterator> typename iterator_traits::value_type //返回值,iterator_traits取出对应迭代器的所指类型,下面有代码 max(Iterator first,Iterator end);
 template <class _Iterator> struct iterator_traits {   typedef typename _Iterator::iterator_category iterator_category;   typedef typename _Iterator::value_type        value_type;   typedef typename _Iterator::difference_type   difference_type;   typedef typename _Iterator::pointer           pointer;   typedef typename _Iterator::reference         reference; }; 
这样max就可以借由传入的迭代器知道它所指向的类型了,其实事情就是这么简单,整个traits技术不过如此,呵呵。 当然如果考虑的再可复用一点，那么traits似乎就没这么简单了，所谓的偏特化从此诞生！应为并不是所有的Iterator都是类类型，比如那个对于数组操作的find，其Iterator就是一个指针，但是怎么定义一个指针::vlaue_type呢?int*::value_type?不可能，死心吧。解决办法是对iterator_traits做点手脚。
 //偏特化 template <class _Tp> struct iterator_traits<_Tp*> {   typedef random_access_iterator_tag iterator_category;   typedef _Tp                         value_type;   typedef ptrdiff_t                   difference_type;   typedef _Tp*                        pointer;   typedef _Tp&                        reference; }; 当然整个traits机制还有const类型的偏特化，不在累述。
上面还提到用traits技术对于uninitialized_copy的优化，使用的是一个type_traits类，个人认为实在对不起这个名字，按照设计初衷，可以判断出类型是否有默认构造函数，析构函数，赋值构造函数，operator =，是否是一个POD，这么5个traits，其实根本无法判断，只是对于内置数据类型判断结果都是没有，对于类类型都是有，够弱智的~~~~ 文章出处：飞诺网：http://www.diybl.com/course/3_program/c++/cppsl/2008513/115798.html

收藏举报

TAG:

查看全部评论