STL源码剖析_traits特性萃取技术

有了迭代器之后,我们就会在各种算法的实现中,通过迭代器来操作各种容器。但是在这个过程中,我们有时候需要用到”迭代器所指向的类型”。
(理解traits需要了解模板、特化、偏特化等概念)

为什么需要traits技术

我们的算法接口通常是只接受迭代器作为参数,就像下面这个函数的参数:

1
2
3
void reverse(Iterator first,Iterator last){
...
};

但是有时候只有迭代器是不够的,我们可能还需要迭代器所指向数据的类型。
假如现在需要实现一个函数:接受一个迭代器,然后将迭代器所指的变量值取出来,然后将其加1,最后也不用返回该值。
函数的实现应该像下面这样:

1
2
3
4
5
template<typename Iter>
void addone(Iter iter){
T tmp=*iter;//此处T的类型我们无法获取
tmp++;
}

上面这个代码里的问题在于,这个函数只接收了一个Iter参数,我们可以靠模板的参数推导机制获得这个迭代器的类型推导机制获得这个迭代器的类型。
但是我们无法得到该迭代器所指向数据的类型。这时候你可能会想到,我们可以给函数再加一个参数,让调用者把指向的数据直接传进来,然后再利用类型推导机制得到参数类型。
这样是可以的,但是为了保证addone函数的接口的简洁性,我们可以用下面这种方式:

1
2
3
4
5
6
7
8
9
10
template<typename Iter>
void addone(Iter iter){
_addone(iter,*iter);
}

template<typename Iter,typename T>
void _addone(Iter iter,T t){
T tmp=*iter;//我们通过类型推导机制,已经获取到T的类型了。
tmp++;
}

这样已经比较丑陋地解决了这个问题了,但是如果要求addone函数返回加1后的值呢?
内层的_addone前面我们可以加一个T,表示返回的是T类型,但是外层的addone的返回值我们该写个什么呢?

如何实现traits

所以我们需要一个魔法,通过迭代器的类型,就可以获取到其指向的数据的类型,就像下面这样:

1
2
3
4
5
6
template<typename Iter>
魔法<Iter> addone(Iter iter){
魔法<Iter> tmp=*iter;
tmp++;
return tmp;
}

那么接下来我们实现这个魔法就行了。这个魔法也有两层,分为不通用的和通用的。
首先看不通用的,迭代器既然指向了一个数据,按说这个数据的类型也应该由迭代器保存,所以这个工作应当是迭代器来干,以上一篇迭代器文章中的listIter为例:

1
2
3
4
5
6
7
8
9
template <typename Item>
class ListIter{
public:
...
...
private:
Item *ptr;
typedef Item value_type;//将模板推导出来的Item定义为一个类型
};

我们就可以这样来实现addone了:

1
2
3
4
5
6
typename ListIter::value_type
addone(ListIter iter){
typename ListIter::value_type tmp=*iter;
tmp++;
return tmp;
}

但是这种方法,针对每一种迭代器,我们都需要重写一套算法,改写其返回值,非常不符合我们模板机制的风格。
所以我们需要下面这种通用于不同迭代器的技术:

1
2
3
4
template<typename I>
struct iterator_traits{
typedef typename I::value_type value_type;
}

然后addone算法写成下面这样就可以了:

1
2
3
4
5
6
7
template<typename Iter>
typename iterator_traits<Iter>::value_type
addone(ListIter iter){
typename iterator_traits<Iter>::value_type tmp=*iter;
tmp++;
return tmp;
}

另外针对原生指针,const指针再实现一下相应的特化版本就行了。

参考

欢迎与我分享你的看法。
转载请注明出处:http://taowusheng.cn/