Chapter 38: Iterator Traits

泛型算法拿到的通常只有两个位置对象：first 和 last。算法要继续工作，还需要知道这些位置对象能解引用出什么类型、两个位置相减或推进时使用什么距离类型、能否用 + n 直接跳转、解引用返回真实引用还是代理对象。这些信息不属于某个具体容器接口，却决定算法能否写成统一模板。

std::iterator_traits 是标准库放在 iterator 和 algorithm 中间的一层类型查询入口。它把不同 iterator 类型暴露的关联类型整理成统一名字，让算法可以通过 std::iterator_traits<Iter>::value_type、difference_type、pointer、reference 和 iterator_category 读取能力信息。标准草案的 iterator.traits 条款把它定义为算法只依赖 iterator 时需要查询关联类型的机制；cppreference 的 std::iterator_traits 页面也把它描述为 LegacyIterator 属性的统一访问接口。

本章贯穿一个简化版 reverse 算法。它需要临时保存元素、计算距离、双向移动 iterator，并且要同时支持 std::vector<int>::iterator、std::list<int>::iterator 和原生指针。读完本章后，读者应能定位一个泛型算法到底依赖哪几个 iterator 关联类型，判断一个自定义 iterator 为什么无法进入算法，区分真实引用和 proxy reference 对算法赋值语义的影响，并能按 traits 查询顺序排查算法能力选择。

下面的代码是本章的贯穿材料。它是教学简化代码，用来暴露 traits 查询点；它不声称复刻任一标准库实现。

#include <iterator>
#include <utility>

template<class BidirIt>
void traits_reverse(BidirIt first, BidirIt last)
{
    using traits = std::iterator_traits<BidirIt>;
    using value_type = typename traits::value_type;
    using difference_type = typename traits::difference_type;

    difference_type n = std::distance(first, last);
    while (n > 1) {
        --last;
        value_type tmp = *first;
        *first = *last;
        *last = std::move(tmp);
        ++first;
        n -= 2;
    }
}

这段代码已经暴露出 traits 的核心问题：BidirIt 可能是类类型 iterator，也可能是 int*。算法源码没有资格假设 BidirIt::value_type 一定存在，因为原生指针没有嵌套类型。统一入口必须把“类 iterator 的嵌套类型”和“原生指针的语言属性”合并到同一套名字下。

38.1 iterator_traits 作用

iterator_traits 的作用是把 iterator 的关联类型变成算法可查询的稳定接口。关联类型指一个 iterator 类型随身携带、但不通过运行时成员变量表达的类型信息，包括元素类型、距离类型、指针类型、引用类型和能力标签。算法读取这些类型后，可以生成局部变量、选择重载分支、声明返回类型，并把位置对象的能力限制在可证明范围内。

在传统 STL 设计中，算法的参数只接收 iterator，算法不接收容器。std::sort(first, last) 无法直接知道 first 来自 std::vector<int>、原生数组，还是某个自定义连续缓冲区 iterator。算法能看到的只是 Iter 这个模板参数。iterator_traits<Iter> 就是在这个位置补齐类型信息的入口。

类类型 iterator 通常自己声明五个嵌套类型。下面是一个只展示类型形状的最小 iterator 外壳。代码没有实现完整 iterator 运算，只用于说明 traits 可以从哪里读取类型。

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

struct int_buffer_iterator {
    using value_type = int;
    using difference_type = std::ptrdiff_t;
    using pointer = int*;
    using reference = int&;
    using iterator_category = std::random_access_iterator_tag;

    int* current{};
};

using traits = std::iterator_traits<int_buffer_iterator>;
static_assert(std::is_same_v<traits::value_type, int>);
static_assert(std::is_same_v<traits::difference_type, std::ptrdiff_t>);

这段代码说明 traits 的第一层意义：算法不用直接依赖 int_buffer_iterator::value_type，而是依赖 std::iterator_traits<int_buffer_iterator>::value_type。这个间接层让原生指针、标准 iterator adapter、自定义 iterator 特化都可以进入同一个算法入口。

iterator_traits 的第二层意义是把“类型查询失败”变成模板约束的一部分。C++17 起，主模板对缺少必要嵌套类型的 iterator 更适合参与 SFINAE；C++20 又引入更复杂的关联类型推导路径，例如通过 incrementable_traits、indirectly_readable_traits 和 iter_reference_t 生成部分类型。工程判断要把版本边界分清：C++20 前的传统 STL 代码更常显式依赖五个嵌套类型；C++20 ranges 体系还会使用 iterator_concept 和 std::iter_value_t 等新入口。

