[原创]学STL Iterator,traits设计笔记

类别:编程语言 点击:0 评论:0 推荐:

学STL Iterator,traits笔记

最近看侯杰老师的《STL源码剖析》有一点收获,特把我对STL iterator设计的认识草草记录下来,大部分内容来自那本书(看原书更好)。欢迎大家跟我讨论,里面也有问题希望您能提供宝贵看法!

一. Iterator认识
如果需要构造一组通用容器,提供一套统一的算法,构造底层数据结构类库,iterator的设计无疑是非常重要的。iterator可以方便容器元素的遍历,提供算法的统一参数接口。怎么说?首先,让我们考虑一个算法。
Template <class T> ptrdiff_t
distance(T p1, T p2)
{
  //计算p1和p2之间的距离
}
显然这个函数是想计算两个“位置”之间距离。这里表示“位置”的类型T,可以是指向数组中某个元素的(原生)指针,可以是指向链表节点的指针,也可以是用来记录位置的任何对象(例如我们要谈的iterator)。不管这两个位置是对应在数组,vector,链表或是其他任何容器,我们当然希望设计好的类库中最好只要一个这样的distance函数,而不需要每种容器都有不同的“位置”记录方式,从而导致需要很多个这样的distance算法。对,我们完全可以抽象出一种表示“位置”的概念,它像游标,像智能的指针,可以方便的遍历容器中的元素,记录位置,而不用管你作用的是什么类型的容器,这就是现在被容器设计者普遍接受的iterator概念。




二. STL iterator的设计:
为什么不用继承构造iterator?
容器抽象出5种iterator 类型,input<--forward<--bidrectional<--random access iterator加上output iterator,我们能不能通过refinement关系设计出具有继承关系的几个iterator类?然后各个容器的iterator类去继承这些基类。那么上面的disatance函数可以设计两个版本
ptrdiff_t distance(InputIterator p1, InputIterator p2)
{
 //InputIterator只能一个一个前进,例如链表
  ptrdiff_t n=0;
  while(p1 != p2)
  {
   ++p1; ++n;   
  }
  return n;
}

ptrdiff_t distance(RandomAccessIterator p1, RandomAccessIterator p2)
{
 //RandomAccessIterator可以直接计算差距,例如数组,vector等
 return p2-p1;
}

这样看来是可行的对吗?但为什么STL不采用这种方式呢?(各位帮我想想啊,我实在是菜,想不出很好的理由啊)我所能想到的有:iterator可以是原生指针的类型,而原生指针是不会继承InputIterator基类的。(是不是还有效率问题?)

不讨论STL为什么不这么作,还是看看它漂亮的处理方法吧:先提醒你,它用的是函数模板(function template)的参数推导机制来确定函数返回值和参数类型的。

(1)  通过不同的iterator概念,先作几个表明iterator类型的tag类。input_iterator_tag<--forward_iterator_tag<--bidrectonal_iterator_tag<--random_access_iterator_tag。还有output_iterator_tag,这几个类都是空的,前面4个有继承关系。

(2)  STL设计的iterator类都需要typedef一个重要的类型iterator_category用来表明这个iterator是什么类型的iterator,它必须是上面tag类中的一个。例如list<T>的iterator类有:
    typedef bidrectonal_iterator_tag iterator_category;
   
    另外需要有一个value_type类型表明iterator是指向什么类型的元素。例如list<T>的iterator类有:
    typedef T value_type;

(3)  设计iterator_traits<class Iterator>类,这个类的作用是可以提取出模板参数Iterator类的类型。也是通过typedef实现的。如下:
template <class Iterator>
struct iterator_traits {
  typedef typename Iterator::iterator_category iterator_category;
  typedef typename Iterator::value_type        value_type;
  //.....
};

本来第二步中,我们设计的iterator类已经可以通过typedef别名来标志类型了,为什么要这层中间转换?原因是通常我们可以写Iterator::iterator_category作为一个typename,但如果Iterator是一个原生指针T*,我们写T*::iterator_category就得不到啦。利用partial specialization(模板偏特化)技术,可以通过中间层iterator_traits自己指定并得到原生指针的iterator_category类型,代码如下。(这么复杂的编译技术,真不知他们咋整的...吾辈只能望洋兴叹55)

