前言
什么是迭代器
迭代器是一种抽象的设计概念,《Design Patterns》一书中对于 iterator 模式的定义如下:提供一种方法,使之能够依序巡访某个聚合物(容器)所含的各个元素,而又无需暴露该聚合物的内部表述方式。
为什么需要迭代器萃取
有时在我们使用迭代器的时候,很可能会用到其相应型别(associated type)。什么是相应型别,就是迭代器所指之物的类型、所属的类型(随机迭代器、单向双向、只读只写)。
如果我们想要以「迭代器所指之物的类型」为类型声明一个变量,该怎么办呢?
一种解决方法是:利用 function template 的参数推导(argument deducation)机制。
例如:
template <class I, class T>void func_impl(I iter, T t) {// 成功声明了迭代器所指之物类型的变量T tmp;}template <class I>void func(I iter) {func_impl(iter, *iter);}int main() {int num = 0;func(&num);}
但迭代器的型别不只是迭代器所指对象的型别,而且上述解法并不能用于所有情况,因此需要更加全面的解法。
比如上述解法就无法解决 value type 用于函数返回值的情况,毕竟推导的只是参数,无法推导返回值型别。
声明内嵌类型似乎是个很好的方法,像这样:
template <class T>struct MyIter {typedef T value_type;T* ptr;MyIter(T* p) {ptr = p;}T& operator*() {return *ptr; }};template <class I>typename I::valie_type func (I ite) {// typename I::valie_type 为返回值类型return *ite;}MyIter<int> ite(new int(1231));cout << func(ite) << endl;
此处 typename 的作用是告诉编译器这是一个类型,因为 I 是一个模板参数,在它被具现化之前编译器对它一无所知,也就是说编译器不知道 I::valie_type 是个类型或是成员函数等等。
更多关于 typename 的用法可以看这个链接:typename 的用法
还有一种情况是上述代码无法解决的,那就是不是所有的迭代器都是 class type,原生指针就不是。如果不是 class type 就无法为它定义内嵌型别,因此我们需要对原生指针作些特殊处理。
例如:
template <class I>struct iterator_traits {typedef typename I::value_type value_type;};template <class T>struct iterator_traits<T*> {typedef T value_type;};template <class T>struct iterator_traits<const T*> {typedef T value_type;};
此时,不管是 class type 类型的迭代器还是原生指针都可以处理了。
迭代器萃取,就是为我们榨取出迭代器的相应型别。当然,要使萃取有效的运行,每个迭代器都要自行以内嵌性别定义(nested typedef)的方式定义出相应型别。
最常用的迭代器型别有五种:value type,difference type,pointer,reference,iterator catagoly。
迭代萃取机 traits 会很忠实地将它们榨取出来:
template <class I>struct iterator_traits {typedef typename I::iterator_category iterator_category;typedef typename I::value_typevalue_type;typedef typename I::difference_typedifference_type;typedef typename I::pointerpointer;typedef typename I::referencereference;};
iterator_traits 必须针对传入型别为 point 及 point-to-const 者,设计特化版本。
value type
value type 是指迭代器所指对象的型别。
做法如上文所述。
difference type
difference type 用来表示两个迭代器之间的距离。对于连续空间的容器来说,头尾之间的距离就是最大容量,因此它也可以用来表示一个容器的最大容量。
如果一个泛型算法提供记数功能,例如 STL 的count()
,其返回值就必须使用迭代器的 difference type:
template<class I, class T>typename iterator_traits<I>::difference_type// 返回值类型,实际是 I::difference typecount(I first, I last, const T& value) {typename iterator_traits<I>::difference_type res = 0;for (; first != last; ++first) {if (*first == value) {++res;}}return res;}
针对相应型别 difference type,traits 的两个特化版本,以 C++ 内建的 ptrdiff_t 作为原生指针的 difference type。
template <class I>struct iterator_traits {typedef typename I::difference_type difference_type;};template <class T>struct iterator_traits<T*> {typedef ptrdiff_t difference_type;};template <class T>struct iterator_traits<const T*> {typedef ptrdiff_t difference_type;};
reference type
从迭代器所指之物的内容是否允许改变的角度来说,迭代器分为两种:不允许改变所指对象的内容者,称为 constant iterators;允许改变所指对象的内容者,称为 mutable iterators。当我们对允许改变内容的迭代器进行解引用操作时,获得的不应是一个右值,应该是一个左值,因为右值不允许赋值操作。
在 C++ 中,函数如果要传回左值,都是以引用的方式进行。所以当 p 是个 mutable iterators 时,如果其 value type 是 T,那么 *p 的型别不应该是 T,而应是 T&。同样的,如果 p 是一个 constant iterators,其 value type 是 T,那么 *p 的型别不应该是 const T,而应该是 const T&。实现将在下一部分给出。
point type
同样的问题也出现在指针这里,能否改变所指地址的内容,影响着取出的指针类型。
实现如下:
template <class I>struct iterator_traits {typedef typename I::pointer pointer;typedef typename I::referencereference;};template <class T>struct iterstor_traits<T*> {typedef T* pointer;typedef T& reference;};template <class T>struct iterstor_traits<const T*> {typedef const T*pointer;typedef const T& reference;};
iterator_category
根据移动特性与施行操作,迭代器被分为五类:
前三种支持operator++
,第四种再加上oprerator--
,最后一种则涵盖所有指针算术能力。
这些迭代器的分类与从属关系,可以用下图表示。直线与箭头并非表示继承关系,而是所谓概念与强化的关系。更类似于,随机迭代器是一个双向迭代器,双向迭代器也是一个单向迭代器的概念。
设计一个算法时,要尽可能针对图中某种迭代器提供一个明确定义,并针对更加强化的某种迭代器提供另一种定义,这样才能在不同情况下提供最大效率。
以 distance() 为例
distance()
函数用来计算两个迭代器之间的距离。针对不同的迭代器类型,它可以用不同的计算方式,带来不同的效率。
template <class InputIterator>inline iterator_traits<InputIterator>::difference_type__distance(InputIterator first, InputIterator last,input_iterator_tag) {iterator_traits<InputIterator>::iteratordifference_type n = 0;// 逐一累计距离while (first != last) {++first;++n;}return n;}template <class RandomAccessIterator>inline iterator_traits<RandomAccessIterator>::difference_type__distance(RandomAccessIterator first, RandomAccessIterator last,random_access_iterator_tag) {// 直接计算差距return last - first;}// InputIterator 命名规则:所能接受的最低阶迭代器类型template <class InputIterator>inline iterator_traits<InputIterator>::difference_typedistance(InputIterator first, InputIterator last) {typedef typename iterator_traits<InputIterator>::iterator_category category;return __distance(first, last, category());}