STL源码分析《4》----Traits技术

在 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 源码分析上的图:

STL源码分析《4》----Traits技术

大家先消化以下。。。。

。。。。。。。。。。。。。。。。。。。。。。。。。

二、

大家可能立刻想到一个问题,这对于 指针行不通。。因为我们不能在指针的内部定义一个 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 源码分析

上一篇:STL源码分析《3》----辅助空间不足时,如何进行归并排序


下一篇:STL 源码分析《2》----nth_element() 使用与源码分析