把贯穿材料放回来看，traits_reverse 至少依赖三类信息。value_type 用来创建临时对象，difference_type 用来保存距离，iterator_category 虽然没有直接写出，但 std::distance 和 std::advance 这类基础算法会利用它决定推进方式。若这三类信息缺失，算法即使语法上只拿到了两个 iterator，也无法生成正确代码。

38.2 value_type

value_type 表示 iterator 所遍历序列中的元素值类型。它回答的问题是：算法如果需要创建一个“元素值的独立副本”，应该声明成什么类型。这个类型通常去掉引用语义，代表可存储、可移动、可拷贝的值对象。

贯穿材料中的 value_type tmp = *first; 依赖的就是这条规则。*first 的结果可能是 int&，也可能是代理引用对象；算法希望 tmp 成为一个独立临时值，用来在交换过程中保存旧元素。因此 tmp 使用 value_type，而非直接使用 decltype(*first)。如果直接写成 decltype(*first) tmp = *first;，当解引用返回 int& 时，tmp 会成为引用绑定，后续赋值会改变原元素，交换过程就会失去独立暂存对象。

下面的短代码展示 value_type 与解引用表达式类型的差异。std::vector<int>::iterator 解引用返回 int&，但它的 value_type 是 int。

#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

using iter = std::vector<int>::iterator;
using traits = std::iterator_traits<iter>;

static_assert(std::is_same_v<traits::value_type, int>);
static_assert(std::is_same_v<decltype(*std::declval<iter&>()), int&>);

这段代码对应算法设计中的一个固定判断：需要保存元素值时看 value_type，需要表达解引用结果时看 reference 或 decltype(*it)。前者服务临时对象和返回值，后者服务读写元素和生命周期边界。

value_type 对 proxy iterator 的意义更明显。以 std::vector<bool> 的常见实现形状为例，容器通常把多个布尔值压缩到一个机器字中，单个元素解引用无法返回真实 bool&，于是返回一个代理对象。这个代理对象可以转换成 bool，也可以通过赋值修改对应 bit。此时 iterator 的 value_type 仍然表示逻辑元素类型 bool，解引用结果却是代理引用类型。

#include <iterator>
#include <type_traits>
#include <vector>

using iter = std::vector<bool>::iterator;
using traits = std::iterator_traits<iter>;

static_assert(std::is_same_v<traits::value_type, bool>);
static_assert(!std::is_same_v<traits::reference, bool&>);

这个例子给出工程边界：算法用 value_type 创建临时值时，拿到的是逻辑值对象；算法用 reference 写回元素时，接触的是容器暴露的访问代理。traits_reverse 中的 value_type tmp = *first; 对 std::vector<bool> 这类场景仍然有合理语义，因为临时保存的是一个 bool 值，写回时才由 proxy reference 负责修改底层 bit。

标准版本也影响 value_type 的推导方式。C++20 前，类 iterator 通常要提供 Iter::value_type；C++20 的标准措辞允许在满足旧式输入 iterator 要求时通过 indirectly_readable_traits<Iter>::value_type 参与推导。写工程代码时，面向传统 STL 算法的自定义 iterator 仍建议显式提供 value_type，因为它能让旧代码、旧编译器和调试信息都更直接。

38.3 difference_type

difference_type 表示两个 iterator 位置之间的距离类型。它通常是有符号整数类型，因为 last - first、std::distance(first, last) 和 std::advance(it, n) 都需要表达正向、反向或零距离。标准库对原生指针的 traits 使用 std::ptrdiff_t，这也说明距离类型属于位置差异，而非容器 size() 返回的元素数量类型。

贯穿材料中的 difference_type n = std::distance(first, last); 用距离控制循环。std::distance 对不同 iterator 能力有不同成本：随机访问 iterator 可以用减法一次算出距离；输入、前向、双向 iterator 通常要线性推进计数。difference_type 在这里提供保存结果的类型，iterator_category 决定计算路径。

下面的代码把这个差异压成两个重载。真实标准库实现可能使用 tag dispatch、if constexpr、concepts 或内部 helper；教学代码只展示判断入口。

#include <iterator>

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

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

template<class It>
typename std::iterator_traits<It>::difference_type
fast_distance(It first, It last)
{
    using category = typename std::iterator_traits<It>::iterator_category;
    return fast_distance(first, last, category{});
}

