C++ 迭代器：范围、能力与失效规则

迭代器把“怎样定位元素”与“对元素执行什么算法”分开。它可以像指针，但不保证就是地址；算法必须使用该迭代器支持的操作。类型正确也不保证位置有效，越界、寿命结束和容器修改都可能使它失效。

本页采用C++17的传统迭代器分类；C++20的迭代器概念和ranges是在此基础上的进一步组织。

1. 半开范围与遍历

容器通常用 [begin(), end())表示全部元素：begin()指向首项，end()表示越过最后一项的位置。空容器两者相等，不能解引用 end()。

#include <cassert>
#include <vector>

int main()
{
    std::vector<int> values{1, 2, 3, 4, 5};
    int sum = 0;
    for (auto iterator = values.begin(); iterator != values.end(); ++iterator)
        sum += *iterator;
    assert(sum == 15);

    auto iterator = values.begin();
    *iterator = 10;
    const auto fixedPosition = values.begin();
    *fixedPosition = 20; // const的是迭代器对象，元素仍可写。
    auto readOnly = values.cbegin();
    ++readOnly;         // 只读元素不等于位置不能移动。
    assert(*readOnly == 2);
}

const_iterator约束经它访问的元素不可修改；const iterator约束迭代器对象自身不可改变。两者不要混淆。范围for的 auto value复制元素，auto& value借用可写元素，const auto& value借用只读元素，也要按用途选择。

2. 五种传统能力类别

类别	主要能力	典型例子/限制
输入迭代器	顺序读取和递增；可能只有单遍保证。	istream_iterator读取流；复制的迭代器不代表能独立回放输入。
输出迭代器	把值写入输出位置并推进。	back_insert_iterator；不要求可读取所指值。
前向迭代器	输入能力加多遍保证，可从保存的位置再次遍历。	forward_list，无递减。
双向迭代器	前向能力加 --。	list、map；不能因此使用 it + n。
随机访问迭代器	常数时间跳转、距离与顺序比较。	vector、array、deque；随机访问不等于全部元素物理连续。

原来的“输入=只读、输出=只写”只能提示用途，不能替代单遍/多遍和操作集合等要求。常量与可写性也是另一条维度：例如 vector<int>::const_iterator仍能随机访问。

普通对象指针也可作为相应范围的迭代器，但指针运算只能在同一数组及其尾后位置等允许范围内进行。C++工作草案：迭代器要求

3. distance、advance、next与prev

#include <cassert>
#include <forward_list>
#include <iterator>
#include <list>

int main()
{
    std::forward_list<int> singly{10, 20, 30};
    auto iterator = singly.begin();
    std::advance(iterator, 2);
    assert(*iterator == 30);
    assert(std::distance(singly.begin(), singly.end()) == 3);

    std::list<int> doubly{1, 2, 3};
    const auto last = std::prev(doubly.end());
    assert(*last == 3);
    assert(*std::next(doubly.begin()) == 2);
}

advance修改传入的迭代器；next/prev返回移动后的副本。它们不会自动检查容器边界：不能从空容器的末端取 prev，也不能把前向迭代器用负步数往回移。随机访问迭代器的跳转/距离可为常数时间，链表通常需要逐项走；使用统一接口不意味着统一复杂度。

std::sort要求随机访问范围，所以 list不能直接传给它；应使用 list::sort。是否支持 ++与是否支持某个算法是两个问题。

4. 修改容器后的失效

操作	要注意什么
vector重新分配	原迭代器、引用、指针全部失效；reserve也可能触发。
vector插入/删除且不重分配	插入/删除位置及其后的相关迭代器等可能失效，末端也会改变。
list插入节点	通常保留既有元素的迭代器；删除仅使被删元素相关访问失效。
map/set删除	被删除元素的迭代器失效；键排序约束仍必须保持。
unordered容器rehash	迭代器失效；对元素的引用/指针有不同规则，不能一概而论。

按容器的具体成员函数核对规则；把 end()保存下来后持续往vector追加，也可能使用已经失效的末端。删除循环常用 iterator = container.erase(iterator)接住返回的新位置，而不是删除后再递增旧位置。

反向迭代器和插入迭代器能改变遍历/写入接口，见适配器。完整容器选择与容量边界见容器，算法所需前提见算法。