3.迭代器iterator解析_iterator迭代器详解

iterator的作用

在STL中，基于泛型思想，将数据容器（containers)和算法（algorithms）分开，独立设计，使用iterator作为中间件链接它们。在设计模型中，iterator模式指的是，提供一种方法，使其能够依序遍历某个容器所含的各个元素，而又无需暴露该容器内部实现。

下面是不同迭代器，作为中间件实现不同容器的查找功能：

#include <vector>
#include <list>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    const int arraySize = 7;
    int ia[arraySize] = {0, 1, 2, 3, 4, 5, 6};
    /*
    template <class InputIterator>
         vector (InputIterator first, InputIterator last,
                 const allocator_type& alloc = allocator_type());
    */
    vector<int> ivect(ia, ia + arraySize);
    list<int> ilist(ia, ia + arraySize);
    deque<int> ideque(ia, ia + arraySize);

    vector<int>::iterator it1 = find(ivect.begin(), ivect.end(), 4);
    if (it1!=ivect.end())
        cout << "4 not found." << endl;
    else
        cout << "4 found. " << *it1 << endl;

    list<int>::iterator it2 = find(ilist.begin(), ilist.end(), 6);
    if (it2!=ilist.end())
        cout << "6 not found." << endl;
    else
        cout << "6 found. " << *it2 << endl;

    deque<int>::iterator it3 = find(ideque.begin(), ideque.end(), 8);
    if (it3!=ideque.end())
        cout << "8 not found." << endl;
    else
        cout << "8 found. " << *it3 << endl;
}
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

iterator是什么？

迭代器iterator是一种行为类似指针的对象，是一种smart pointer，对应的其最重要的工作是dereference和member access，即对operator*和operator->运算符的重载工作。
以auto_ptr源码为例，演示如何实现operator*和operator->运算符重载，以及operator->的工作原理。

上述代码需要注意几个点：

• auto_ptr对象初始化传入的初值是指针对象；
• auto_ptr尖括号中填入的是用来初始化指针对象指向的数据类型，而非指针；
• operator->运算符实现的原理

以operator+运算符为例，当编译器遇到a+b时，会将其转换为a.operator+(b)，但是operator->成员访问运算符的返回值为指针，与指针所指对象的成员之间没有任何联系，那它是如何实现成员调用的呢？
运算符重载通常可以通过全局函数和成员函数两种方式实现，但是在重载operator->时，只能使用成员函数，没有输入参数，当返回值为一个指针，那么就将右操作数作为这个指针指向类型的成员进行访问；如果返回值为另一个object，则继续调用这个object的operator->，直到返回一个指针为止，然后按照第一种情况处理。

为了解迭代器iterator是如何实现的，接下来，我们为list设计一个专属的迭代器，具体过程如下：

1. 设计基础数据结构：list节点；
   
2. 设计list容器：提供各种方法对数据进行增删改查操作；
   
3. 设计list专属迭代器：用于遍历容器中所有的元素；
   
4. 使用算法：以iterator作为中间件连接算法find和list容器；
   
   
   在设计list节点的迭代器时，需要对list节点的实现细节有全面的了解，因此，每一种STL容器都提供有专属迭代器。
   

iterator traits

在算法中运用迭代器时，需要得到迭代器相对应的型别associated type信息。STL通过在迭代器中内嵌型别信息，对于原生指针采用template partial specialization定义相应的型别信息，然后输入到iterator traits中得到迭代器或者指针对应的型别信息。

template partial specialization指的是，如果class template
拥有一个（包含一个）以上的template参数，就可以针对其中某个（或数个，但非全部）template参数进行特化工作。
《泛型思维》一书对partial specialization的定义是：针对（任何）template参数更进一步的条件限制所设计出来的特化版本。

template <typename T>
class C {...};			// 这个泛化版本允许T为任何型别

// 偏特化
template <typename T>
class C<T*> {...};		// 这个特化版本仅适用于"T为原生指针"的情况
                    	// "T为原生指针"便是"T 为任何型别"的一个更进一步的条件限制
1
2
3
4
5
6
7

如下图所示，iterator traits的功能是萃取得到各个迭代器的型别信息，traits接收3种类型输入：

• 各种迭代器
• 原生指针
• 原生常量指针
  

与之对应的，iterator traits的实现也有3种不同形式，分别如下：

// 萃取机 traits
template <class _Iterator>
struct iterator_traits {
  typedef typename _Iterator::iterator_category iterator_category;
  typedef typename _Iterator::value_type        value_type;
  typedef typename _Iterator::difference_type   difference_type;
  typedef typename _Iterator::pointer           pointer;
  typedef typename _Iterator::reference         reference;
};

