迭代器：STL 的粘合剂
理解迭代器类别，从输入迭代器到连续迭代器。学习迭代器算术、begin/end 约定以及迭代器如何将容器与算法连接起来。
迭代器抽象
迭代器是 STL 容器和算法之间的粘合剂。无需为 M 个容器编写 N 个算法（N*M 种实现），STL 定义了一个通用的迭代器接口。每个容器提供迭代器，每个算法在迭代器范围上操作──从而得到 N+M 种可协同工作的实现。
迭代器是一个对象，它：
1. 指向序列中的一个元素
2. 可以解引用（*it）以访问元素
3. 可以递增（++it）以移动到下一个元素
4. 可以比较（it != end）以检测序列末尾
不同的迭代器类别支持不同的操作集，形成从最弱到最强的层次结构。
迭代器类别
C++ 迭代器类别形成一个层次结构（每个级别包含其下所有级别的能力）：
| 类别 | 操作 | 示例容器 |
|---|---|---|
| 输入 | 读取，单遍正向（++、*、==） | istream_iterator |
| 输出 | 写入，单遍正向（++、*=） | ostream_iterator、back_inserter |
| 前向 | 读/写，多遍正向 | forward_list、unordered_set |
| 双向 | 前向 + 反向（--） | list、set、map |
| 随机访问 | 双向 + 跳跃（+n、-n、[]、<） | deque |
| 连续（C++17） | 随机访问 + 元素在内存中相邻 | vector、array、string |
算法声明它们所需的最低类别。std::sort 需要随机访问迭代器，因此它可以与 vector 一起工作，但不能与 list 一起工作（list 提供自己的 sort() 成员函数）。
begin/end 约定
每个 STL 容器都提供 begin() 和 end()──一个半开区间 [begin, end)，其中 end 指向最后一个元素之后的位置。自由函数 std::begin() 和 std::end() 可用于容器、C 数组以及任何提供成员 .begin() 和 .end() 的类型。
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>
int main() {
std::vector<int> vec = {5, 3, 1, 4, 2};
// Member functions
auto first = vec.begin(); // points to 5
auto last = vec.end(); // points past 2
// Free functions — preferred for generic code
auto first2 = std::begin(vec);
auto last2 = std::end(vec);
// Works with C-arrays too
int arr[] = {10, 20, 30};
std::sort(std::begin(arr), std::end(arr));
// const iterators — read-only access
auto cit = vec.cbegin(); // const_iterator
// *cit = 99; // ERROR: cannot modify through const_iterator
// Reverse iterators — iterate backward
for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
std::cout << *rit << ' '; // 2, 4, 1, 3, 5 (reversed, pre-sort was applied)
}
std::cout << '\n';
}迭代器工具：next、prev、advance、distance
#include <iterator>
#include <vector>
#include <list>
#include <iostream>
int main() {
std::vector<int> vec = {10, 20, 30, 40, 50};
// std::next — returns iterator n positions forward (default 1)
auto it = std::next(vec.begin(), 2); // points to 30
std::cout << *it << '\n'; // 30
// std::prev — returns iterator n positions backward
auto it2 = std::prev(vec.end()); // points to 50
std::cout << *it2 << '\n'; // 50
// std::advance — modifies iterator in place (no return)
auto it3 = vec.begin();
std::advance(it3, 3); // now points to 40
std::cout << *it3 << '\n'; // 40
// std::distance — number of increments from first to last
auto d = std::distance(vec.begin(), vec.end()); // 5
std::cout << "Distance: " << d << '\n';
// These work with non-random-access iterators too
std::list<int> lst = {1, 2, 3, 4, 5};
auto lit = std::next(lst.begin(), 2); // O(n) for list, O(1) for vector
std::cout << *lit << '\n'; // 3
auto ld = std::distance(lst.begin(), lst.end()); // O(n) for list
std::cout << "List distance: " << ld << '\n'; // 5
}插入迭代器和流迭代器
插入迭代器允许算法插入到容器中，而不是覆盖现有元素。流迭代器将 I/O 流适配到迭代器接口。
#include <iterator>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
int main() {
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst;
// back_inserter — calls push_back on each assignment
std::copy(src.begin(), src.end(), std::back_inserter(dst));
// dst: {1, 2, 3, 4, 5}
// front_inserter — calls push_front (works with deque, list)
// inserter — calls insert at a given position
// ostream_iterator — write to an output stream
std::copy(dst.begin(), dst.end(),
std::ostream_iterator<int>(std::cout, ", "));
std::cout << '\n'; // 1, 2, 3, 4, 5,
// istream_iterator — read from an input stream
std::istringstream iss("10 20 30 40");
std::vector<int> from_stream(
std::istream_iterator<int>(iss),
std::istream_iterator<int>() // end-of-stream sentinel
);
// from_stream: {10, 20, 30, 40}
}将迭代器递增到 end() 之后或递减到 begin() 之前是未定义行为。对 end() 解引用也是如此──它是一个哨兵，不是一个有效的元素。
一个常见的错误是在未检查 it 是否已经在末尾或接近末尾时写 it + 1：
auto it = vec.end();
++it; // UB — past-the-end
*it; // UB — dereferencing end()在操作之前始终检查迭代器的有效性。使用 std::next 和 std::prev 时进行距离检查，或使用自动处理边界的基于范围的 for 循环。
编写操作序列的泛型函数时：
1. 接受迭代器对（或 C++20 中的范围）而不是特定容器
2. 对迭代器类型使用 typename 或 auto
3. 使用 std::distance 代替减法（减法需要随机访问）
4. 使用 std::next/std::prev 代替 +/- 算术
5. 在 C++20 中，优先使用概念来约束迭代器要求：
template<std::forward_iterator Iter>
auto my_algorithm(Iter first, Iter last) { ... }这确保你的代码能与最广泛的容器一起工作。
- 迭代器将容器与算法解耦──这是 STL 的核心设计原则
- 存在六种迭代器类别：输入、输出、前向、双向、随机访问、连续
- 使用自由函数
std::begin()/std::end()编写兼容容器和 C 数组的泛型代码 std::next、std::prev、std::advance、std::distance跨所有迭代器类别工作- 插入迭代器（
back_inserter、front_inserter、inserter）让算法能够扩展容器 - 永远不要解引用
end()或递增到它之后──两者都是未定义行为
测验 — 检验你的知识
(15 经验值)1. `std::sort` 需要哪种迭代器类别？
2. `std::back_inserter(vec)` 创建了什么？
3. 在 `std::list` 上 `std::distance(first, last)` 的时间复杂度是多少？