迭代器

迭代器是将算法和容器两个独立的泛型进行调和的一个接口. 使我们不需要关系中间的转化是怎么样的就都能直接使用迭代器进行数据访问. 而迭代器最重要的就是对operator *和operator->进行重载, 使它表现的像一个指针.

类型

迭代器根据移动特性和实施操作被分为5类

  1. input iterator(输入迭代器) : 迭代器所指的内容不能被修改, 只读且只能执行一次读操作.
  2. output iterator(输出迭代器) : 只写并且一次只能执行一次写操作.
  3. forward iterator(正向迭代器) : 支持读写操作且支持多次读写操作.
  4. bidirectional iterator(双向迭代器) : 支持双向的移动且支持多次读写操作.
  5. random access iterator(随即访问迭代器) : 支持双向移动且支持多次读写操作. p+n, p-n等.

源码分析

category的五类迭代器以及继承关系

1
2
3
4
5
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 {};

这五个类都是空类, 只是为了之后调用时通过类选择不同的重载函数. 继承是为了可以使用传递调用，当不存在某种迭代器类型匹配时编译器会依据继承层次向上查找进行传递, 就可以通过继承关系来决定选择最优的调用. 我们通过用distance来讲最优.

distance是用于计算连个迭代器之间的距离, 因为重载就可以通过不同的迭代器类型选择不同的函数来提高效率.

这里distance的iterator_category函数是每个迭代器自己定义的, 它能通过first参数推断出是哪一类的迭代器从而选择调用哪一个函数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <class InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n) 
{
  	__distance(first, last, n, iterator_category(first));
}
	
template <class InputIterator, class Distance>
inline void __distance(InputIterator first, InputIterator last, Distance& n, 
                       input_iterator_tag) 
{
  	while (first != last) 
    { ++first; ++n; }
}

template <class RandomAccessIterator, class Distance>
inline void __distance(RandomAccessIterator first, RandomAccessIterator last, 
                       Distance& n, random_access_iterator_tag) 
{
  	n += last - first;
}

五类迭代器源码

五类迭代器的结构体, 可以看出来每个类都定义了相同的变量名. 但是每个名的类型不一定一样, 提供统一的名是为了traits进行类型萃取. 每个类的iterator_category都是代表了不同的迭代器, 通过它来选择该迭代器执行的函数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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;
};

iterator_category判断传入迭代器的类型

1
2
3
4
5
6
template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
  typedef typename iterator_traits<Iterator>::iterator_category category;
  return category();
}