这段代码暴露出两个工程判断。第一，距离类型来自 iterator，而非容器；泛型算法只持有 first 和 last 时不能去找容器的 size_type。第二，difference_type 的存在不承诺距离计算是常数时间；复杂度来自 iterator 能力和算法路径。

difference_type 与 size_type 的区别经常出现在边界错误中。std::vector<T>::size_type 通常是无符号类型，适合表达容器当前元素数量；difference_type 通常是有符号类型，适合表达两个位置的相对距离。把反向移动距离强行放进无符号类型会让负值变成很大的正值，随后推进 iterator 时触发越界访问或长时间循环。

#include <iterator>
#include <vector>

void move_back_example(std::vector<int>& values)
{
    auto it = values.end();
    using diff_t = std::iterator_traits<decltype(it)>::difference_type;

    diff_t step = -1;
    std::advance(it, step);
}

这段代码的重点是类型语义。step 表示相对位移，所以使用 difference_type。若算法要保存元素数量，才应考虑容器的 size_type 或 std::size_t。泛型 iterator 算法的判断顺序是先确认位置差异，再选择有符号距离类型，随后根据 iterator category 判断推进成本。

38.4 pointer

pointer 表示 iterator 暴露的指针式访问类型。对原生指针和普通容器 iterator，它通常是 T* 或 const T*；对没有 operator-> 的 iterator，C++20 标准推导路径会把 pointer 设为 void；对代理或特殊访问器，它可能是自定义 pointer-like 类型。

pointer 解决的问题是成员访问和地址表达，而非元素所有权。iterator 自身只是位置对象，pointer 也通常只是指向或代理访问底层元素的类型。算法如果只是读写 *it，通常不需要查询 pointer；只有在实现 operator->、需要适配指针式接口或判断 contiguous 访问时，它才进入核心路径。

下面的简化 iterator 展示 pointer 与 operator-> 的关系。它把 operator-> 的返回类型和 traits 中的 pointer 保持一致。

#include <cstddef>
#include <iterator>

struct record {
    int id;
};

struct record_iterator {
    using value_type = record;
    using difference_type = std::ptrdiff_t;
    using pointer = record*;
    using reference = record&;
    using iterator_category = std::forward_iterator_tag;

