动机

标准的迭代器分类和要求存在缺陷，因为它们使用单一的概念层次结构来处理两个正交的问题：*迭代器遍历*和*数值访问*。结果是，许多以迭代器分类来表达要求的算法过于严格。此外，许多现实世界中的迭代器无法被准确分类。例如，具有随机访问遍历能力的基于代理（proxy-based）的迭代器，在法律上只能被归类为“输入迭代器”，因此泛型算法无法利用其随机访问能力。当前的迭代器概念层次结构倾向于迭代器遍历（因此有了这些分类名称），而涉及数值访问的要求则在多处混入。下表总结了当前迭代器分类中的数值访问要求。

由于迭代器遍历和数值访问在单一层次结构中混在一起，许多有用的迭代器无法得到适当的分类。例如：vector<bool>::iterator几乎是一个随机访问迭代器，但返回类型不是bool&（参见 issue 96 和 Herb Sutter 的论文 J16/99-0008 = WG21 N1185）。因此，vector<bool>的迭代器仅满足输入迭代器和输出迭代器的要求。这非常不直观，以至于 C++ 标准在这一点上自相矛盾。在 23.2.4/1 段落中指出，vector是一个支持随机访问迭代器的序列。

另一个难以分类的迭代器是变换迭代器（transform iterator），这是一种将一元函数对象应用于某些底层迭代器解引用后的值的适配器（参见 transform_iterator）。对于诸如times之类的一元函数，函数对象的返回类型operator*的返回类型显然需要是函数对象的result_type通常不是引用。因为随机访问迭代器被要求从operator*返回左值，如果你用变换迭代器包装int*，你得到的不是预期的随机访问迭代器，而是输入迭代器。

第三个例子可以在 Boost Graph Library 的顶点（vertex）和边（edge）迭代器中找到。这些迭代器返回顶点和边描述符，它们是即时创建的轻量级句柄。它们必须按值返回。结果是，它们当前的标注迭代器分类是input_iterator_tag，这意味着严格来说，您不能将这些迭代器与像min_element()。作为临时解决方案，引入了 Multi-Pass Input Iterator（多遍输入迭代器）概念来描述顶点和边描述符，但正如该概念的设计说明所建议的那样，需要更好的解决方案。

总之，许多有用的迭代器不适合当前的标准迭代器类别。其结果是出现了以下不良情况：

• 迭代器经常被错误分类。
• 算法要求比必要的更严格，因为它们无法将对随机访问或双向遍历的需求与对真实引用返回类型的需求分开。

对标准的影响

针对 TR1 的这一提案是一个纯粹的扩展。此外，新的迭代器概念与旧的迭代器要求向后兼容，且旧的迭代器与新的迭代器概念向前兼容。也就是说，满足旧要求的迭代器也满足新系统中相应的概念，而符合新概念模型的迭代器将自动满足相应的旧要求。

设计

迭代器要求将被分为两组。一组概念处理数值访问的语法和语义

• 可读迭代器
• 可写迭代器
• 可交换迭代器
• 左值迭代器

访问概念描述了与operator*andoperator->相关的要求，包括value_type, reference和pointer等关联类型。

另一组概念处理遍历

• 可增量迭代器
• 单次遍历迭代器
• 前向遍历迭代器
• 双向遍历迭代器
• 随机访问遍历迭代器

遍历概念的精化 (refinement) 关系如下图所示。

除了迭代器移动操作（例如operator++）之外，遍历概念还包括对位置比较（例如operator==andoperator<）的要求。将概念细分为“可增量 (Incrementable)”和“单遍 (Single Pass)”的原因是为了提供与原始输入和输出迭代器要求完全匹配的概念。

本提案还包括一个用于指定迭代器何时与另一个迭代器“可互操作”的概念，其含义是int*与int const*.

• 可互操作迭代器 (Interoperable Iterators)

新旧迭代器概念之间的关系见下图。

与旧的迭代器要求类似，我们提供了用于基于遍历概念进行派发 (dispatching) 的标签。这些标签通过继承关联，如果与第一个标签关联的概念是第二个标签的精化，则该标签可以转换为另一个标签。

我们的设计重用了iterator_traits<Iter>::iterator_category来指示迭代器的遍历能力。为了指定任何旧式迭代器分类都无法涵盖的能力，迭代器设计者可以使用一个iterator_category类型，该类型既可以转换为最合适的派生程度最高的旧迭代器分类标签，也可以转换为相应的新迭代器遍历标签。

我们没有提供用于基于访问概念进行派发的标签，部分原因是由于我们无法找到一种方法来为旧式迭代器自动推断正确的访问标签。迭代器的可写性可能取决于其value_type的赋值性，而目前没有已知的方法可以检测任意类型是否可赋值。幸运的是，基于访问能力进行派发的需求不如基于遍历能力进行派发的需求那么迫切。

一个困难的设计决策涉及operator[]。指定operator[]直接的方法是让其返回类型为reference；与operator*相同。然而，朝这个方向发展意味着满足旧随机访问迭代器要求的迭代器不一定符合可读或可写左值迭代器的模型。相反，我们选择了一个符合 issue 299 首选解决方案的设计：operator[]仅被要求返回可转换为value_type的内容（对于可读迭代器），并被要求支持赋值i[n] = t（对于可写迭代器）。

提议文本

{
  X tmp = r;
  --r;
  return tmp;
}

{
  Distance m = n;
  if (m >= 0)
    while (m--)
      ++r;
  else
    while (m++)
      --r;
  return r;
}

// lib.iterator.traits, traits and tags
template <class Iterator> struct is_readable_iterator;
template <class Iterator> struct iterator_traversal;

struct incrementable_traversal_tag { };
struct single_pass_traversal_tag : incrementable_traversal_tag { };
struct forward_traversal_tag : single_pass_traversal_tag { };
struct bidirectional_traversal_tag : forward_traversal_tag { };
struct random_access_traversal_tag : bidirectional_traversal_tag { };

category-to-traversal(iterator_traits<X>::iterator_category)

category-to-traversal(C) =
    if (C is convertible to incrementable_traversal_tag)
        return C;
    else if (C is convertible to random_access_iterator_tag)
        return random_access_traversal_tag;
    else if (C is convertible to bidirectional_iterator_tag)
        return bidirectional_traversal_tag;
    else if (C is convertible to forward_iterator_tag)
        return forward_traversal_tag;
    else if (C is convertible to input_iterator_tag)
        return single_pass_traversal_tag;
    else if (C is convertible to output_iterator_tag)
        return incrementable_traversal_tag;
    else
        the program is ill-formed

脚注

UnaryTypeTrait 概念在 n1519 中定义；LWG 正在考虑增加其特化版本应派生自其嵌套的::type.