C++迭代器：forward与bidirectional区别解析

std::forward_iterator 是单向可读写迭代器，支持++、*、==、!=及复制比较，但不支持--或随机访问；std::bidirectional_iterator在此基础上增加--操作，支持双向遍历，如std::list::iterator；二者为概念分层关系，非类型别名继承。

std::forward_iterator 是单向可读写的迭代器概念

它要求迭代器支持 ++it（前缀递增）、it++（后缀递增）、*it（解引用）、== 和 !=，且必须满足“可复制构造/赋值”和“可比较相等性”的语义。典型代表是 std::forward_list::iterator 和输入流迭代器（如 std::istream_iterator）。

关键限制：不支持 --it 或 it--；不能倒退；一旦递增，原值不可恢复（除非额外保存）。

• 只保证单向遍历：从 begin 到 end，不能回头
• 不要求支持 -> 操作符（但多数实现提供）
• 不要求支持 it + n、it - n 或随机访问
• 对底层容器无所有权或修改要求；只承诺“能读、能走、能判等”

std::bidirectional_iterator 在 forward_iterator 基础上增加反向能力

它继承自 std::forward_iterator，并额外要求支持 --it 和 it--。这意味着你可以前后移动，适合需要双向扫描的算法，比如 std::reverse、std::list::sort。

典型代表是 std::list::iterator、std::set::iterator，以及 C++20 中的 std::deque::iterator（注意：deque 迭代器其实是 random_access_iterator，但它也满足 bidirectional）。

• 必须能“来得去得”：任意位置可前进一格，也可后退一格
• 仍不支持算术运算（如 it + 5）或下标访问（it[3]）
• 所有 bidirectional_iterator 都是 forward_iterator，但反之不成立
• 某些操作（如 std::prev(it)）在 bidirectional 上是 O(1)，在 forward 上是 O(n)

为什么 std::vector::iterator 不是 bidirectional_iterator？

它其实是 std::random_access_iterator —— 这是一个更强的概念，已隐含 bidirectional 和 forward 的所有要求。C++ 标准库中迭代器概念是分层的：input_iterator ⊂ forward_iterator ⊂ bidirectional_iterator ⊂ random_access_iterator ⊂ contiguous_iterator。

所以 std::vector::iterator 能 --、能 +、能 []，但它“属于更高阶概念”，编译器不会把它降级为 bidirectional_iterator 类型别名 —— 类型系统靠 concept 约束，而非别名继承。

• 用 static_assert(std::bidirectional_iterator::iterator>) 会通过（因为满足约束）
• 但 std::vector::iterator 的类型定义本身不是 typedef 自 bidirectional_iterator
• 真正区分行为的是 concept 检查，不是 typedef 名字

实际写泛型代码时怎么选 concept？

取决于你要做的操作。如果你只遍历一次、不需要回头，用 std::forward_iterator 更宽泛，能接受更多容器（如 std::forward_list）。如果要 reverse 或双指针扫描（如 partition），就必须提升到 std::bidirectional_iterator。

错误示例：给一个只接受 bidirectional_iterator 的函数传入 std::forward_list::iterator，编译失败，报错类似 no match for 'operator--'。

template<std::bidirectional_iterator It>
It find_last(It first, It last, const auto& val) {
    while (first != last) {
        --last; // ← 这里要求 --last 合法
        if (*last == val) return last;
    }
    return last;
}

这个函数对 std::list 有效，但无法用于 std::forward_list —— 即便你手动重写成从头扫，逻辑也不同。概念不是“能不能凑合”，而是“接口契约是否完整”。

最容易被忽略的一点：concept 判断的是表达式有效性 + 语义要求（如可比较、可复制），不是看类有没有叫 operator-- 的成员函数。有些自定义迭代器重载了 -- 但不满足可交换性或可复制性，依然不算 bidirectional_iterator。