C++ 迭代器与 traits

迭代器是 STL 的"胶水"——算法不认容器，只认迭代器；容器只要暴露迭代器，就能对接整套算法库。这套设计的关键，是给迭代器分类别（category），让算法按能力分派到最优实现。traits 则是"编译期问迭代器属性"的接口，是泛型代码的基础设施。C++20 用 concepts 重写了这套体系，引入了 sentinel 和 contiguous 迭代器，让迭代器能力和 ranges 库严丝合缝。这篇把迭代器类别、traits、sentinel、自定义迭代器讲清楚。concepts 的语法见 C++ Concept，ranges 见 C++ Ranges 完全指南。

迭代器是一种"泛型指针"

迭代器抽象了"指向序列中某个元素、能前进、能解引用"这一组操作。指针是最原始的迭代器：

int a[5] = {1, 2, 3, 4, 5};
int* p = a;              // pointer as iterator
*p;                      // 1, dereference
++p;                     // advance
p[2];                    // 5, random access

std::vector<int>::iterator 在行为上几乎等同于 int*；而 std::list 的迭代器只能 ++/--/解引用，不能 [] 或 +n——因为链表不支持随机跳。迭代器类别就是在描述这种能力差异。

迭代器类别（category）

C++20 之前用"迭代器分类"五个层级（标签类 std::input_iterator_tag 等）；C++20 改用 concepts 描述能力，并新增了 contiguous。能力是逐层递增的：

类别 (C++20 concept)	能力	典型代表
`input_iterator`	单遍读：`*it` 读、`++it` 前进、`==` 比较	`istream_iterator`
`output_iterator`	单遍写：`*it = x`、`++it`	`back_insert_iterator`
`forward_iterator`	多遍前向读：可多次遍历、可拷贝保留位置	`forward_list::iterator`、`unordered_map::iterator`
`bidirectional_iterator`	forward + `--it` 后退	`list::iterator`、`set/map::iterator`
`random_access_iterator`	bidirectional + `it + n`、`it[n]`、`<` 比较	`vector::iterator`、`deque::iterator`、指针
`contiguous_iterator`	random_access + 元素在内存中连续（`it[n]` 等价于 `(it + n)`，且 `&it + n == &*it[n]`）	`vector::iterator`、`array::iterator`、指针

能力越强，能用的算法越多、越快：

std::sort 要求 random_access——所以不能 std::sort 一个 list（链表只能用成员函数 list::sort）。
std::find 只要 input——任何能遍历的都能用。
std::binary_search 要求 forward 且序列有序，但真正高效需要 random_access 才能随机跳。

std::list<int> l = {3, 1, 2};
// std::sort(l.begin(), l.end());   // ERROR: list iterator is only bidirectional
l.sort();                            // OK: list has its own O(n log n) sort

std::vector<int> v = {3, 1, 2};
std::sort(v.begin(), v.end());       // OK: random access

output 迭代器与 inserter

output 迭代器是"只写"的，最常见的是各种 inserter，把"写入"转成"插入容器"：

1
2
3

std::vector<int> dst;
std::copy(src.begin(), src.end(), std::back_inserter(dst));   // push_back each
// back_inserter(dst) returns a back_insert_iterator (output iterator)

back_inserter/front_inserter/inserter 让算法能向"未知大小"的容器输出，无需预先 reserve。这也是 ranges 的 std::ranges::to（C++23）普及前，把视图物化成容器的标准手段。

iterator_traits：编译期问迭代器

算法是泛型的，需要知道"这个迭代器指向的是什么类型、差值类型是什么、属于哪个类别"——这些信息由 std::iterator_traits<Iter> 提供。它是迭代器的"类型档案"：

template<typename Iter>
void algo(Iter first, Iter last) {
    // 这个迭代器指向的元素类型
    using value_type = typename std::iterator_traits<Iter>::value_type;
    // 两个迭代器之差的类型（通常是 ptrdiff_t）
    using difference_type = typename std::iterator_traits<Iter>::difference_type;
    // 迭代器类别
    using category = typename std::iterator_traits<Iter>::iterator_category;

    value_type sum{};
    for (auto it = first; it != last; ++it) sum += *it;
}

iterator_traits 对所有迭代器类型（含裸指针）都有特化，所以算法无需特判指针：

// 对裸指针 T*，traits 退化成：
template<typename T>
struct std::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;   // C++20 前
    // C++20: contiguous_iterator_tag
};

这就是为什么 std::sort(arr, arr + 5) 能直接对 C 数组工作——指针经 traits 被识别为 random_access（C++20 起 contiguous）迭代器。

五个关联 typedef

一个完整的迭代器（C++20 前）需要提供这五个 typedef，算法通过 traits 取它们：

typedef	含义	典型值
`value_type`	指向元素的类型（去 const）	`int`
`difference_type`	两个迭代器差值类型	`std::ptrdiff_t`
`pointer`	"指向元素的指针"类型	`int*`
`reference`	解引用返回的引用类型	`int&`
`iterator_category`	迭代器类别标签	`std::forward_iterator_tag`

C++20 起，concepts 通过检测 iter_value_t/iter_difference_t/iter_reference_t 等别名来推断这些，新写迭代器不再需要手填五个 typedef——只要提供 operator*/operator++/operator== 等操作，concept 会自动推导能力。但自定义迭代器仍建议显式提供 iterator_category 和 value_type，保证与旧式算法（std::reverse_iterator、某些 trait 探测）兼容。

类别分派：用 tag 选最优实现

traits 的核心用途是按类别分派到不同实现。std::advance(it, n) 是教科书例子：random_access 直接 it += n（O(1)），其他类别只能 ++it n 次（O(n)）：

