第8.3章: 迭代器类别

概述

迭代器就是在 range 中移动的“游标”。range 产生迭代器；迭代器表示 range 中的某个位置。

与 range 一样，迭代器也构成一条能力层级。每个更强的迭代器类别都包含所有更弱类别的能力。

本章将介绍：

• 迭代器类别的完整层级
• 从 input_iterator 到 contiguous_iterator 的可读链条
• 独立的可写分支 output_iterator
• 为什么指向对象类型的指针是最强的可读迭代器
• 为什么有些指针不对应任何迭代器类别
• to_address 如何定义连续性

1. 完整的迭代器层级

所有迭代器类别都是对基础概念 input_or_output_iterator 的细化。由此，层级分成一条可读链条和一个独立的可写分支：

input_or_output_iterator
│
├── input_iterator
│     │
│     ├── forward_iterator
│     │
│     ├── bidirectional_iterator
│     │
│     ├── random_access_iterator
│     │
│     └── contiguous_iterator   ← pointers to object types live here
│
└── output_iterator   (separate writable branch)

2. range 与迭代器的关系

range 是一个对象，它产生两个迭代器：

• 起始迭代器（第一个位置）
• 末尾迭代器（最后一个位置之后的一个位置）

range 不存储位置，迭代器不存储容器。

两者是互补的：

• range 描述可以遍历什么。
• 迭代器描述遍历过程中你在哪里。

range 由以下内容定义：

auto it  = begin(r);
auto end = end(r);

迭代器由以下内容定义：

++it;   // move to next position
*it;    // access the element at that position

3. input_or_output_iterator

这是迭代器层级的根。每个迭代器要么可读，要么可写，要么两者兼备。

其他所有迭代器类别都是对它的细化。

4. input_iterator

最小的可读迭代器类别。input_iterator 支持：

• 只能读取元素一次
• 只能向前移动
• 单遍遍历

5. forward_iterator

forward_iterator 具有 input_iterator 的全部能力，并额外支持：

• 对同一批元素进行多次遍历
• 按相同顺序重新访问元素

6. bidirectional_iterator

bidirectional_iterator 具有 forward_iterator 的全部能力，并额外支持：

• 既能向前也能向后移动

7. random_access_iterator

random_access_iterator 具有 bidirectional_iterator 的全部能力，并额外支持：

• 常数时间跳到任意位置
• 用 it[n] 做下标访问

8. contiguous_iterator

contiguous_iterator 具有 random_access_iterator 的全部能力，并额外保证它所指的元素在程序的抽象地址空间中占据相邻的地址。

当迭代器指向真实元素（而不是末尾位置）时，下面的等式成立：

::std::to_address(it + 1) == ::std::to_address(it) + 1

指针作为 contiguous_iterator

指向对象类型的指针（例如 int* 或 char*）是 contiguous_iterator 的典型例子。

然而，并非所有指针都是迭代器：

• void* 不能自增，也不能按元素类型解引用
• 函数指针不能自增，也不能解引用

示例：::fast_io::vector<int>::iterator

void analyze_vector_iterator(::fast_io::vector<int>::iterator it)
{
    if constexpr(::std::contiguous_iterator<decltype(it)>)
        print("vector::iterator is a contiguous iterator\n");

    if constexpr(::std::random_access_iterator<decltype(it)>)
        print("vector::iterator is a random_access iterator\n");

    if constexpr(::std::bidirectional_iterator<decltype(it)>)
        print("vector::iterator is a bidirectional iterator\n");

    if constexpr(::std::forward_iterator<decltype(it)>)
        print("vector::iterator is a forward iterator\n");

    if constexpr(::std::input_iterator<decltype(it)>)
        print("vector::iterator is an input iterator\n");

    if constexpr(::std::output_iterator<decltype(it), int>)
        print("vector::iterator is an output iterator for int\n");
}

9. output_iterator（独立分支）

output_iterator 是 input_iterator 的可写对应物。它允许写入元素，但不要求从迭代器读取。

它不属于可读层级。

10. 用 if constexpr 探测迭代器类别

void analyze_iterator(int* it)
{
    if constexpr(::std::contiguous_iterator<decltype(it)>)
        print("pointer is a contiguous iterator\n");

    if constexpr(::std::random_access_iterator<decltype(it)>)
        print("pointer is a random_access iterator\n");

    if constexpr(::std::bidirectional_iterator<decltype(it)>)
        print("pointer is a bidirectional iterator\n");

    if constexpr(::std::forward_iterator<decltype(it)>)
        print("pointer is a forward iterator\n");

    if constexpr(::std::input_iterator<decltype(it)>)
        print("pointer is an input iterator\n");

    if constexpr(::std::output_iterator<decltype(it), int>)
        print("pointer is an output iterator for int\n");
}

要点

• input_or_output_iterator 是根概念。
• 可读层级从 input_iterator 一直上升到 contiguous_iterator。
• output_iterator 是一个独立的可写分支。
• 指向对象类型的指针是 contiguous_iterator。
• void* 和函数指针都不是迭代器。
• range 产生迭代器；迭代器表示位置。