// 原生指针的traits 偏特化
template <class _Tp>
struct iterator_traits<_Tp*> {
  typedef random_access_iterator_tag iterator_category;
  typedef _Tp                         value_type;
  typedef ptrdiff_t                   difference_type;
  typedef _Tp*                        pointer;
  typedef _Tp&                        reference;
};

// 原生常量指针 pointer-to-const 的traits 偏特化
template <class _Tp>
struct iterator_traits<const _Tp*> {
  typedef random_access_iterator_tag iterator_category;
  typedef _Tp                         value_type;
  typedef ptrdiff_t                   difference_type;
  typedef const _Tp*                  pointer;
  typedef const _Tp&                  reference;
};
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

迭代器的型别信息

为了能使iterator traits能有效运作，每一个迭代器都必须以内嵌型别定义nested typedef的方式定义出相应型别associated types。迭代器最常用到的型别总共有五种：value type, difference type, pointer, reference, iterator catagory。

value type

value type，指的是迭代器所指对象的数据类型，如同之前所描述的一样，迭代器本质上是一个smart pointer，auto_ptr<string> ps (new string("jjjj"));，其中所指对象的数据类型为string。

difference type

difference type用来表示两个迭代器之间的距离，且difference type的取值范围必须能用来表示容器的最大容量，通常使用ptrdiff_t做为difference type，而ptrdiff_t是long int的别名。
在STL的算法中count()函数，其返回值必须必须使用迭代器的difference type。

template <class I, class T>
typename iterator_traits<T>::diiference_type  // 函数返回值类型
count (I first, I last, const T& value)
{
    typename iterator_traits<T>::diiference_type n = 0;
    for(; first != last; ++first)
    {
        if(*first == value)
            ++n;
    }
    return n;
}
1
2
3
4
5
6
7
8
9
10
11
12

reference type

迭代器所指之物的引用类型；

pointer type

指向迭代器所指之物的指针类型；

iterator category

迭代器的iterator category可分为五类：

• Input Iterator：这种迭代器所指的对象，不允许外界改变，只读；
• Output Iterator：只写；
• Forward Iterator：允许对迭代器所指的对象进行读写，且能在迭代器做形成的区间内进行单向移动；
• Bidirectional iterator：与Forward Iterator功能一样，但是可以进行双向移动；
• Random Access Iterator：支持所有指针算术能力，包括operator++，operator--，p+n，p-n，p[n]，p1-p2，p1<p2；

五种迭代器类型class type的定义如下：

// 五种迭代器类型
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 {};
1
2
3
4
5
6

Advance函数

由于上述iterator category的行为限制不同，为了效率，在设计算法时，应该尽可能为某种迭代器提供一个明确定义，并针对更强化的某种迭代器提供另一种定义。

以advance函数为例，该函数输入两个参数，迭代器p和数值n，功能是将迭代器p向前移动n个距离。按照iterator category不同，设计了3份函数定义。

template <class InputIterator, class Distance>
void advance_II(InputIterator& p, Distance n)			// for Input Iterator
{
    // 单向移动
    for(; n>0; --n)
        ++p;
}

template <class BidirectionalIterator, class Distance>
void advance_BI(BidirectionalIterator& p, Distance n)	// for Bidirectional Iterator
{
    // 双向移动
    if(n >=0)
        for(; n>0; --n, ++p);
    else
        for(; n<0; ++n, --p);
}
template <class RandomAccessIterator, class Distance>
void advance_II(RandomAccessIterator& p, Distance n)			// for RandomAccess Iterator
{
	// 双向, 跳跃
    p += n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

当使用advance函数时，可以根据输出的迭代器，结合iterator traits得到iterator category，然后调用对应的函数。但是这种在执行时期才确定使用哪个版本，会影响程序效率，因此，需要通过重载函数机制，在编译期就选择正确的版本。

template <class _InputIter, class _Distance>
inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) {
  while (__n--) ++__i;
}

template <class _BidirectionalIterator, class _Distance>
inline void __advance(_BidirectionalIterator& __i, _Distance __n, 
                      bidirectional_iterator_tag) {
  if (__n >= 0)
    while (__n--) ++__i;
  else
    while (__n++) --__i;
}

template <class _RandomAccessIterator, class _Distance>
inline void __advance(_RandomAccessIterator& __i, _Distance __n, 
                      random_access_iterator_tag) {
  __i += __n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

通过在函数参数列表中，加入第三参数，形成函数重载，然后通过如下统一的接口进行调用。

template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&)
{
    typedef typename iterator_traits<Iterator>::iterator_category category;
    return category(); // 临时对象
}
template <class InputIterator, class Distance>
void advance(InputIterator& p, Distance n)			// 函数统一接口
{
	__advance(p, n, iterator_category(p));
}
1
2
3
4
5
6
7
8
9
10
11
12