    record* current{};

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

这段代码说明了一个常见约定：pointer 是 operator-> 暴露给调用者的类型。调用者写 it->id 时，使用的是 iterator 提供的成员访问路径。若 iterator 的解引用结果是 proxy reference，operator-> 可能要返回一个临时代理指针对象；这种设计会引入生命周期边界，调用者不能把它简单等同于底层元素地址。

pointer 与 contiguous iterator 的关系需要单独区分。连续 iterator 表示元素在内存中按 value_type 连续排列，C++20 引入 std::contiguous_iterator_tag 和 contiguous iterator concept 来表达这层语义。原生指针的 traits 在 C++20 中同时给出 iterator_category = std::random_access_iterator_tag 和 iterator_concept = std::contiguous_iterator_tag。这意味着指针既支持随机访问运算，也表达连续存储能力。

工程代码中，判定连续内存需要更多证据。一个 iterator 的 pointer 可能是 T*，但库是否允许把 [first, last) 当作连续缓冲区，还要看 iterator concept、标准保证和容器语义。std::vector<T>::iterator 在现代标准中满足连续 iterator 要求；std::deque<T>::iterator 支持随机访问，但底层分段存储，不能把整个范围当作一段连续内存。

贯穿材料 traits_reverse 没有读取 pointer，这正好说明 traits 的成员类型各有位置。交换元素只需要 value_type 和 reference 语义；把 iterator 传给需要地址或连续缓冲区的接口时，才需要检查 pointer、operator->、std::to_address 和 contiguous 能力。

38.5 reference

reference 表示 *it 解引用后暴露给算法的访问结果类型。它可能是真实引用，例如 int&；也可能是 proxy reference，例如 std::vector<bool>::reference；还可能在输出 iterator 场景中被声明为 void 或一个只支持赋值的代理类型。这个类型决定算法能否读、能否写、写入后修改的是哪个底层对象，以及临时绑定是否安全。

在普通容器中，reference 和 value_type& 经常相同。这个相同性让算法可以把 *it 当成元素对象本身。

#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

using iter = std::vector<int>::iterator;
using traits = std::iterator_traits<iter>;

static_assert(std::is_same_v<traits::reference, int&>);

一旦进入 proxy reference，算法就要按“访问句柄”理解 reference。std::vector<bool>::reference 通常保存指向底层字和 bit 位置的信息，赋值时修改对应 bit，读取时转换成 bool。它像引用一样参与表达式，但类型层面是由容器提供的代理对象。

#include <iterator>
#include <type_traits>
#include <vector>

using iter = std::vector<bool>::iterator;
using traits = std::iterator_traits<iter>;

static_assert(std::is_same_v<traits::value_type, bool>);
static_assert(!std::is_reference_v<traits::reference> ||
              !std::is_same_v<traits::reference, bool&>);

这个差异会直接影响算法写法。traits_reverse 使用 value_type tmp = *first; 保存逻辑值，再通过 *first = *last; 和 *last = std::move(tmp); 写回元素。它没有把 reference 保存到局部变量里长期使用，因此 proxy reference 的生命周期风险较低。若算法写成 auto& ref = *it;，在 proxy 场景中可能无法编译，因为解引用结果没有提供左值引用绑定；若写成 auto ref = *it;，ref 可能复制了一个代理句柄，后续赋值仍会修改原容器位置。

输出 iterator 是另一类边界。std::back_insert_iterator<std::vector<int>> 的解引用结果是一个适配器对象；对它赋值会调用底层容器的 push_back。这类 iterator 的 value_type、reference 等传统关联类型在不同标准版本和实现中可能没有普通读写 iterator 那样的含义。算法如果需要读取旧值，就应要求输入能力；如果只需要写入，就应把需求收窄到输出能力。

判断 reference 时应按三个问题推进。第一，*it 是否能读出一个 value_type 逻辑值；第二，*it = value 是否会写回底层序列；第三，解引用结果能否被保存并跨越 iterator 递增、容器修改或临时对象结束。真实引用通常跟随底层元素生命周期；proxy reference 则跟随代理对象和底层存储的共同边界。

38.6 iterator_category

iterator_category 是旧式 iterator 体系中的能力标签。它用一个空类型表示 iterator 至少支持哪组操作，典型标签包括 std::input_iterator_tag、std::output_iterator_tag、std::forward_iterator_tag、std::bidirectional_iterator_tag 和 std::random_access_iterator_tag。C++20 又加入 std::contiguous_iterator_tag 并引入 iterator_concept；本节先围绕传统算法常用的 iterator_category 展开。

能力标签服务算法选择。std::distance 面对随机访问 iterator，可以直接返回 last - first；面对输入 iterator，只能逐步 ++first 并计数。std::advance 面对随机访问 iterator，可以执行 it += n；面对双向 iterator，负数距离可以通过 --it 逐步回退；面对输入 iterator，通常只支持正向推进。

下面的 Mermaid 图展示传统 traits 能力查询路径。图只表达教学路径，真实实现可能使用不同 helper 名称。

图中的核心路径是从模板参数转到 traits，再从标签转到实现分支。算法不需要知道容器名称，只需要知道 iterator 能力下限。这个下限必须真实反映 iterator 支持的操作；把一个只会 ++ 的 iterator 标成 random_access_iterator_tag 会让算法选择 it + n、last - first 这类表达式，编译失败或得到错误语义。

标签之间存在层级关系。forward iterator 在 input iterator 的基础上提供多遍遍历语义；bidirectional iterator 在 forward 的基础上提供 --；random access iterator 在 bidirectional 的基础上提供加减整数、两个 iterator 相减、下标访问和全序比较。算法可以用更强标签走更快路径，但算法的接口前提也会随之提高。

#include <iterator>
#include <list>
#include <type_traits>
#include <vector>

static_assert(std::is_base_of_v<
    std::bidirectional_iterator_tag,
    typename std::iterator_traits<std::list<int>::iterator>::iterator_category>);

static_assert(std::is_base_of_v<
    std::random_access_iterator_tag,
    typename std::iterator_traits<std::vector<int>::iterator>::iterator_category>);

这段代码使用 std::is_base_of_v，因为标准标签通常按继承表达能力包含关系。工程代码中常见的 tag dispatch 也依赖这种关系：传入更强标签时，可以匹配更具体重载，或在回退路径中作为较弱能力使用。

C++20 的边界需要单独说明。现代 ranges 算法更多使用 concepts 和 iterator_concept 表达能力，iterator_category 主要服务旧式算法和向后兼容。一个自定义 iterator 面向 C++20 ranges 时，可能需要同时考虑 iterator_concept 和 iterator_category；面向传统 STL 算法时，iterator_category 仍然是许多旧代码的关键查询入口。

38.7 指针特化

原生指针没有 value_type、difference_type、reference 这类嵌套类型。标准库通过 std::iterator_traits<T*> 的偏特化把指针映射成 iterator 关联类型，让原生数组可以直接进入 iterator-based algorithm。没有这层特化，traits_reverse(a, a + n) 这类调用就无法通过 std::iterator_traits<int*>::value_type 生成临时对象。

C++20 中，指针特化大致给出以下关联类型：difference_type 是 std::ptrdiff_t，value_type 是去掉 cv 限定后的 T，pointer 是 T*，reference 是 T&，iterator_category 是 std::random_access_iterator_tag，并额外给出 iterator_concept = std::contiguous_iterator_tag。这里的“指针”只覆盖对象类型指针，函数指针不满足同样的 iterator 语义。

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

using traits = std::iterator_traits<const int*>;

static_assert(std::is_same_v<traits::difference_type, std::ptrdiff_t>);
static_assert(std::is_same_v<traits::value_type, int>);
static_assert(std::is_same_v<traits::pointer, const int*>);
static_assert(std::is_same_v<traits::reference, const int&>);
static_assert(std::is_base_of_v<
    std::random_access_iterator_tag,
    traits::iterator_category>);

这段代码解释了两个细节。第一，const int* 的 value_type 是 int，因为 value type 表示逻辑元素值，cv 限定体现在 reference 和 pointer 上。第二，const int* 的 reference 是 const int&，所以算法可以读取元素，但不能通过该 iterator 写回元素。

把指针特化放回 traits_reverse，就能解释原生数组为什么能调用泛型算法。int* 在语言层面支持 ++、--、+ n、last - first、*p 和 p->member 等操作；traits 偏特化把这些语言能力翻译成 STL 需要的关联类型。算法看到的是统一的 std::iterator_traits<int*>，而非为指针单独写一套算法。

指针特化也给出一个源码阅读信号。看到标准库算法内部写 typename iterator_traits<_Iter>::value_type 时，不应马上把 _Iter 理解成类类型。_Iter 可能就是 T*。这也是很多 STL 源码坚持通过 traits 取类型的原因：它要同时覆盖容器 iterator、指针和 iterator adapter。

38.8 算法如何通过 traits 获取 iterator 能力

算法通过 traits 获取 iterator 能力时，通常按“值类型、引用语义、距离类型、能力标签、版本边界”的顺序建立判断。这个顺序能把编译错误、复杂度差异和生命周期风险分开处理。

第一步看算法是否需要元素值对象。需要临时保存、返回新值、创建缓冲区时，查询 value_type。traits_reverse 的 tmp 就属于这个场景。若算法只是把输入写到输出，例如 std::copy 的核心循环，通常可以通过 *out = *in 传播值，而不必显式创建 value_type 临时对象。

第二步看算法是否需要保存解引用结果。需要直接读写底层元素时，关注 reference。真实引用、const reference、proxy reference 会给出不同赋值边界。对 const int* 来说，reference 是 const int&，写入路径会失败；对 std::vector<bool>::iterator 来说，reference 是代理类型，保存局部变量时要意识到它可能仍指向底层 bit。

第三步看算法是否需要位置距离。需要计数、推进、切分区间时，查询 difference_type。这个类型只解决“用什么类型保存距离”，不解决“计算距离要花多少操作”。复杂度要继续交给 iterator_category 或 C++20 concepts 判断。

第四步看算法是否能走优化路径。传统算法通过 iterator_category 做 tag dispatch；现代 C++ 代码也可以用 if constexpr 配合 concepts 表达同样意图。下面的简化代码把两条路径写在一起，展示 traits 在旧式算法中的位置。

#include <iterator>
#include <type_traits>

namespace detail {
    template<class It>
    void advance_impl(It& it,
                      typename std::iterator_traits<It>::difference_type n,
                      std::random_access_iterator_tag)
    {
        it += n;
    }

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

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

template<class It>
void teaching_advance(It& it,
                      typename std::iterator_traits<It>::difference_type n)
{
    using category = typename std::iterator_traits<It>::iterator_category;
    detail::advance_impl(it, n, category{});
}

这段代码展示的是“先查询类型，再选择实现”。teaching_advance 没有询问容器，也没有分支判断 std::vector 或 std::list。它只相信 iterator 报告的能力标签。若标签真实，算法得到对应复杂度；若标签夸大，代码会在不支持的表达式上失败。

第五步看标准版本和实现形状。传统 iterator 通过五个嵌套类型接入 traits；原生指针通过偏特化接入；标准 iterator adapter 可能有标准库提供的 traits 特化；C++20 还引入 iterator_concept、iter_value_t、iter_reference_t、incrementable_traits 等新工具。阅读源码时，先确认目标代码属于旧式 algorithm、ranges algorithm，还是实现内部桥接层，再判断它为什么查询某个 traits 成员。

这一章的可复用判断顺序可以固定为五步：先确认算法是否需要值对象；再确认解引用结果能否按预期读写；再确认距离类型是否能表达正负位移；再用能力标签判断复杂度和可用操作；最后检查指针、proxy、adapter 和 C++20 concepts 是否改变了入口。这个顺序比直接背五个成员名更稳定，因为它从算法需求倒推 iterator 必须提供的证据。

最小自检任务

阅读下面的代码，判断 rotate_one_left 对 std::vector<int>::iterator、std::list<int>::iterator、int* 和 std::vector<bool>::iterator 分别会依赖哪些 traits 信息。说明 value_type、difference_type、reference 和 iterator_category 在这个算法中的作用，并指出哪一类 iterator 能走常数时间距离计算。

#include <iterator>
#include <utility>

template<class ForwardIt>
void rotate_one_left(ForwardIt first, ForwardIt last)
{
    using traits = std::iterator_traits<ForwardIt>;
    using value_type = typename traits::value_type;
    using difference_type = typename traits::difference_type;

    difference_type n = std::distance(first, last);
    if (n <= 1) {
        return;
    }

    value_type saved = *first;
    ForwardIt current = first;
    ForwardIt next = first;
    ++next;

    while (next != last) {
        *current = *next;
        ++current;
        ++next;
    }
    *current = std::move(saved);
}

答案要点

value_type 用来保存第一个元素的逻辑值。对 std::vector<int>::iterator、std::list<int>::iterator 和 int*，它是 int；对 std::vector<bool>::iterator，它是 bool。这个临时值脱离原位置，后续移动元素时不会跟随 first 指向的存储变化。

difference_type 用来保存 std::distance(first, last) 的返回值。它表达两个位置之间的相对距离，通常是有符号类型。这里的 n <= 1 是区间长度边界判断；距离计算本身的复杂度取决于 iterator 能力。

reference 通过 *current = *next 和 *current = std::move(saved) 进入写回路径。普通 int iterator 的 reference 是 int& 或 const 变体；std::vector<bool>::iterator 的 reference 是代理访问类型，赋值会修改对应 bit。算法保存的是 value_type，写回时使用解引用结果，因此 proxy 场景仍然可以表达逻辑旋转。

iterator_category 影响 std::distance 的实现路径。std::vector<int>::iterator 和 int* 通常是随机访问 iterator，可以通过减法走常数时间距离计算；std::list<int>::iterator 是双向 iterator，距离计算需要线性遍历；std::vector<bool>::iterator 常见实现提供随机访问能力，但解引用 reference 是代理类型。判断时要把“随机访问能力”和“真实引用”分开。

本章知识点总结

• 统一入口：std::iterator_traits 把不同 iterator 的关联类型整理成算法可查询的统一名字。
• 算法视角：泛型算法通常只持有 iterator，必须通过 traits 获取元素、距离和能力信息。
• value_type：value_type 表示逻辑元素值类型，适合创建临时值、返回值和缓冲区元素。
• 解引用差异：decltype(*it) 描述访问结果，value_type 描述独立值对象，二者在引用和代理场景中会分离。
• difference_type：difference_type 表示位置差异，适合保存 distance 和 advance 使用的相对位移。
• 距离复杂度：距离类型不决定计算成本，iterator_category 或 concepts 才决定能否常数跳转。
• pointer：pointer 表达指针式访问类型，主要服务 operator->、地址适配和连续访问判断。
• reference：reference 表达解引用访问结果，可能是真实引用，也可能是 proxy reference。
• 能力标签：iterator_category 用标签表达旧式 iterator 的可用操作集合，并支持 tag dispatch。
• 指针特化：std::iterator_traits<T*> 让原生指针具备 STL iterator 关联类型，原生数组因此能进入泛型算法。
• 版本边界：C++20 引入 iterator_concept 和更多关联类型工具，传统算法仍大量依赖 iterator_category。
• 判断顺序：分析 iterator 算法时，先看值对象需求，再看解引用语义，再看距离类型，再看能力标签，最后检查指针、代理和版本边界。