C++ / a working model

67 / 80   ·   C++20   ·   约 10 分钟

迭代器：能力类别、范围与有效性

先记住这句话

迭代器类别描述可以执行哪些操作以及相应复杂度，不负责延长对象生命周期。区分单趟输入、多趟前向、双向、随机访问和连续迭代器，再单独检查容器修改导致的失效，才能正确组合算法。

本篇内容
  1. 类别是算法可用能力的契约
  2. 半开区间与算法成本
  3. 有效、可解引用和仍是同一业务元素
  4. 运行示例
  5. 动手练习

类别是算法可用能力的契约

输入迭代器支持读取和前进，但可能只有单趟语义，例如流输入；复制一个迭代器不意味着复制了可独立回放的数据源。前向迭代器增加多趟保证，双向迭代器再增加递减，随机访问迭代器支持常数时间跳转和距离计算。输出迭代器描述写入能力，是另一条能力维度，不是“比输入更高级”。

连续迭代器在随机访问基础上要求元素对应连续内存位置。普通 vector 的迭代器满足连续要求，deque 只有随机访问保证，list 是双向迭代器。示例用 C++20 concepts 表达这些要求；不要通过 sizeof、某个实现的内部字段或“看起来像指针”识别类别。

半开区间与算法成本

多数算法接受 [first,last)：first 指向首元素，last 是不包含的边界。空区间允许 first 等于 last，但 end 不可解引用；前进也不能超过有效边界。两个来自不同容器的迭代器通常不能组合成一个范围，即使元素类型相同、地址看起来接近。

std::distance 对随机访问迭代器是常数时间，对普通 list 迭代器则必须逐步前进。std::next 提供统一写法，不会自动把线性操作变成常数。现代 ranges 允许迭代器与哨兵是不同类型，用能力约束替代假设“所有 end 都长得一样”，但仍要求范围本身有效。

有效、可解引用和仍是同一业务元素

迭代器失效由容器及具体修改决定，与类别高低无关。vector 重分配会使所有迭代器失效，list 插入则不会。迭代器有效也不保证可解引用，end 就是典型反例；排序后位置仍有效，也可能已装着另一个值，因此业务身份与存储位置必须分开。

边遍历边删除时，使用 it = container.erase(it) 接收后继；未删除时才递增。示例删除偶数并验证结果，避免删除后再对失效迭代器执行 ++。对 vector 反复单个 erase 可能产生平方成本，批量筛选更适合 erase-remove；该循环展示的是有效性协议，而非所有容器上的最佳性能。

容易答错的地方

  • const_iterator 只限制通过它修改元素，不保证容器不会变化，也不让失效迭代器恢复有效。
  • 迭代器仍有效、迭代器可解引用、迭代器仍对应原业务记录是三个不同命题。

运行一个例子

最低标准 C++20 · 完整程序 · 下载 .cpp

#include <cassert>
#include <deque>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>

int main() {
    static_assert(std::contiguous_iterator<std::vector<int>::iterator>);
    static_assert(std::random_access_iterator<std::deque<int>::iterator>);
    static_assert(!std::contiguous_iterator<std::deque<int>::iterator>);
    static_assert(std::bidirectional_iterator<std::list<int>::iterator>);
    static_assert(!std::random_access_iterator<std::list<int>::iterator>);

    std::vector<int> values{1, 2, 3, 4, 5};
    for (auto it = values.begin(); it != values.end();) {
        if (*it % 2 == 0) {
            it = values.erase(it);
        } else {
            ++it;
        }
    }
    assert((values == std::vector<int>{1, 3, 5}));
    std::list<int> nodes{4, 8, 12};
    auto a = nodes.begin();
    auto b = a;
    ++b;
    assert(*a == 4 && *b == 8);
    assert(std::distance(nodes.begin(), nodes.end()) == 3);
    std::cout << values[0] << ' ' << values[1] << ' ' << values[2] << '\n';
}

在本地编译

g++ -std=c++20 -Wall -Wextra -Wpedantic -pthread stl-iterators.cpp -o example && ./example

预期结果

1 3 5

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

函数先对输入迭代器区间调用 distance 计算长度，再遍历同一来源读取所有值。它能用于 istream_iterator 吗？如何修正接口？

查看参考答案

不能假设可以。istream_iterator 是单趟输入，distance 的递增会消费共享输入流，保存起点副本不能回放已经读过的值。如果确实需要两遍，要求至少 forward_iterator；若希望支持流输入，就单遍处理并同时计数，或先把数据读入 vector，再在缓存上重复遍历。

继续查证

标准草案链接会随工作草案更新；本文版本标记对应示例最低要求，不表示草案中的所有新规则都适用于旧标准。

回到目录