STL源码剖析笔记 - traits编程技法

C++

设计目的

STL中，算法（algorithm）和容器（container）是分离的，如何再两者之间实现合适的“粘合剂”是一个关键问题。Iterator就是这个“粘合剂”，如何在Iterator中获得container需要的类型，就要借助traits

traits编程技法

通常模板编程可以用来将不同类型的逻辑进行复用，但是有些情况下简单的类型推倒不能完成我们的需求。比如需要根据返回值的类型进行不同处理的情况。

将类型声明内嵌是个解决方法：

template <class T>
struct MyIter{
    typedef T value_type; // 内嵌型别声明
    T* ptr;
    MyIter(T* p = 0): ptr(p){}
    T& operator*() const {return *ptr;}
    //...
};
template <class I>
typename I::value_type // 函数的返回值，typename是告诉编译器，这是一个型别
func(I ite)
{ return *ite; }
//...
MyIter<int> ite(new int(8));
cout << func(ite); // 输出 8

上述方法有一个缺陷，每个迭代器必须是类别（class type），但是原生指针并不是，因此无法定义内嵌型别。为了兼容原生指针作为迭代器的情况，需要用到偏特化的特性。

偏特化

下面是一个偏特化的例子，注意偏特化不能在函数中使用，需要用重载来替代偏特化，更多偏特化支持，请参考其他资料。

// 接受T为任何类型
template <typename T>
class C {...}
// 只接受T为原生指针的类型
template <typename T>
class C<T*>{...}

利用这种偏特化的特性，可以解决上述原生指针引出的问题。

traits

接下来是traits的核心

template <class I>
struct iterator_traits{
    typedef typename I::value_type value_type;
};

上述func调用可以写为

template<class I>
typename iterator_traits<I>::value_type //这是返回值
func (I ite)
{ return *ite; }

上述返回值多了一层间接地调用，这一层就可以进行特化，比如针对原生指针，我们提供如下特化版本

template<class T>
struct iterator_traits<T*>{
    typedef T value_type;
};

此时，模板参数为原生指针时（比如int*），通过这个特化版本，就将value_type萃取为int。需要注意，以上的方案面对如下情况时不太合理。

iterator_traits<const int*>::value_type; //萃取到 const int

萃取到const型别没什么用，因此，再添加一个特化版本，解决这个问题

template <class T>
struct iterator_traits<const T*>{
    typedef T value_type;
};

这时，两种情况都可以处理。
上述traits方法扮演了“型别萃取机”的角色，可以想到，若要这个“萃取机”正常运行，每个迭代器必须定义自己的型别(value_type)，这是STL的约定。

traits中的型别

template <typename T>
struct iterator_traits{
    typedef typename T::iterator_category   iterator_category;
    typedef typename T::value_type          value_type;
    typedef typename T::different_type      different_type;
    typedef typename T::pointer             pointer;
    typedef typename T::reference           reference;
};

value_type

如之前所述

different_type

该类型表示两个迭代器之间的距离，也可以用来表示容器的最大容量。例如，count函数

template<class I, class T>
typename iterator_traits<I>::different_type
count(I first, I end, const T& value){
    typename iterator_traits<I>::different_type count = 0;
    for(; first != end; ++first)
    {
        if(*first == value) count ++;
    }
    return n;
}

也需要提供原生指针的特化版本和point-to-const版本

template <class I>
struct iterator_traits{
    ...
    typedef typename I::different_type different_type;
};
template <class T>
struct iterator_traits<T*>{
    ...
    typedef ptrdiff_t different_type; // ptrdiff_t是C++内建的类型
};
// pointer-to-const 的特化版
template <class T>
struct iterator_traits<const T*>{
    ...
    typedef ptrdiff_t different_type;
};

pointer, reference

迭代器应该有提领和指针操作，通常如下

Item& operator*() const { return *ptr; }
Item* operator->() const { return ptr; }

这里Item&是Iter的reference type，而Iter*是pointer type。
将这两个类型放入traits内

template<class I>
struct iterator_traits{
    ...
    typedef I::pointer      pointer;
    typedef I::reference    reference;
};
// 原生指针的偏特化版本
template<class T>
struct iterator_traits<T*>{
    ...
    typedef T*      pointer;
    typedef T&      reference;
};
// pointer-to-const的偏特化版本
template<class T>
struct iterator_traits<const T*>{
    ...
    typedef const T*    pointer;
    typedef const T&    reference;
};

iterator_category

该类型表示迭代器的类型，根据移动和施行的操作，迭代器被分为五类：

• Input Iterator 只读迭代器
• Output Iterator 只写迭代器
• Forward Iterator 单向移动(operator++)，允许在此种迭代器的区间上进行读写操作
• Bidirectional Iterator 可双向移动的迭代器
• Random Access Iterator 前三种都支持(operator ++)，第四种加上(operator--)，该种涵盖所有指针运算能力，p+n, p-n, p[n], p2-p1, p1<p2

介绍这些概念是因为，依照不同类型的迭代器类型，提供运算的效率是不同的，我们需要合适的函数里用最高的效率解决问题。我们可以在运行时根据不同类型选择不同的算法进行计算，但是这样有损效率。使用函数重载的方法可以高效的解决这个问题，定义下面五个class

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct input_iterator_tag : public forward_iterator_tag {};
struct input_iterator_tag : public bidirectional_iterator_tag {};

依照不同的迭代器类型，可以调用不同版本的函数，以advance函数为例

// 2
template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n)
{
    // 1
    __advance(i, n, iterator_traits<InputIterator>::iterator_category());
}
template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, input_iterator_tag)
{
    while (n--) ++i;
}
template <class ForwardIterator, class Distance>
inline void __advance(ForwardIterator& i, Distance n, forward_iterator_tag)
{
    advance(i, n, input_iterator_tag());
}
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;
}
template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag)
{
    i += n;
}

1. 这里iterator_traits::iterator_category()生成临时对象，用以进行重载判决
2. 这里typename 为InputIterator是STL命名规则，以接受最低阶的类型为参数命名。

总结

用编程实现traits技法不难看出，traits充分利用了偏特化的特点实现了容器和算法之间的桥梁作用，代码实现traits的功能，也让自己对模板特化属性有了进一步的理解。

参考

侯捷. STL源码剖析[M]. 华中科技大学出版社, 2002.