Chapter 49: Mini Iterator

Mini STL 进入 iterator 后，主问题从“元素放在哪里”转向“算法如何用同一套位置接口访问不同对象”。一个 iterator 的实现质量，取决于它能否同时交付三件事：当前位置状态、可用操作集合、可被算法读取的类型信息。状态决定 *it 指向哪个元素，操作集合决定它能向前走、向后走还是随机跳转，类型信息决定泛型算法能否在编译期选择正确实现。

本章使用一个贯穿材料：为后续 mini_vector<T> 实现一组指针式随机访问迭代器，再在它上面包装反向迭代器和最小算法分发。这个材料足够小，可以把 iterator 的核心压缩到一个指针；同时它又足够接近真实 STL，因为 vector 迭代器的关键语义就是连续存储上的位置对象。

读完本章后，读者应能定位一个 iterator 类型缺失了哪些关联类型，判断它是否满足随机访问能力，解释 reverse_iterator::base() 和解引用元素之间的偏移关系，并能设计 distance / advance 这类算法的标签分发路径。后续 mini_vector 只要提供 begin()、end()、rbegin()、rend()，算法层就能通过这些 iterator 访问元素，而无需读取容器内部三指针。

本章代码是教学简化实现。它使用 C++17 风格的 iterator_category 和 tag dispatch 作为主线，并在最后说明 C++20 concepts 的对应写法。标准库真实实现会处理更多边界，例如 proxy reference、sentinel、contiguous iterator、iter_move、iter_swap、const 转换和 debug iterator；本章先建立最小可用骨架。

49.1 实现 iterator traits

iterator traits 是算法读取 iterator 类型信息的统一入口。算法通常只拿到一个模板参数 It，它不知道 It 是原始指针、容器内部类，还是某个 adapter 包装出来的位置对象。iterator_traits<It> 把 value_type、difference_type、reference 和 iterator_category 这类信息集中到一个类型上，算法只依赖这个类型入口。

贯穿材料中的 mini_vector<T> 迭代器会把一个 T* 包在类里。这个类需要告诉算法四类信息：value_type 表示元素值类型，difference_type 表示两个位置相减后的距离类型，reference 表示解引用后的结果类型，iterator_category 表示它承诺的迭代器能力。对连续数组上的位置对象来说，最自然的能力标签是 std::random_access_iterator_tag。

先实现一个最小 traits。主模板假设 iterator 类型自己提供嵌套类型；指针偏特化把原始指针也接入同一套算法入口。

#include <cstddef>
#include <iterator>
#include <type_traits>

namespace mini {

template<class It>
struct iterator_traits {
    using value_type = typename It::value_type;
    using difference_type = typename It::difference_type;
    using pointer = typename It::pointer;
    using reference = typename It::reference;
    using iterator_category = typename It::iterator_category;
};

template<class T>
struct iterator_traits<T*> {
    using value_type = std::remove_cv_t<T>;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;
    using iterator_category = std::random_access_iterator_tag;
};

template<class T>
struct iterator_traits<const T*> {
    using value_type = std::remove_cv_t<T>;
    using difference_type = std::ptrdiff_t;
    using pointer = const T*;
    using reference = const T&;
    using iterator_category = std::random_access_iterator_tag;
};

} // namespace mini

这段代码的关键点在于“算法读取信息”和“iterator 执行动作”被拆开。iterator_traits 自己不移动位置，也不访问元素；它只把类型信息暴露给算法。真正移动位置的代码仍在 iterator 对象里，例如 ++it、it += n、it - other。

指针偏特化使 T* 和自定义 iterator 在算法眼中具有同样入口。假设一个简化 mini_distance 接收 It first, It last，它可以通过 mini::iterator_traits<It>::difference_type 决定返回类型。传入 int* 时，主模板找不到 int*::difference_type，偏特化接管这条路径；传入 mini_vector<int>::iterator 时，主模板读取类内嵌套类型。

这个设计也给失败情况一个清晰位置。一个类型即使能写 ++it 和 *it，只要没有提供 traits 所需的类型信息，C++17 风格算法就很难可靠读取它的能力边界。真实标准库在 C++20 后引入了 iter_value_t、iter_reference_t、iterator_concept 等更细的入口，本章保留 C++17 风格，是因为 mini STL 的目标是展示核心结构：iterator 自己负责位置语义，traits 负责把语义暴露给算法。

