STL源码笔记2 —— traits
简介
在stl的源码中，广泛用到了traits这个字样，用来表达一个萃取的方法的描述。traits在stl中的用途一般有几种，包括对应迭代器iterator的iterator traits，对应类类型的type traits，针对指针pointer的pointer traits等等。而它的核心思想就是想通过定义好的某种规则，只要写的代码按照这种规则给出对应的定义，那么就能通过traits的机制，融入到泛化后的各种操作或者算法等。
iterator traits
光是上面的说明可能还不是十分理解traits的作用，在stl源码中，应用最广泛的就是容器迭代器相关的iterator traits。之前在使用stl的时候可能也会好奇，为什么stl里面一些算法或者函数都是传进去iterator，就可以正确的运行，但对应的各个容器的iterator却并不是一模一样的，而是有各自特性的，那么他们究竟是怎么实现的呢？
例如我们看gcc2.95的stl源代码中的 advanced() 函数
template <class _InputIterator, class _Distance>
inline void advance(_InputIterator& __i, _Distance __n) {
__advance(__i, __n, iterator_category(__i));
}
而 __advance() 有几个偏特化版本：
template <class _InputIter, class _Distance>
inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) {
while (__n--) ++__i;
}
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1183
#endif
template <class _BidirectionalIterator, class _Distance>
inline void __advance(_BidirectionalIterator& __i, _Distance __n,
bidirectional_iterator_tag) {
if (__n >= 0)
while (__n--) ++__i;
else
while (__n++) --__i;
}
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1183
#endif
template <class _RandomAccessIterator, class _Distance>
inline void __advance(_RandomAccessIterator& __i, _Distance __n,
random_access_iterator_tag) {
__i += __n;
}
可以看出来，在调用advance的时候，里面会调用__advance()，而传递进去的第三个参数，正是通过 iterator_category() 萃取出的迭代器类型，然后再根据不同类型进入不同偏特化版本的 __advance()。而在 stl_iterator.h 文件里面，可以看到iterator_category()的构造函数会根据 iterator_category 的值来返回对象：
template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
iterator_category(const _Iter& __i) { return __iterator_category(__i); }
template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&)
{
typedef typename iterator_traits<_Iter>::iterator_category _Category;
return _Category();
}
由此，整个iterator traits的流程就出来了，其实就是根据定义迭代器的时候定义的 iterator_category 决定了最后会调用的函数偏特化版本，而如果我们自己去定义一个容器，想让对应的迭代器iterator能使用stl中的各种函数，则也需要按照规则定义好迭代器里的这种识别类型。一般常用的识别类型有以下几个：
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; //引用
};
type traits
同样的，type traits 也是一种针对泛型函数的处理手法，这次需要萃取的是跟类或类型的产生密切相关的东西。type traits 更多的是关注类的构造、拷贝构造、析构、赋值等几个对类而言十分重要的函数，由此产生出更有效率的通用代码。
template <class _Tp>
struct __type_traits {
typedef __true_type this_dummy_member_must_be_first;
typedef __false_type has_trivial_default_constructor; //不重要的默认构造函数
typedef __false_type has_trivial_copy_constructor; //不重要的拷贝构造函数
typedef __false_type has_trivial_assignment_operator; //不重要的赋值函数
typedef __false_type has_trivial_destructor; //不重要的析构函数
typedef __false_type is_POD_type; //plain old data 普通旧数据
};
这次也是gcc 2.95版本的源代码，观察的是copy()函数。在容器里面copy几乎是贯穿始终的很重要的函数，而它的效率也极大的影响容器的效率，所以在copy()函数中可以看到针对各种类型做了很细致的处理：
template <class _InputIter, class _OutputIter>
inline _OutputIter copy(_InputIter __first, _InputIter __last,
_OutputIter __result) {
typedef typename iterator_traits<_InputIter>::value_type _Tp;
typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
_Trivial;
return __copy_dispatch<_InputIter, _OutputIter, _Trivial>
::copy(__first, __last, __result);
}
inline char* copy(const char* __first, const char* __last, char* __result) {
memmove(__result, __first, __last - __first);
return __result + (__last - __first);
}
inline wchar_t* copy(const wchar_t* __first, const wchar_t* __last,
wchar_t* __result) {
memmove(__result, __first, sizeof(wchar_t) * (__last - __first));
return __result + (__last - __first);
}
上面的代码首先分为了3类，迭代器版本，字符串 char* 版本和 wchar_t* 版本，除了迭代器版本，另外两个字符串的都是直接使用memmove操作，所以效率极高。那么再往下看迭代器版本的实现：
template <class _InputIter, class _OutputIter, class _BoolType>
struct __copy_dispatch {
static _OutputIter copy(_InputIter __first, _InputIter __last,
_OutputIter __result) {
typedef typename iterator_traits<_InputIter>::iterator_category _Category;
typedef typename iterator_traits<_InputIter>::difference_type _Distance;
return __copy(__first, __last, __result, _Category(), (_Distance*) 0);
}
};
template <class _Tp>
struct __copy_dispatch<_Tp*, _Tp*, __true_type>
{
static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
return __copy_trivial(__first, __last, __result);
}
};
template <class _Tp>
struct __copy_dispatch<const _Tp*, _Tp*, __true_type>
{
static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
return __copy_trivial(__first, __last, __result);
}
};
可以看到，针对迭代器版本，经过 __copy_dispatch 的分离后，如果是经过type_traits分析后，发现类的 has_trivial_assignment_operator 是 __true_type，那么就会跑到指针或者const指针的偏特化版本。此时，copy里面的实现是直接调用 __copy_trivial ，内部实现也是使用快速的memmove。源码如下：
template <class _Tp>
inline _Tp*
__copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result) {
memmove(__result, __first, sizeof(_Tp) * (__last - __first));
return __result + (__last - __first);
}
而如果有特殊的赋值函数，那么就再分离普通迭代器和随机迭代器，这两种迭代器的区别在于 randomAccessIter 可以在循环前就确切知道需要循环的次数，从而再提升一点效率：
template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __copy(_InputIter __first, _InputIter __last,
_OutputIter __result,
input_iterator_tag, _Distance*)
{
for ( ; __first != __last; ++__result, ++__first)
*__result = *__first;
return __result;
}
template <class _RandomAccessIter, class _OutputIter, class _Distance>
inline _OutputIter
__copy(_RandomAccessIter __first, _RandomAccessIter __last,
_OutputIter __result, random_access_iterator_tag, _Distance*)
{
for (_Distance __n = __last - __first; __n > 0; --__n) {
*__result = *__first;
++__first;
++__result;
}
return __result;
}
后话
从上面的两段源码，可以看出其实traits就是充当一个中间转换的角色。对于STL中许多泛化后的函数，如果能通过traits机制，从而知道其中一些参数的具体的类型，就能很好的运用后这些抽象过后的泛化函数。而如果自己编写一些容器或者类，只要将对应的识别类型都定义好，也就可以很好的融合到STL里面一起使用。