namespace detail {
template<typename Iter>
void advance_impl(Iter& it, typename std::iterator_traits<Iter>::difference_type n,
                  std::input_iterator_tag) {
    while (n--) ++it;                    // forward/input: only ++, n>=0
}
template<typename Iter>
void advance_impl(Iter& it, typename std::iterator_traits<Iter>::difference_type n,
                  std::bidirectional_iterator_tag) {
    if (n >= 0) while (n--) ++it;
    else        while (n++) --it;        // bidirectional: also --
}
template<typename Iter>
void advance_impl(Iter& it, typename std::iterator_traits<Iter>::difference_type n,
                  std::random_access_iterator_tag) {
    it += n;                             // random access: O(1)
}
}

template<typename Iter>
void advance(Iter& it, typename std::iterator_traits<Iter>::difference_type n) {
    detail::advance_impl(it, n,
        typename std::iterator_traits<Iter>::iterator_category{});   // tag dispatch
}

传一个 tag 对象，重载决议自动选出匹配的实现——这就是"用类型在编译期做分支"。现代 C++ 更常用 if constexpr + concept 做同样的事，但 tag 分派在标准库和旧代码里随处可见，理解它有助于读懂实现。

C++20 等价写法：

template<typename Iter>
void advance(Iter& it, std::iter_difference_t<Iter> n) {
    if constexpr (std::random_access_iterator<Iter>) it += n;
    else if constexpr (std::bidirectional_iterator<Iter>) {
        if (n >= 0) while (n--) ++it; else while (n++) --it;
    } else { while (n--) ++it; }
}

C++20：sentinel 与非对称区间

C++20 之前，[begin, end) 的两端必须是同类型迭代器。这限制了一些场景：C 字符串的 end 是"遇到 \0 就停"，而不是某个具体指针；无限生成器的 end 是"永不停止"。C++20 引入 sentinel——end 可以是和 begin 不同类型的"哨兵"，只要它能和迭代器比较相等：

// 一个"遇到 0 就停"的 sentinel
struct NullTerminated {
    bool operator==(const char* p) const { return *p == '\0'; }
};

const char* s = "hello";
// [s, NullTerminated{}) — end 是个 sentinel，不是指针
for (auto it = s; it != NullTerminated{}; ++it)
    std::println("{}", *it);

std::ranges 大量用 sentinel：std::istream_view、std::views::take(n) 的终止条件、std::counted_iterator 配 default_sentinel。sentinel 让"区间"的表达力从"两个同型指针"扩展到"任何能定义终止条件的序列"，这是 ranges 库能优雅处理无限流和 IO 流的基础。

自定义迭代器

写一个自定义迭代器，要提供"算法期望的最小操作集"，并声明类别让算法选对实现。下面是个 forward 迭代器的最小骨架（C++20 风格，配合 concept 推导）：

class IntSeqIterator {
    int cur_;
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type        = int;
    using difference_type   = std::ptrdiff_t;
    using pointer           = const int*;
    using reference         = int;

    IntSeqIterator(int start) : cur_(start) {}
    int operator*() const { return cur_; }
    IntSeqIterator& operator++() { ++cur_; return *this; }
    IntSeqIterator operator++(int) { auto t = *this; ++cur_; return t; }
    bool operator==(const IntSeqIterator& o) const = default;
};

// 可用于任何只要 forward 的算法
std::vector<int> v(IntSeqIterator(0), IntSeqIterator(5));  // {0,1,2,3,4}

C++20 后，更推荐的做法是只提供操作、用 std::iterator_traits 特化或 concept 自动推导，并在类里加 using iterator_concept = std::forward_iterator_tag;（注意是 iterator_concept，C++20 新增，与旧的 iterator_category 并存）。旧代码仍读 iterator_category，新代码读 iterator_concept，自定义迭代器两者都填最稳妥。

proxy 迭代器（如 std::vector<bool> 的迭代器、std::bitset）是个进阶难点：operator* 返回的不是真引用而是个代理对象。C++20 用 std::indirectly_readable / std::indirectly_writable 和 std::iter_reference_t 正确支持了 proxy 迭代器，旧式 traits 的 reference = T& 假设在这里会失效——写代理迭代器时 reference 要填代理类型。

常用工具迭代器

迭代器	作用
`back_insert_iterator` (`back_inserter`)	`*it = x` → `container.push_back(x)`
`front_insert_iterator` (`front_inserter`)	`*it = x` → `container.push_front(x)`
`insert_iterator` (`inserter`)	`*it = x` → 在指定位置 `insert`
`istream_iterator<T>`	从 `istream` 读取 `T`，到 EOF 终止
`ostream_iterator<T>`	向 `ostream` 写 `T`，可加分隔符
`move_iterator`	`*it` 变成右值，用于 move 出区间
`reverse_iterator`	反转方向（`++` 变后退）
`counted_iterator` (C++20)	计数到 n 终止，配 sentinel 用
`default_sentinel` (C++20)	通用哨兵

// move 整个区间到另一个容器（move 而非拷贝）
std::vector<std::string> src = {"a", "b", "c"};
std::vector<std::string> dst(
    std::make_move_iterator(src.begin()),
    std::make_move_iterator(src.end()));   // src elements moved-from

一句话总结

迭代器是 STL 的统一接口，其能力被分成 input/forward/bidirectional/random_access/contiguous 几个层级，决定能调用哪些算法；iterator_traits 是"编译期查迭代器档案"的标准入口，让泛型算法能取到值类型、差值类型、类别并据此分派最优实现。C++20 用 concepts 重写了这套体系、用 sentinel 打破了"两端必须同型"的限制，让迭代器既保留了几十年的抽象模型，又足以支撑现代 ranges 库处理无限流、IO 流和代理迭代器。理解类别与 traits，是读懂标准库算法实现、写出可对接 ranges 的自定义容器的必修课。