template <class T>
struct iterator_traits<T*> {
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  //........
};

(4)  设想要设计一个算法template <class Iterator> RET_TYPE gen_fun(Iterator p1, Iterator p2, ...)。
一般这么处理:
template <class Iterator> RET_TYPE gen_fun(Iterator p1, Iterator p2, ...)
{
    typedef iterator_traits<Iterator>::iterator_category category;   
    typedef iterator_traits<Iterator>::value_type type;  //这个type用于实际运算中得知iterator指向的对象(*运算符返回类型)
   __gen_fun(Iterator p1, Iterator p2, ..., category());
}

category()构造一个iterator_tag类型的临时变量,该临时变量只用于区分调用函数,不参与实际算法实现。具体实现方法如下:(注意最后的参数不用变量名)

template <class Iterator> RET_TYPE __gen_fun(Iterator p1, Iterator p2, ..., input_iterator_tag)
{
   //input_iterator类型的实际实现方法
   //并且由于tag类继承机制,forward_iterator类型也会调用本方法
}
 
template <class Iterator> RET_TYPE __gen_fun(Iterator p1, Iterator p2, ..., bidrectonal_iterator_tag)
{
   //bidrectonal_iterator类型的实际实现方法
}

template <class Iterator> RET_TYPE __gen_fun(Iterator p1, Iterator p2, ..., random_access_iterator_tag)
{
   //random_access_iterator类型的实际实现方法
}

这样通过定义iterator tag和函数模板的参数推导机制,就实现了参数类型识别,达到了构造继承关系的iterator类实现的功能。并且没有继承要求那么严格,而且typedef是在编译时候完成的工作,丝毫不影响程序运行速度。如果增加iterator中typedef的类型,如pointer等,可以增强参数类型识别的功能。

另外需要提醒的是,在STL代码中,如果是random_access_iterator类型的方法,它通常写
template <class RandomAccessIterator> RET_TYPE __gen_fun(RandomAccessIterator p1, RandomAccessIterator p2, ..., random_access_iterator_tag)
是input_iterator类型的方法,它通常写
template <class InputIterator> RET_TYPE __gen_fun(InputIterator p1, InputIterator p2, ..., input_iterator_tag)
但是,别被这里的RandomAccessIterator和InputIterator迷惑了,它们只是模板参数而已,并没有继承关系,也不存在这样的类!(我就被这个迷惑了好久:( )也不是我开头提的构造一组继承关系的Iterator类。模板参数写成RandomAccessIterator并不能表示该RandomAccessIterator类型就是random_access_iterator的,它写成T,Type,Iter都没有关系。只有通过iterator_traits得到iterator_tag才能表明iterator的真正类型。我想它那样写,只是为了提醒你调用函数的iterator类型吧。



三. 最后看看开头提的distance()算法实际实现

template <class Iterator> inline
 typename iterator_traits<Iterator>::iterator_category
  iterator_category(const Iterator&) 
  //提取Iterator的iterator_category类型
{
  typedef typename iterator_traits<Iterator>::iterator_category category;
  return category();
}


template <class InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n) 
{
  __distance(first, last, n, iterator_category(first));
  //根据提取的iterator_category类型选择实际执行函数
  //Distance是通过引用传递,相当于函数返回值
}


template <class InputIterator, class Distance>
inline void __distance(InputIterator first, InputIterator last, Distance& n,
                       input_iterator_tag)
{
  //input_iterator类型的实现,根据input_iterator_tag的继承关系,forward_iterator
  //和bidrectonal_iterator也会调用此实现函数。
  while (first != last) { ++first; ++n; }
}

template <class RandomAccessIterator, class Distance>
inline void __distance(RandomAccessIterator first, RandomAccessIterator last,
                       Distance& n, random_access_iterator_tag)
{
  //random_access_iterator类型的实现
  n += last - first;
}

                                                                              2004.11.10

 

 

 

 

 

 

 

 

 

本文地址:http://com.8s8s.com/it/it25603.htm