首页 > 代码库 > traits技法小计
traits技法小计
在学习算法导论的时候，对于各数据结构，自然是实现一个才算掌握，工具当然是template编程，但是自己的demo经常存在很多问题，比如没有给出迭代器啊，操作符重载
不够啊等等设计上的问题，而某些问题实际上是从设计之初就该考虑的大框架，而非小细节。对于C++而言，STL无疑是最佳的参考资料，侯捷先生的STL源码剖析一书给我们良好的示范，
而直接从第四章开始看会云里雾里，无法得其精髓，因此在学习算法之余决定尾随侯捷先生脚步，学习STL traits技法，从而可以从STL中学到更多的数据结构实现。
收获自是颇多，不仅可以掌握数据结构的基础知识，还会教会我们如何去筛选那些实现的方案，比如hash_table选择了chaining法解决冲突，map和set采用红黑树等等，
而且对我们C++泛型编程技法和C++重载技术也是极好的锻炼，源码之前，尽是宝藏。
当然前提是有良好的数据结构知识和C++primer程度的C++技能。
本文对侯捷先生的第二章进行简单概括，便于日后查看，将一些和traits不太相关的比如C++语法等略去。
我们以list的迭代器开发来逐步走入STL 迭代器的世界
1 template<typename T> 2 class List //链表 3 { 4 void insert_front(T value); 5 void insert_end(T value); 6 void display(ostream &os=cout) const; 7 private: 8 ListItem<T>* _end; 9 ListItem<T>* _front; 10 long _size; 11 }; 12 13 template<typename T> 14 class ListItem //结点 15 { 16 public: 17 T get_value()const; 18 ListItem* next()const; 19 private: 20 T _value; 21 ListItem* _next; 22 }; 23 24 //要定义迭代器需要封装指针 25 template<class Item> // Item的实际参数是ListItem 26 struct ListIter 27 { 28 Item *ptr; //指向结点的指针，迭代器就是在此基础上封装 29 30 ListIter(Item *p=0):ptr(p){}//构造函数 31 32 Item& operator*()const{return *ptr;}//解引用 33 Item* operator->()const{return ptr;}//->操作符 34 //... 35 }; 36 37 /* 38 这里存在问题，我们将listiter封装，并于list绑定，用于泛型算法 39 时，无法获取iter所指对象型别以及迭代器距离，所指之物的引用和指针等， 40 STL中借助模板类型推导来实现这一点 41 */ 42 //第一想法是在模板形参表当中加入另一个参数，即所指之物的类型,然后将双参数的函数放在private中，在public接口函数中调用private函数 43 44 template<typename Item, typename value> 45 class Item 46 { 47 private: 48 void func_pri(Item iter,value v); 49 public: 50 void func(Item iter){func_pri(iter,*iter);} 51 }; 52 //问题又来了，如果在返回值中想要获取类型怎么办？C++ 的参数推导不可以在返回值中使用，因为从C继承而来的函数的必要因素是参数和函数名，调用 53 //一个函数并不需要返回值，因此若支持返回值自动推导，编译器可能无法获知其类型 54 55 这里还有一种方法完成： 56 template<class value> 57 class Iter // 在迭代器的定义中内嵌一个关于value_type的声明 58 { 59 typedef value value_type; 60 }; 61 62 template<class I> 63 typename Iter::value_type func(I i) //这是某个Iter适用的函数（泛型算法，并不是Iter类的成员函数），算法的形参为迭代器类型，在其中可以访问value_type，符合我们的预期 64 { 65 return *i; 66 } 67 68 //只有一个小问题，和指针不兼容，因为指针不可内嵌声明，因为它不是类类型。 69 我们想到了C++中template编程的一种技法，即部分特化，注意部分特化和特化是不同的，特化后实质已经不是模板，而部分特化是对模板的一个特殊情况，仍是模板 70 接下来正式介绍traits技法 71 72 ------------------------------------------------------------------------------------------------- 73 //trait技法 74 template<class I> 75 struct iterator_traits 76 { 77 typedef typename I::value_type value_type; 78 typedef typename I::iterator_category iterator_category; 79 /*此型别比较特殊，是因为iterator有5种（写入、只读、读写、双向、随机）,应用于泛型算法时，不同算法针对不同类型的迭代器有不同的效率，应该分开实现 80 比如，对于+操作而言，随机迭代器效率是O（1），写入是O（n），应该针对随机迭代器另行实现 81 让我们想到了函数重载，但问题是上面的不同类型的迭代器都是模板参数，编译器无法获取它的类型，因此无法重载，因此加入这一个参数作为标志，此标志必须是类类型，才可以推导进行重载决议 82 具体的实现见P95*/ 83 typedef typename I::difference_type difference_type; 84 typedef typename I::pointer pointer; 85 typedef typename I::reference reference; 86 }; 87 部分特化版本--原生指针 88 template<class P> 89 struct iterator_traits<P*> 90 { 91 typedef typename P value_type; 92 typedef typename random_access_iterator_tag iterator_category; 93 typedef typename ptrdiff_t difference_type; 94 typedef typename P* pointer; 95 typedef typename P& reference; 96 }; 97 98 部分特化版本--const指针 99 template<class P>100 struct iterator_traits<const P*>101 {102 typedef typename P value_type;103 typedef typename random_access_iterator_tag iterator_category;104 typedef typename ptrdiff_t difference_type;105 typedef typename const P* pointer;106 typedef typename const P& reference; 107 };108 ------------------------------------------------------------------------------------------------------------------109 110 template<class I>111 typename iterator_traits<I>::value_type func(I i) //这个和上面的无区别，就是间接取了一下,但好处在于有部分特化版本，对于不同类型的参数会返回正确的类型112 {113 return *i;114 }115 116 117 我们自己实现iterator的时候，可以继承iterator class，见P100
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。