对 mini 实现来说，检查 iterator traits 的顺序应固定下来。先看算法需要哪些关联类型，再看 iterator 类是否提供这些类型，然后看指针偏特化是否覆盖原始指针，最后看 iterator_category 是否和实际操作集合一致。最后一步很容易出错：把一个只能单向前进的类型标成 random_access_iterator_tag，算法可能会调用 it + n 或 last - first，编译失败或语义错误会出现在算法实例化处。

49.2 实现 random access iterator

随机访问迭代器的核心状态可以是一个指针。对 mini_vector<T> 来说，容器元素存放在连续存储中，begin() 返回首元素位置，end() 返回尾后位置。iterator 保存当前元素地址后，递增就是指针加一，递减就是指针减一，下标访问就是当前地址加偏移后解引用，两个 iterator 相减就是两个地址之间的元素距离。

下面的实现只覆盖 mini_vector<T> 需要的最小随机访问能力。它提供值类型信息、解引用、成员访问、前后移动、算术跳转、距离计算和比较。它没有加入 debug 边界检查；因此调用者必须保证 iterator 来自同一个连续区间，并且解引用时位置处于有效元素范围内。

namespace mini {

template<class T>
class vector_iterator {
public:
    using value_type = std::remove_cv_t<T>;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;
    using iterator_category = std::random_access_iterator_tag;

    vector_iterator() = default;
    explicit vector_iterator(pointer current) : current_(current) {}

    reference operator*() const { return *current_; }
    pointer operator->() const { return current_; }
    reference operator[](difference_type n) const { return *(current_ + n); }

    vector_iterator& operator++() {
        ++current_;
        return *this;
    }

    vector_iterator operator++(int) {
        vector_iterator old(*this);
        ++(*this);
        return old;
    }

    vector_iterator& operator--() {
        --current_;
        return *this;
    }

    vector_iterator operator--(int) {
        vector_iterator old(*this);
        --(*this);
        return old;
    }

    vector_iterator& operator+=(difference_type n) {
        current_ += n;
        return *this;
    }

    vector_iterator& operator-=(difference_type n) {
        current_ -= n;
        return *this;
    }

    friend vector_iterator operator+(vector_iterator it, difference_type n) {
        it += n;
        return it;
    }

    friend vector_iterator operator+(difference_type n, vector_iterator it) {
        it += n;
        return it;
    }

    friend vector_iterator operator-(vector_iterator it, difference_type n) {
        it -= n;
        return it;
    }

    friend difference_type operator-(vector_iterator lhs, vector_iterator rhs) {
        return lhs.current_ - rhs.current_;
    }

    friend bool operator==(vector_iterator lhs, vector_iterator rhs) {
        return lhs.current_ == rhs.current_;
    }

    friend bool operator!=(vector_iterator lhs, vector_iterator rhs) {
        return !(lhs == rhs);
    }

    friend bool operator<(vector_iterator lhs, vector_iterator rhs) {
        return lhs.current_ < rhs.current_;
    }

    friend bool operator>(vector_iterator lhs, vector_iterator rhs) {
        return rhs < lhs;
    }

    friend bool operator<=(vector_iterator lhs, vector_iterator rhs) {
        return !(rhs < lhs);
    }

    friend bool operator>=(vector_iterator lhs, vector_iterator rhs) {
        return !(lhs < rhs);
    }

    pointer base() const { return current_; }

private:
    pointer current_ = nullptr;
};

} // namespace mini

这个类的语义来自指针，但它多了一层类型边界。vector_iterator<T> 可以被 traits 识别，可以作为 mini_vector<T> 的公开位置类型，也可以在未来扩展调试信息。例如 debug 版本可以额外保存所属容器地址和区间边界，在解引用和相减时检查来源一致性。教学版本保留单指针状态，是为了让随机访问能力和连续内存之间的关系保持可见。

随机访问迭代器有几个必须同时成立的不变量。第一，it + n 和 n + it 应得到同一个位置。第二，(it + n) - it 应得到 n。第三，it[n] 应等价于 *(it + n)。第四，比较运算只在同一连续区间内有意义。第五，尾后位置可以比较、相减、递减到最后一个元素，但尾后位置本身没有可解引用元素。

把这些不变量放进一个短例子，可以看出算法如何消费 iterator。

int data[] = {10, 20, 30, 40};
mini::vector_iterator<int> first(data);
mini::vector_iterator<int> last(data + 4);

auto third = first + 2;
int value = *third;        // 30
auto count = last - first; // 4
bool ordered = first < last;

