概要

STL的中心思想在于把数据（容器）和算法分离开，彼此之间没有关系，独立设计，都不必关心彼此的实现细节，但是那我们就需要用什么东西去使这两者能够结合起来，这就是迭代器的意义。

以 C++14 的 STL 源码为例，其线性查找函数如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/// This is an overload used by find algos for the Input Iterator case.
template<typename _InputIterator, typename _Predicate>
  inline _InputIterator
  __find_if(_InputIterator __first, _InputIterator __last,
      _Predicate __pred, input_iterator_tag)
  {
    while (__first != __last && !__pred(__first))
 ++__first;
    return __first;
  }

/**
 * 源码剖析
 * 这是其find函数最底层实现的一个（有多个重载函数）
 * 可以看到，此处的输入的参数是 __first，__last，__pred，
 * 分别代表查找段的开头，结尾，需要查找的数据（严格来说不是数据本身）
 * 虽然不知道_InputIterator本身具体是什么（指针？类？），但是我们并不关心它是什么
 * 拿来用就行了，该做的++操作什么的还是照常来，（具体来说因为迭代器内部已经有实现了）
 * 此处__pred(__first)是用来判断__first指向的值是否等于__pred指向的值
 * input_iterator_tag用来表明迭代的是该类型的
 * 简单来说，iterator本身是有不同类型的，
 * 然后针对不同的iterator类型通过函数重载设计了当前类型下最优的算法
 */

这段代码是比较有代表性的，我们完全不知道容器内部的构造，但是能够通过迭代器对其元素进行访问。

基本概念

迭代器（iterator）是一种行为类似于指针的东西（对象，或者本身就是原生指针）。

那因此想到指针最重要的就是元素访问，所以需要对 * 运算符进行重载，再就是成员访问，因此还需要对 -> 运算符进行重载