侯捷老师在《STL 源码剖析》中说到:了解 traits 编程技术,就像获得 "芝麻开门" 的口诀一样,从此得以一窥 STL 源码的奥秘。如此一说,其重要性就不言而喻了。
之前已经介绍过迭代器,知道了不同的数据结构都有自己专属的迭代器,不同的迭代器也有不同的特性,由于算法的接口是统一的,通过迭代器的不同属性,算法自动选择正确的执行流程,在完全任务的同时,也尽可能提高算法的执行效率。那算法如何获知迭代器的属性呢?这一光荣的任务就是 traits 完成的。在 STL 实现中,traits 编程技术得到大量的运用,它利用了 "内嵌类型" 的编程技巧与 C++ 的 template 参数推导功能,弥补了 C++ 类型识别方面的不足。通过 traits,算法可以原汁原味的将迭代器的属性萃取出来,帮助算法正确高效的运行。
前面说了很多关于 traits 的光荣事迹,但是却一直没有介绍 traits 究竟是个什么东西,究竟是用来干什么的?traits 在英文解释中就是特性,下面将会引入 traits 技术的作用,一步一步地揭开其神秘的面纱。
下面是一个以迭代器为模板形参的函数模板:
- template
- void func(Iterator iter)
- {
- //函数体
- }
假如现在算法中需要声明一个变量,而变量的类型是迭代器所指对象的类型,应该怎么处理呢?
- template
- void func(Iterator iter)
- {
- *Iterator var;//这样定义变量可以吗?
- }
上面的代码是不可以通过编译的,虽然 C++ 支持 sizeof(),但是并不支持 typeof(),就算是用到 RTTI 性质中的 typeid(),获取到的也仅仅是类型的名字,因此不能直接用来声明变量。此时可以利用函数模板的参数类型推导机制解决问题,例如:
- template
- void func_impl(Iterator iter, T t)
- {
- T temp;//这里就解决了问题
- //这里做原本func()的工作
- }
- template
- void func(Iterator iter)
- {
- func_impl(iter, *iter);//func的工作全部都移到func_impl里面了
- }
- int main(int argc, const char *argv[])
- {
- int i;
- func(&i);
- }
函数 func 作为对外接口,实际的操作却由函数 func_impl 执行,通过函数 func_impl 的参数类型推导,获取到 Iterator 指向对象的类型 T,从而解决了问题。
现在通过函数模板的参数类型推导解决了函数体内声明变量的问题,但问题又来了,如果需要返回类型是迭代器所指对象的类型又可以怎样做呢?
- template
- (*Iterator) func(Iterator iter)
- {
- //这样定义返回类型可以吗?
- }
在这种情况下,模板的参数类型推导机制也无能为力了,因为它只能推导参数,并不能推导函数的返回类型。STL 解决这种问题的办法就是内嵌类型声明,即在迭代器内部添加一种 "特性",通过这种 "特性",算法可以很容易地获知迭代器所指对象的类型,请看下面的代码:
- template
- class Iterator
- {
- public:
- typedef T value_type;//内嵌类型声明
- Iterator(T *p = 0) : m_ptr(p) {}
- T& operator*() const { return *m_ptr;}
- //...
- private:
- T *m_ptr;
- };
- template
- typename Iterator::value_type //以迭代器所指对象的类型作为返回类型,长度有点吓人!!!
- func(Iterator iter)
- {
- return *iter;
- }
- int main(int argc, const char *argv[])
- {
- Iterator<int> iter(new int(10));
- cout<//输出:10
- }
函数 func() 的返回类型前面必须加上关键词 typename,原因在本人之前写的"C++ 模板学习 "中也解释过,因为 T 是一个 template 参数,编译器在编译实例化 func 之前,对 T 一无所知,就是说,编译器并不知道 Iterator<T>::value_type 是一个类型,或者是一个静态成员函数,还是一个静态数据成员,关键词 typename 的作用在于告诉编译器这是一个类型,这样才能顺利通过编译。
之前在介绍迭代器的分类之时说过,原生指针也是一种迭代器,此时问题就来了,原生指针并不是一种类类型,它是无法定义内嵌类型的。因此,上面的内嵌类型实现还不能完全解决问题,那可不可以针对原生指针做特殊化的处理呢?答案是肯定的,利用模板偏特化就可以做到了。
《泛型思维》一书对模板偏特化的定义是:
- /这个泛型版本允许T为任何类型
- template
- class C
- {
- //...
- };
我们很容易接受上面的类模板有一个形式如下的偏特化版本:
- template
- class C
- {
- //...
- };
这个特化版本仅适用于 T 为原生指针的情况,"T 为原生指针" 就是 "T 为任何类型" 的一个更进一步的条件限制。那如何利用模板偏特化解决原生指针不能内嵌类型的问题呢?下面介绍的 iterator_traits 就是关键了。
标准库中声明如下:
- template class iterator;
- template <class Iterator> class iterator_traits;
- template <class T> class iterator_traits;
- template <class T> class iterator_traits<const T*>;
STL 里面使用 iterator_traits 这个结构来专门 "萃取" 迭代器的特性,前面代码中提到的 value_type 就是迭代器的特性之一:
- template
- struct iterator_traits
- {
- typedef typename Iterator::value_type value_type;
- };
如果 Iterator 有定义 value_type,那么通过 iterator_traits 作用之后,得到的 value_type 就是 Iterator::value_type,比较之前写的版本和经 iterator_traits 作用后的版本:
- template
- typename Iterator::value_type //这行是返回类型
- func(Iterator iter)
- {
- return *iter;
- }
- //通过iterator_traits作用后的版本
- template
- typename iterator_traits::value_type //这行是返回类型
- func(Iterator iter)
- {
- return *iter;
- }
从长度上看,好像需要敲的代码更多了,为什么要这么麻烦加上一层间接层呢?由于原生指针也是一种迭代器,而且不是一种类类型,因此原生指针并不能定义内嵌类型。这里通过实现 iterator_traits 的一个偏特化版本就可以解决这个问题了,具体的实现如下:
- //iterator_traits的偏特化版本,针对迭代器是个原生指针的情况
- template
- struct iterator_traits
- {
- typedef T value_type;
- };
大家在进行函数重载的时候,应该都曾遇到过以下的情况:
- //函数版本一
- void func(int *ptr)
- {
- //...
- }
- //函数版本二
- void func(const int *ptr)
- {
- //...
- }
以上两个函数虽然函数、形参个数和位置都一样,但它们不是同一个函数,而是函数重载的一种情况,也就是说函数形参的 const 和非 const 版本是不一样的,在函数版本一里面,可以修改指针 ptr 指向的数据,但是在函数版本二里面却不可以,因为传入的指针 ptr 是一个 const 指针。由此可以联想到,当将一个 const 指针作为模板形参传给前面声明的偏特化版本的 iterator_traits 会有发生什么情况呢?
- iterator_traits < const int * >::value_type //获得的value_type是const int,并不是int
当我们想用 iterator_traits 萃取出 value_type 并声明一个临时变量时,却发现声明的变量是 const 类型,并不能进行赋值,这违背了我们的用意。我们需要一种方法区别 const 和非 const 才能避免这种误会的发生,答案很简单,只要另外再设计一个 iterator_traits 偏特化版本就可以了:
- template
- struct iterator_traits<const T*>
- {
- typedef T value_type;
- }
现在,不论是自定义的迭代器,还是原生指针 int * 或者是 const int*,都可以通过 iterator_traits 获取到正确的 value_type。
STL 根据经验,定义了迭代器最常用到的五种类型:value_type、difference_type、pointer、reference、iterator_category,任何开发者如果想将自己开发的容器与 STL 结合在一起,就一定要为自己开发的容器的迭代器定义这五种类型,这样都可以通过统一接口 iterator_traits 萃取出相应的类型,下面列出 STL 中 iterator_traits 的完整定义:
- tempalte
- struct iterator_traits
- {
- typedef typename I::iterator_category iterator_category;
- typedef typename I::value_type value_type;
- typedef typeanme I:difference_type difference_type;
- typedef typename I::pointer pointer;
- typedef typename I::reference reference;
- };
下面会分别介绍一下这五种类型:
(1) 迭代器类型之一:value_type
value_type 就是指迭代器所指对象的类型,例如,原生指针也是一种迭代器,对于原生指针 int*,int 即为指针所指对象的类型,也就是所谓的 value_type。
(2) 迭代器类型之二:difference_type
difference_type 用来表示两个迭代器之间的距离,例如:
- int array[5] = {
- 1,
- 2,
- 3,
- 4,
- 5
- };
- int * ptr1 = array + 1; //指向2
- int * ptr2 = array + 3; //指向4
- ptrdiff_t distance = ptr2 - ptr1; //结果即为difference_type
上面代码中,指针 ptr2 与 ptr1 相减的结果的类型就是 difference_type,对于原生指针,STL 以 C++ 内建的 ptrdiff_t 作为原生指针的 difference_type。
(3) 迭代器类型之三:reference_type
reference_type 是指迭代器所指对象的类型的引用,reference_type 一般用在迭代器的 * 运算符重载上,如果 value_type 是 T,那么对应的 reference_type 就是 T&;如果 value_type 是 const T,那么对应的 reference_type 就是 const T&。
(4) 迭代器类型之四:pointer
pointer 就是指迭代器所指的对象,也就是相应的指针,对于指针来说,最常用的功能就是 operator * 和 operator-> 两个运算符。因此,迭代器需要对这两个运算符进行相应的重载工作:
- T & operator * () const {
- return * ptr;
- } // T& is reference type
- T * operator - >() const {
- return ptr;
- } // T* is pointer type
5) 迭代器类型之五:iterator_category
iterator_category 的作用是标识迭代器的移动特性和可以对迭代器执行的操作,从 iterator_category 上,可将迭代器分为 Input Iterator、Output Iterator、Forward Iterator、Bidirectional Iterator、Random Access Iterator 五类,具体为什么要这样分类,简单来说,就是为了尽可能地提高效率,这也是 STL 的宗旨之一。具体的情况已经在本人的 "《STL 源码剖析》学习之迭代器" 中详细介绍过,这里就不在多说了。
为了保证 iterator_traits 可以正常工作,STL 提供了一个 iterator 类,所有自定义的迭代器都必须继承自它,这样才能保证这些自定义的迭代器可以顺利地狱其它 STL 组件进行协作,iterator 类具体定义如下:
- template<typename Category,
- typename T,
- typename Distance = ptrdiff_t,
- typename Pointer = T*,
- typename Reference = T&>
- struct iterator
- {
- typedef Category iterator_category;
- typedef T value_type;
- typedef Distance difference_type;
- typedef Pointer pointer;
- typedef Reference reference;
- };
类 iterator 不包含任何成员变量,只有类型的定义,因此不会增加额外的负担。由于后面三个类型都有默认值,在继承它的时候,只需要提供前两个参数就可以了,如:
- template <typename T>
- class ListIter : public std::iterator<std::forward_iterator_tag, T>
- {
- //...
- }
来源: http://www.bubuko.com/infodetail-1972559.html