这段代码证明了两个结论。运行时对象关系上，iterator 只保存一个地址，所有位置变化都落到地址运算。编译期类型关系上，iterator 通过嵌套类型告诉算法“我支持随机访问”。这两件事必须匹配；如果只实现 operator++ 却标成随机访问，last - first 这类算法分支会在实例化时失败。

这个 iterator 的有效性跟底层存储绑定。只要 mini_vector 的存储未搬迁，指向现有元素的 iterator 可以继续定位原元素。发生 reallocate 后，旧地址不再指向新存储中的元素，旧 iterator 随即失效。这个失效判断来自对象存储地址变化，和 iterator 类本身是否还有一个非空指针无关。一个悬垂 iterator 仍可能保存旧地址，但那个地址已经脱离容器当前对象状态。

49.3 实现 reverse iterator

反向迭代器是一个 adapter。它不拥有元素，也不重新排列底层区间；它保存一个底层 iterator，并把移动方向和解引用位置做一次转换。对一个由底层位置 i 构造出来的反向迭代器 r，只要 r 可解引用，*r 对应底层的 *(i - 1)。因此 rbegin() 通常由 end() 构造，rend() 通常由 begin() 构造。

这个“一格偏移”是反向迭代器最容易出错的地方。底层 end() 指向尾后位置，无法直接解引用；但 reverse_iterator(end()) 的解引用结果应是最后一个元素。实现 operator* 时需要先复制 current_，再对副本执行 --tmp，最后返回 *tmp。base() 返回保存的底层当前位置，它和 operator* 指向的元素差一格。

namespace mini {

template<class It>
class reverse_iterator {
public:
    using iterator_type = It;
    using traits = mini::iterator_traits<It>;
    using value_type = typename traits::value_type;
    using difference_type = typename traits::difference_type;
    using pointer = typename traits::pointer;
    using reference = typename traits::reference;
    using iterator_category = typename traits::iterator_category;

    reverse_iterator() = default;
    explicit reverse_iterator(It current) : current_(current) {}

    It base() const { return current_; }

    reference operator*() const {
        It tmp = current_;
        --tmp;
        return *tmp;
    }

    pointer operator->() const {
        return &operator*();
    }

    reverse_iterator& operator++() {
        --current_;
        return *this;
    }

    reverse_iterator operator++(int) {
        reverse_iterator old(*this);
        ++(*this);
        return old;
    }

    reverse_iterator& operator--() {
        ++current_;
        return *this;
    }

    reverse_iterator operator--(int) {
        reverse_iterator old(*this);
        --(*this);
        return old;
    }

    reverse_iterator& operator+=(difference_type n) {
        current_ -= n;
        return *this;
    }

    reverse_iterator& operator-=(difference_type n) {
        current_ += n;
        return *this;
    }

    reference operator[](difference_type n) const {
        return *(*this + n);
    }

    friend reverse_iterator operator+(reverse_iterator it, difference_type n) {
        it += n;
        return it;
    }

    friend reverse_iterator operator-(reverse_iterator it, difference_type n) {
        it -= n;
        return it;
    }

    friend difference_type operator-(reverse_iterator lhs, reverse_iterator rhs) {
        return rhs.current_ - lhs.current_;
    }

    friend bool operator==(reverse_iterator lhs, reverse_iterator rhs) {
        return lhs.current_ == rhs.current_;
    }

    friend bool operator!=(reverse_iterator lhs, reverse_iterator rhs) {
        return !(lhs == rhs);
    }

    friend bool operator<(reverse_iterator lhs, reverse_iterator rhs) {
        return rhs.current_ < lhs.current_;
    }

private:
    It current_{};
};

} // namespace mini

这段实现展示了 adapter 的典型结构：类型信息来自底层 iterator，状态也是底层 iterator，外部行为由包装层重新解释。operator++ 在反向视角里向“下一个反向元素”移动，对底层来说就是 --current_。operator- 的方向也需要反转，所以两个反向 iterator 的距离写成 rhs.current_ - lhs.current_。

用同一组数组例子可以验证 base() 和解引用的关系。

int data[] = {10, 20, 30, 40};
using It = mini::vector_iterator<int>;

It first(data);
It last(data + 4);
mini::reverse_iterator<It> rfirst(last);

int value = *rfirst;       // 40
It underlying = rfirst.base();
bool points_to_end = underlying == last;

