存在的问题
上一篇中我们最终实现了find的算法：
template <class T, class Iter>
Iter find(Iter start, Iter end, const T& x)
{
Iter p = start;
while( p != end && *p != x) {
p++;
}
return p;
}
这个算法针对Iter进行了一些假设：
- 支持
operator++。 - 支持
operator* - 支持
operator!=。
也就是说凡事支持这些操作的Iter都可以应用我们的算法find。但是Iter还可以应用于其他算法吗？有的算法可能针对Iter的假设跟find的假设是不一样的。
例如，我们需要一个reverse的算法：
template <class Iter, class T>
void reverse(Iter start, Iter end)
{
while( start < end ) {
T t = *start;
--end;
*start = *end;
*end = t;
++start;
}
return p;
}
这个算法对于Iter提出了比find更多的假设：
- 支持
operator<进行比较。 - 支持
operator--向前移动。 - 必须保证
operator*返回的是一个左值，否则将不能进行赋值。
从上面的例子可以很明显的看出Iter这个我们提出的泛型并不能满足现在reverse的要求。如果我们的目标是提供一整套的算法库，那我们可能需要针对每一种算法都需要定制化一套Iter，这是无法忍受的。
所以我们需要对算法的需求进行分类处理。找到一套能够适用于某个算法集的需求，以及另外一套适合另外的算法集。所以我们得到了下面针对迭代器的分类。
输入迭代器
满足：
- 支持
operator*可以读取内容（不一定支持写入） - 支持
operator++和operator++(int)指向下一个元素。 - 支持
operator!=和operator==进行边界判断。
这些条件的可以被称为：输入迭代器。
注意这里说的输入迭代器并不是指某个类或者对象。相反它表示的是一种概念：任何满足上面需求的完整类型集合中任意成员。可以把它当作是迭代器的一种划分：category。
输出迭代器
输出迭代器与输入迭代器的唯一区别就是: operator*的行为。输出迭代器operator*应该返回一个允许我们修改的左值。当然也可以有迭代器既满足输出迭代器，有满足输出迭代器，这时这个类需要对operator*的返回类型进行重载。但是c++的函数重载是不支持返回类型不同的，所以我们采用const重载进行区分。
我们可以使用输入迭代器和输出迭代器实现copy的泛型：
template <class In, class Out>
void copy(In start, In end, Out result)
{
while (start != end) {
*result = *start;
++result;
++start;
}
}
前向迭代器
我们已经有了输入迭代器，输出迭代器，为什么还需要一个前向迭代器呢？
前向迭代器是为了：在遍历过程中，修改元素的值，但是一旦遍历过了这个元素就不能再次访问了。即：前向迭代器的operator*需要返回一个可读可写的类型。
双向迭代器
我们reverse算法的需求还没有得到满足，即：operator--，向后移动的需求。所以我们需要在增加一种迭代器，它除了支持前向迭代器的需求还满足了operator--的需求。
随机存取迭代器
假设p指向序列的起始位置，如果我们需要它指向第1000个元素应该怎么处理呢？我们现在拥有的迭代器都只支持operator++的操作，让用户使用循环执行1000次++p是不可接受的。
为了满足这个需求，我们需要另外一种迭代器类型：随机存取迭代器。除了支持双向迭代器的需求以外还支持例如：operator+=,operator-=,operator[]的操作。可以让我们随机访问。
是继承吗？
我们上面描述了5种迭代器，那么他们之间有继承关系吗？
这5种迭代器描述了满足或者不应该满足的需求集合，不能使用继承来描述他们。他们是针对迭代器的不同划分。一种概念上的继承。
llvm-iterator
llvm项目使用category来区分不同的迭代器类型：
struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {};
struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {};
struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {};
struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {};
struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {};
可以看出这里的tag都是空的struct，说明他们只是一种划分。
在判断有没有迭代器类型时，llvm采用了下面的代码：
struct __has_iterator_category
{
private:
struct __two {char __lx; char __lxx;};
template <class _Up> static __two __test(...);
template <class _Up> static char __test(typename _Up::iterator_category* = 0);
public:
static const bool value = sizeof(__test<_Tp>(0)) == 1;
};
通过__test函数的重载，然后通过sizeof判断是使用了哪个重载，进而确定有没有iterator_category*类型的参数。
