在 STL 源码中,到处可见 Traits 的身影,其实 Traits 不是一种语法,更确切地说是一种技术。
STL库中,有一个函数叫做 advance, 用来将某个迭代器(具有指针行为的一种 class)移动
某个给定的距离。声明如下:
template <typename IterT, typename DistT> // 将迭代器向前移动 d 单位
void advance(IterT& iter, DistT d); // 如果 d < 0, 则向后移动
通常来说, iter += d 即可。但是其实不是。因为只有随机迭代器才支持算数运算。
而其他的迭代器种类,advance 只能一步步 ++ iter,走 d 步。
STL 库共有 5 种迭代器:
1. Input 迭代器
2. Output 迭代器
3. forward 迭代器
4. Bidirectional 迭代器
5. random 迭代器
对于这五种迭代器,STL 定义了五个专属的卷标结构(tag struct)加以标识。
struct input_iterator_tag { };
struct output_iterator_tag { };
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag { };
struct random_access_iterator_tag : public bidirectional_iterator_tag { };
他们的用途我在稍微会讲到。
现在回到 advance 函数。为了让 advance 满足不同迭代器的需要, 并且效率达到最高,
我们期望它以如下的方式定义:
template <typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
if ( iter is a random access iterator) {
iter += d; // 针对 random_access 迭代器采用迭代器算数运算,复杂度是 O(1)
}
else {
if (d > 0) { while (d--) ++iter; }
else { while (d++) --iter; }
}
}
难点在于如何判断 iter 是否是 random_access 迭代器这种类型?? 这里就是 traits 所做之事。
traits 技术让你能够 萃取 出迭代器的某些性质: 比如,迭代器类型,所指向元素的类型等等。
下面开始详细讲解 traits:
可以说它主要由两部分组成:
1. stl 中定义的 iterator_traits 的模板类:
template <typename IterT>
struct iterator_traits;
这个模板类里面包含了许多的 typedef, 其中有一个 typedef 名为 iterator_category,就是用来确认迭代器分类。
2. 要求用户自定义的迭代器类型中,必须定义一个 iterator_category 的 typedef.
举个例子:加入下面是 list 迭代器的定义,注意 list 是有双链表实现的,所以迭代器应该是 bidirectional 迭代器。
class iterator { // for list
public:
typedef bidirectional_iterator_tag iterator_category;
...
};
之前所说的 tag struct 就是用在这里,用来标识随机迭代器这种类型。
而 iterator_traits 里面有一个typedef 如下:
template<typename IterT>
struct iterator_traits {
typedef typename IterT::iterator_category iterator_category;
};
大家明白了吗? 这个其实就是 在迭代器中定义一个public 的 typedef, 告诉外界,我是一个什么迭代器类型。
然后 iterator_traits 仅仅是鹦鹉学舌般地响应 迭代器类的嵌套式 typedef 而已。
截取一种 STL 源码分析上的图:
大家先消化以下。。。。
。。。。。。。。。。。。。。。。。。。。。。。。。
二、
大家可能立刻想到一个问题,这对于 指针行不通。。因为我们不能在指针的内部定义一个 typedef.
怎么办?? 这时候,模板的偏特化技术就派上了用途。
我们可以提供一个 iterator_traits 的针对指针的偏特化版本:
template <typename IterT>
struct iterator_traits <IterT*>
{
typedef random_access_iterator_tag iterator_category; // 一般的指针是随机访问迭代器
....
}
讲了一堆难懂的技术,现在来说说具体是如何用的。。
给出一段 advance 函数的代码,但是会有编译问题并且效率不高。。因此,STL 其实并没有采用。
template<typename IterT, typename DistT>
void advance(IterT& iter, DistT d)
{
if (typeid(typename std::iterator_traits<IterT>::iterator_category)
== typeid(std::random_access_iterator_tag) )
....
}
typeid 是 C++ 中用于辨别类型的。。具体参考 C++ primer.
大家知道, IterT 的类型在编译期已经获知,所以 iterator_traits<IterT>::iterator_category
在编译期也可确定。但是 if 语句得到执行期才执行,所以只有到执行期才能判断 iter 是否是随机迭代器。
如何能够在编译期就是判断 iter 是否是随机迭代器呢??(效率更高)
我们需要一个“执行”于编译期的类似 if, else 的语句,
Bingo ! 重载(overloading)
直接上代码。。
template<typename IterT, typename DistT>
void advance(IterT iter, DistT d)
{
doAdvance(iter, d,
std::iterator_traits<IterT>::iterator_category());
// 用 iterator_category 定义一个临时对象,作为参数
} // for random_access iterator
template<typename IterT, typename DistT>
void doAdvance(IterT iter, DistT d,
std::random_access_iterator_tag)
{
iter += d;
} // overload
// for bidirectional iterators
template<typename IterT, typename DistT>
void doAdvance(IterT iter, DistT d,
std::bidirectional_iterator_tag)
{
if(d >= 0){
while(d--) ++iter;
}
else{
while(d++) --iter;
}
} // overload
// for input iterators
template<typename IterT, typename DistT>
void doAdvance(IterT iter, DistT d,
std::input_iterator_tag)
{
if(d < 0){
throw std::out_of_range("Negative distance");
}
while(d--) ++iter;
}
通过定义不同迭代器的 doAdvance 函数的重载版本,
参数唯一不同的是 之前说用来标识迭代器的 tag_struct:
input_iterator_tag
bidirectional_iterator_tag
random_access_iterator_tag
有没有觉得这种技术很酷??
利用重载函数完美地将执行期判断类型是否是某个迭代器,提前到了编译期,
极大地提高了速度。
参考书籍:
Stanley, B. Lippman, C++ Primer 第四版,
Scott, Meyers, Effective C++,
侯捷, STL 源码分析