rfirst.base() 等于 last，但 *rfirst 得到最后一个元素 40。这个结果说明反向迭代器的公开位置和底层解引用位置不同。调用者在执行 erase(rit.base()) 这类操作时要特别小心：rit.base() 指向的是反向元素之后的正向位置。若要删除 *rit 对应元素，常见写法需要使用 std::prev(rit.base()) 对应的正向位置；在 mini 容器里也应保持这个判断。

反向迭代器的能力上限由底层 iterator 决定。底层只有双向能力时，反向迭代器能 ++、--，可以用于反向遍历。底层具有随机访问能力时，反向迭代器才能高效支持 + n、- n、下标和距离计算。本章的简化实现直接暴露随机访问操作，因为贯穿材料使用 vector_iterator；若将来要适配 mini_list，需要按底层 category 或 concepts 限制这些操作。

49.4 实现 iterator category 分发

iterator category 分发解决的问题是：同一个算法接口面对不同能力的 iterator 时，应选择不同复杂度的实现。以 distance(first, last) 为例，输入迭代器需要从 first 递增到 last，复杂度为线性；随机访问迭代器可以直接返回 last - first，复杂度为常数。算法接口相同，内部路径由 iterator_category 决定。

C++17 风格的 tag dispatch 通常分成两层。公开函数读取 traits 中的 iterator_category，再把一个标签对象传给内部实现。内部实现通过重载选择不同路径。标签类型本身没有运行时数据，它的作用是在编译期参与重载决议。

namespace mini {

template<class It>
auto distance_impl(It first, It last, std::input_iterator_tag)
    -> typename mini::iterator_traits<It>::difference_type {
    typename mini::iterator_traits<It>::difference_type n = 0;
    for (; first != last; ++first) {
        ++n;
    }
    return n;
}

template<class It>
auto distance_impl(It first, It last, std::random_access_iterator_tag)
    -> typename mini::iterator_traits<It>::difference_type {
    return last - first;
}

template<class It>
auto distance(It first, It last)
    -> typename mini::iterator_traits<It>::difference_type {
    using category = typename mini::iterator_traits<It>::iterator_category;
    return distance_impl(first, last, category{});
}

} // namespace mini

这个实现利用了标准 iterator tag 的继承关系。std::random_access_iterator_tag 派生自 std::bidirectional_iterator_tag，后者再派生自 std::forward_iterator_tag 和 std::input_iterator_tag。当有精确的随机访问重载时，随机访问 iterator 会选择常数复杂度路径；当只有输入重载时，更强能力的 iterator 也能退到输入路径。这种“能力更强可走更弱接口”的关系，使算法可以先写通用路径，再逐步补强优化路径。

advance 的分发更能说明能力边界。输入迭代器只能向前推进；双向迭代器可以根据正负距离前进或后退；随机访问迭代器可以直接做 it += n。一个公开函数可以维持同一接口，内部按能力选择操作集合。

namespace mini {

template<class It, class Distance>
void advance_impl(It& it, Distance n, std::input_iterator_tag) {
    while (n > 0) {
        ++it;
        --n;
    }
}

template<class It, class Distance>
void advance_impl(It& it, Distance n, std::bidirectional_iterator_tag) {
    if (n >= 0) {
        while (n > 0) {
            ++it;
            --n;
        }
    } else {
        while (n < 0) {
            --it;
            ++n;
        }
    }
}

template<class It, class Distance>
void advance_impl(It& it, Distance n, std::random_access_iterator_tag) {
    it += n;
}

template<class It, class Distance>
void advance(It& it, Distance n) {
    using category = typename mini::iterator_traits<It>::iterator_category;
    advance_impl(it, n, category{});
}

} // namespace mini

这段代码给出一个可复用判断顺序。先判断算法需要哪些基本操作，例如递增、递减、相减、跳转。再从 traits 读取 category，确认该 category 承诺这些操作。然后为最弱可行能力写通用路径，为更强能力写优化路径。最后把复杂度写成接口承诺的一部分：distance 在输入路径是线性，在随机访问路径是常数；advance 在随机访问路径可以一次完成，在输入或双向路径需要循环推进。

C++20 concepts 可以把同一思想写成约束重载。concepts 直接约束表达式集合，例如随机访问 iterator 需要支持 +=、+、-、下标、全序比较和距离计算。对于 mini STL，concepts 版本可以作为接口验收工具；它让错误更接近约束失败点，而 tag dispatch 版本更适合展示传统 STL 的源码形状。

#include <concepts>
#include <iterator>

