SGISTL源码探究-迭代器的类型

前言

迭代器主要用于将数据结构与算法粘合在一起。当我们平时使用迭代器的时候,主要的操作无非是使用operator *以及operator ->,之所以它表现的像指针,就是因为对这两个操作符进行了重载。而不同的容器因为其存储的数据结构不同,比如访问其成员时,若是单链表,则不支持向前遍历,因此缺少跟其他迭代器的一些功能;而一些算法也会根据数据结构能否支持某种操作(比如随机访问)来选择最有效率的做法。

迭代器的五种类型

根据这些原因,每个容器都有自己的迭代器来满足自己的使用并且将迭代器分为五类。
分别是:

• Input Iterator : 该类型迭代器指向的对象只读(基类)
• Output Iterator : 该类型迭代器指向的对象只写(基类)
• ForWard Iterator : 可读可写,但是同样只支持简单的向前操作,不能后退(多重继承自前两个类)
• Bidirectional Iterator : 在Forward Iterator的基础上,支持了前后移动(单继承自Forward Iterator)
• Random Access Iterator : 这种类型最为*,可以随机访问/修改元素,支持指针的所有算术操作。(单继承自Bidirectional Iterator)

将这五种类型设置为类的其中一个好处就是一个Random Access Iterator类型的迭代器同样也可以用于支持Bidirectional Iterator的算法。

我们可以先来看看根据迭代器类型的不同区分的不同的情况的例子:

distance

该函数用于计算传入的first和last迭代器之间的距离

//如果迭代器类型是Random以下的,都调用这个__distance
//采用循环遍历的方式来计算first到last的距离
template <class InputIterator, class Distance>
inline void __distance(InputIterator first, InputIterator last, Distance& n, input_iterator_tag) {
  while(first != last) { ++first; ++n;}
}
//如果迭代器是RandomAccessIterator,则调用效率最佳的__distance
//直接用last-first
template <class RandomAccessIterator, class Distance>
inline void __distance(RandomAccessIterator first, RandomAccessIterator last, Distance& n, random_access_iterator_tag) {
  n += last - first;
}
//根据迭代器的类型不同,调用不同的__distance
template <class
 InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n) {
  __distance(first, last, n, iterator_category(first));
}

再看到distance函数,它根据iterator_category(first)的返回值不同而调用不同的__distance。看起来似乎iterator_category可以判断当前迭代器的类型。

iterator_category到底是什么,等下我们再来分析。

深入源码

知道了迭代器的五种类型,下面我们直接来看它的源码是如何实现的(没什么比看源码来的直接)

/* 首先这五种类型的继承关系一目了然
 * 其中没有任何成员,全是空类
 * 这样做可以很方便的利用类之间的转换来达到类型转换的效果
 */
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 {};
/* 可以看到它们都统一了:
 * iterator_category
 * value_type
 * difference_type
 * pointer
 * reference
 * 这5个统一的迭代器相应型别
 */
template <class T, class Distance> struct input_iterator {
  typedef input_iterator_tag iterator_category;
  typedef T                  value_type;
  typedef Distance           difference_type;
  typedef T*                 pointer;
  typedef T&                 reference;
};

struct output_iterator {
  typedef output_iterator_tag iterator_category;
  typedef void                value_type;
  typedef void                difference_type;
  typedef void                pointer;
  typedef void                reference;
};

template <class T, class Distance> struct forward_iterator {
  typedef forward_iterator_tag iterator_category;
  typedef T                    value_type;
  typedef Distance             difference_type;
  typedef T*                   pointer;
  typedef T&                   reference;
};


template <class T, class Distance> struct bidirectional_iterator {
  typedef bidirectional_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef Distance                   difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

template <class T, class Distance> struct random_access_iterator {
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef Distance                   difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

可以看到除了Output Iterator比较特殊,其余的迭代器类型都将iterator_category定义为各自的类型,而其他的都一致。
这里简单的说明一下迭代器类型中的这五个不同的迭代器相应型别代表什么含义:

• iterator_category:用于获取到迭代器的类型,对应上面的例子中的iterator_category()可以判断出传入的迭代器的类型
• value_type:代表迭代器指向对象的数据类型
• difference_type:代表两个迭代器之间的距离
• pointer:代表对象T的指针
• reference:顾名思义,即代表对象T的引用

除了认识到迭代器的不同类型的对象有什么不同之外,还可能会对它们统一都提供的这五种相应型别产生疑惑,我们将在后面进行具体的分析。

小结

在本小节中我们了解了迭代器的五种类型,并引出了迭代器的五种相应型别,但是在正式分析这五种相应型别之前,我们需要先对traits编程技法有个了解。