因此，iterator category对算法设计优化很重要，也证明了向traits中增加iterator category的必要性。

使用继承消除传递调用

上述内容还存在一个疑点，输入iterator类型应该有四种，但是上面__advance函数在实现时，只实现了三种，而对应ForwardIterator类型没有处理，那是不是当输入ForwardIterator类型时，advance函数就不起作用了？不是的，由于iterator category在定义class type时，运用了继承机制，使得当输入ForwardIterator类型时，找不到该类型实现时，会转而调用InputIterator的实现。
下面通过一个小例子，模拟继承机制下，函数的调用情况：

#include <iostream>
using namespace std;

struct B { // 类比InputIterator
};
struct D1 : public B { // 类比ForwardIterator
};
struct D2 : public D1 { // 类比BidirectionalIterator
};

template <class I> 
void func(I& p, B) {
    cout << "B version" << endl;
}

template <class I> 
void func(I& p, D2) {
    cout << "D2 version" << endl;
}

int main() {
    int * p;
    func(p, B());		// B()临时对象, 参数类型完全吻合，输出"B version"
    func(p, D1());		// 参数类型不吻合，因继承关系而自动传递调用输出"B version"
    func(p, D2());		// 输出"D2 version"
}
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

distance函数

distance函数输入两个迭代器，计算它们之间的距离。针对不同的迭代器类型，使用了不同计算方式。由于迭代器类型之间存在着继承关系，使得当客端输入为ForwardIterator或者Bidirectional iterator时都会调用Input Iterator版本的__distance函数。

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;
}
// distance接口
template <class _InputIterator, class _Distance>
inline void distance(_InputIterator __first, 
                     _InputIterator __last, _Distance& __n)
{
  __distance(__first, __last, __n, iterator_category(__first));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

自定义iterator

对于需要自定义迭代器的需求，STL提供了一个iterator class如下，在设计新的迭代器时只需要继承它，就能保证迭代器符合STL所需的规范。

// 自行开发迭代最好继承下面的iterator
#ifdef __STL_USE_NAMESPACES
template <class _Category, class _Tp, class _Distance = ptrdiff_t,
          class _Pointer = _Tp*, class _Reference = _Tp&>
struct iterator {
  typedef _Category  iterator_category;
  typedef _Tp        value_type;
  typedef _Distance  difference_type;
  typedef _Pointer   pointer;
  typedef _Reference reference;
};
#endif /* __STL_USE_NAMESPACES */
1
2
3
4
5
6
7
8
9
10
11
12

在继承时，由于后三个参数都有默认值，因此只需要提供前两个参数即可，具体可以参考如下例子。

// std::iterator example
#include <iostream>     // std::cout
#include <iterator>     // std::iterator, std::input_iterator_tag

class MyIterator : public std::iterator<std::input_iterator_tag, int>
{
  int* p;
public:
  MyIterator(int* x) :p(x) {}                                 // 构造函数
  MyIterator(const MyIterator& mit) : p(mit.p) {}
  MyIterator& operator++() {++p;return *this;}
  MyIterator operator++(int) {MyIterator tmp(*this); operator++(); return tmp;}
  bool operator==(const MyIterator& rhs) const {return p==rhs.p;}
  bool operator!=(const MyIterator& rhs) const {return p!=rhs.p;}
  int& operator*() {return *p;}
};

int main () {
  int numbers[]={10,20,30,40,50};
  MyIterator from(numbers);   
  MyIterator until(numbers+5);      // end()
  for (MyIterator it=from; it!=until; it++)
    std::cout << *it << ' ';
  std::cout << '\n';

  return 0;
}
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

总结

在STL中，容器和算法被分开设计，使用迭代器作为两者之间的中间件。通过auto_ptr代码，可以知道迭代器本质上是一个smart pointer，主要工作是operator*和operator->运算符重载，其中还分析了operator->的工作原理，借鉴auto_ptr的实现，设计了list单链表的迭代器。
由于算法可能需要知道迭代器的型别消息，因此，迭代器需要以内嵌型别定义nested typedef的方式定义五种常见的型别信息，结合iterator traits萃取得到迭代器的型别信息。重点介绍iterator category型别信息对算法优化设计的影响，以及继承机制下，函数调用的自动传递特性。
最后，描述了如何继承STL提供的iterator class，自定义新的iterator。