namespace mini {

template<std::input_iterator It>
auto concept_distance(It first, It last) {
    typename std::iterator_traits<It>::difference_type n = 0;
    for (; first != last; ++first) {
        ++n;
    }
    return n;
}

template<std::random_access_iterator It>
auto concept_distance(It first, It last) {
    return last - first;
}

} // namespace mini

concepts 版本和 tag dispatch 版本的工程目标一致：把算法选择建立在 iterator 能力上。差异在于表达位置。tag dispatch 通过 iterator_category 标签进入重载，错误常出现在内部实现实例化处；concepts 把约束放在函数签名上，调用点能更早看到“这个 iterator 不满足随机访问”。在维护 mini STL 时，可以先用 tag dispatch 实现传统路径，再用 concepts 写测试或新接口约束。

本章的最终判断可以收束为一个顺序：实现 iterator 时先固定状态模型，再补齐解引用和移动操作，然后提供 traits 类型信息，再用 category 或 concepts 验证算法是否能选择正确路径，最后回到容器存储变化判断 iterator 有效性。这个顺序能同时覆盖接口现象、语言规则、实现形状和工程后果。

最小自检任务

阅读下面代码，判断 mini::distance(first, last)、mini::distance(rfirst, rlast)、rfirst.base() 和 *rfirst 的结果关系，并说明 reverse_iterator 的 operator++ 为什么要修改底层 iterator 的相反方向。

int data[] = {1, 2, 3, 4, 5};
using It = mini::vector_iterator<int>;

It first(data);
It last(data + 5);

mini::reverse_iterator<It> rfirst(last);
mini::reverse_iterator<It> rlast(first);

auto forward_count = mini::distance(first, last);
auto reverse_count = mini::distance(rfirst, rlast);
int first_reverse_value = *rfirst;
It base_of_rfirst = rfirst.base();

答案要点

forward_count 为 5，因为 vector_iterator 的 category 是 std::random_access_iterator_tag，mini::distance 选择 last - first 的常数复杂度路径。reverse_count 也为 5，因为反向迭代器的距离运算把底层方向反过来，rfirst 保存 last，rlast 保存 first，表达式返回 rhs.current_ - lhs.current_，结果等于 first - last 的反向解释后得到正距离。

first_reverse_value 为 5。rfirst 由底层 last 构造，last 是尾后位置；反向解引用先复制底层位置，再递减到最后一个元素位置，所以得到数组最后一个元素。base_of_rfirst == last 成立，这说明 base() 返回保存的底层当前位置，和 operator* 指向的元素差一格。

reverse_iterator::operator++ 需要执行 --current_，因为反向视角中的“前进一步”表示从最后一个元素走向倒数第二个元素。底层正向 iterator 中，倒数第二个元素的位置位于最后一个元素之前，所以底层位置要向低地址方向移动。这个方向反转同样影响 operator+=、operator- 和比较运算。

本章知识点总结

• traits 入口：iterator_traits 把 iterator 的元素类型、距离类型、引用类型和能力标签集中暴露给泛型算法。
• 指针特化：T* 通过 traits 偏特化接入算法体系，原始指针和自定义 iterator 可以共享同一算法入口。
• 状态模型：vector_iterator 的最小状态是当前元素指针，所有移动、比较和距离计算都落到指针运算。
• 能力匹配：iterator_category 必须和实际操作集合一致，随机访问标签要求跳转、相减、下标和全序比较等能力共同成立。
• 尾后位置：end() 可以比较、相减和递减到最后一个元素，解引用尾后位置没有有效元素语义。
• 失效来源：vector_iterator 的有效性跟底层存储地址绑定，容器重新分配存储后旧 iterator 保存的地址脱离当前对象状态。
• 反向偏移：reverse_iterator(i) 可解引用时指向底层 i - 1 对应元素，base() 返回保存的底层当前位置。
• 方向反转：反向迭代器的递增对应底层递减，反向迭代器的距离和比较也要按底层方向反过来解释。
• adapter 边界：反向迭代器不拥有元素，它复用底层 iterator 的状态和类型信息，只改变遍历方向和解引用规则。
• 标签分发：tag dispatch 用 iterator_category 参与重载决议，使同一算法接口按 iterator 能力选择通用路径或优化路径。
• 复杂度承诺：distance 在输入路径需要线性推进，在随机访问路径可以用相减得到常数复杂度结果。
• concepts 对照：C++20 concepts 把能力约束放到函数签名上，能更早表达 iterator 是否满足某个算法入口。
• 实现顺序：实现 mini iterator 时应先固定状态，再实现操作，随后补齐 traits，最后用算法分发和容器存储变化检查语义边界。