Ch 5: 迭代器与算法

本章目标

理解 C++ 迭代器体系
掌握常用算法
学会 lambda 在算法中的使用
理解 C++20 Ranges

5.1 Python 迭代器协议

Python 的迭代器协议是 Python 灵活性的核心：

# Python - __iter__ 和 __next__ 协议
class Counter:
    def __init__(self, n):
        self.n = n
        self.i = 0

    def __iter__(self):
        return self

    def __next__(self):
        if self.i < self.n:
            result = self.i
            self.i += 1
            return result
        raise StopIteration

# 使用
for i in Counter(5):
    print(i)  # 0, 1, 2, 3, 4

# 生成器（更简洁的实现）
def counter(n):
    i = 0
    while i < n:
        yield i
        i += 1

# itertools
import itertools
for i in itertools.count(start=0, step=1):
    if i >= 5: break
    print(i)

Python 的迭代器优势

# 惰性求值 - 只在需要时计算
def infinite_generator():
    i = 0
    while True:
        yield i
        i += 1

# map/filter 也是惰性的
result = map(lambda x: x**2, range(1000000))
# 不立即计算，只是返回一个迭代器

# 可以无限序列
evens = (x for x in infinite_generator() if x % 2 == 0)

5.2 C++ 迭代器体系

C++ 迭代器体系比 Python 更复杂，但更接近硬件：

#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5};

// 迭代器类型
// 输入迭代器 → 前向迭代器 → 双向迭代器 → 随机访问迭代器
//                          ↓
//                    双向 + 输出 → 连续迭代器

// begin/end
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";
}

// C++11 范围 for
for (int x : v) {
    std::cout << x << " ";
}

// C++11 auto
for (const auto& x : v) {  // const 避免拷贝，& 避免拷贝
    std::cout << x << " ";
}

迭代器运算

std::vector<int> v = {10, 20, 30, 40, 50};
auto it = v.begin();

// 前进/后退
++it;      // it 指向 20
--it;      // it 指向 10
it += 2;   // it 指向 30

// 距离
auto it2 = v.begin() + 4;
std::ptrdiff_t dist = it2 - it;  // 4

// 解引用和访问
int val = *it;      // 10
int val2 = it[2];   // 30，等价于 *(it + 2)

迭代器失效

修改容器后，迭代器可能失效：

std::vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin() + 2;  // 指向 3

// ❌ 危险：插入可能导致迭代器失效
v.insert(v.begin(), 0);  // 重新分配，it 失效！

// ✅ 正确：重新获取迭代器
it = v.begin() + 3;  // 重新获取
v.erase(it);         // 现在安全

// 删除元素时也要小心
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) {
        it = v.erase(it);  // erase 返回下一个迭代器
    } else {
        ++it;
    }
}

5.3 map/filter/reduce

Python 实现

from functools import reduce
import itertools

nums = [1, 2, 3, 4, 5]

# map - 转换
squares = list(map(lambda x: x**2, nums))
# [1, 4, 9, 16, 25]

# filter - 过滤
evens = list(filter(lambda x: x % 2 == 0, nums))
# [2, 4]

# reduce - 累积
total = reduce(lambda a, b: a + b, nums, 0)
# 15

# 列表推导（更 Pythonic）
squares = [x**2 for x in nums]
evens = [x for x in nums if x % 2 == 0]

# 链式
result = [x**2 for x in nums if x**2 > 10]
# [16, 25]

# itertools 链式
result = list(itertools.takewhile(lambda x: x < 20,
    map(lambda x: x**2,
    filter(lambda x: x % 2 == 0, nums))))

C++ 标准算法

#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>

std::vector<int> nums = {1, 2, 3, 4, 5};

// transform - map
std::vector<int> squares(nums.size());
std::transform(nums.begin(), nums.end(), squares.begin(),
    [](int x) { return x * x; });

// remove_if + erase - filter
std::vector<int> evens = nums;
evens.erase(std::remove_if(evens.begin(), evens.end(),
    [](int x) { return x % 2 != 0; }), evens.end());

// accumulate - reduce
int total = std::accumulate(nums.begin(), nums.end(), 0,
    [](int a, int b) { return a + b; });

// count_if
int even_count = std::count_if(nums.begin(), nums.end(),
    [](int x) { return x % 2 == 0; });

// find_if
auto it = std::find_if(nums.begin(), nums.end(),
    [](int x) { return x > 3; });

算法详解

#include <algorithm>
#include <vector>

std::vector<int> nums = {5, 2, 8, 1, 9, 3, 7, 1, 4};

// sort - 排序
std::sort(nums.begin(), nums.end());  // 升序
std::sort(nums.begin(), nums.end(), std::greater<int>());  // 降序
std::sort(nums.begin(), nums.end(),
    [](int a, int b) { return a > b; });  // Lambda 降序

// stable_sort - 稳定排序（保持相等元素的相对顺序）
std::stable_sort(nums.begin(), nums.end());

// reverse - 反转
std::reverse(nums.begin(), nums.end());

// unique - 去重（需要先排序）
nums.erase(std::unique(nums.begin(), nums.end()), nums.end());

// fill - 填充
std::fill(nums.begin(), nums.end(), 0);

// copy_if - 条件复制
std::vector<int> result;
std::copy_if(nums.begin(), nums.end(), std::back_inserter(result),
    [](int x) { return x > 5; });

// partition - 分区
auto mid = std::partition(nums.begin(), nums.end(),
    [](int x) { return x > 5; });

5.4 Lambda 表达式

Python Lambda

# Python Lambda
square = lambda x: x ** 2
add = lambda a, b: a + b

# map/filter/reduce
list(map(lambda x: x**2, nums))
list(filter(lambda x: x > 3, nums))

# 带捕获的 lambda（闭包）
factor = 2
list(map(lambda x: x * factor, nums))

C++ Lambda

// 基本语法
auto square = [](int x) { return x * x; };
auto add = [](int a, int b) { return a + b; };

// 调用
int s = square(5);  // 25
int sum = add(3, 4);  // 7

// 捕获
int factor = 2;
auto scaled = [factor](int x) { return x * factor; };

// 捕获列表
// []      - 不捕获
// [=]     - 按值捕获所有
// [&]     - 按引用捕获所有
// [x]     - 按值捕获 x
// [&x]    - 按引用捕获 x
// [=, &x] - 默认按值，x 按引用

Lambda 在算法中的应用

#include <algorithm>
#include <vector>

std::vector<int> nums = {1, 2, 3, 4, 5};

// 排序
std::sort(nums.begin(), nums.end(),
    [](int a, int b) { return a > b; });

// 自定义比较器
struct Person {
    std::string name;
    int age;
};

std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}};
std::sort(people.begin(), people.end(),
    [](const Person& a, const Person& b) {
        return a.age < b.age;  // 按年龄排序
    });

// for_each
std::for_each(nums.begin(), nums.end(),
    [](int x) { std::cout << x << " "; });

// all_of / any_of / none_of
bool all_positive = std::all_of(nums.begin(), nums.end(),
    [](int x) { return x > 0; });

5.5 C++20 Ranges

Ranges 是 C++20 最重要的特性之一：

#include <vector>
#include <ranges>

std::vector<int> nums = {1, 2, 3, 4, 5};

// 惰性求值，不创建中间容器
auto evens = nums | std::views::filter([](int x) { return x % 2 == 0; });
auto squares = evens | std::views::transform([](int x) { return x * x; });

for (int n : squares) {
    std::cout << n << " ";  // 4 16
}

// 链式操作
auto result = nums
    | std::views::filter([](int x) { return x % 2 == 0; })
    | std::views::transform([](int x) { return x * x; })
    | std::views::take(2);  // 取前两个

// iota - 类似 Python range
for (int i : std::views::iota(1, 6)) {  // 1,2,3,4,5
    std::cout << i << " ";
}

Ranges 视图操作

视图	Python 等价	说明
`filter(pred)`	`filter(pred, iterable)`	过滤
`transform(func)`	`map(func, iterable)`	转换
`take(n)`	`itertools.islice(it, n)`	取前 n 个
`drop(n)`	`itertools.islice(it, n, None)`	跳过前 n 个
`reverse`	`reversed(iterable)`	反转
`all`	`all(iterable)`	全满足

// drop - 跳过
for (int n : nums | std::views::drop(2)) {  // 3, 4, 5
    std::cout << n << " ";
}

// take + reverse
for (int n : nums | std::views::take(3) | std::views::reverse) {  // 5, 4, 3
    std::cout << n << " ";
}

// 组合
auto pipeline = nums
    | std::views::filter([](int x) { return x > 1; })
    | std::views::transform([](int x) { return x * 2; })
    | std::views::take(3);

5.6 常用算法速查

Python	C++	说明
`max(lst)`	`std::max_element`	最大值
`min(lst)`	`std::min_element`	最小值
`sum(lst)`	`std::accumulate`	求和
`sorted(lst)`	`std::sort`	排序
`reversed(lst)`	`std::reverse`	反转
`enumerate(lst)`	`std::views::enumerate` (C++23)	带索引
`zip(a, b)`	`std::views::zip` (C++23)	组合
`all(pred, lst)`	`std::all_of`	全满足
`any(pred, lst)`	`std::any_of`	任一满足
`filter, map`	`std::copy_if, std::transform`	过滤/转换

章节总结

C++ 迭代器是泛型编程的基础
std::algorithm 提供丰富的算法
Lambda 是连接数据和算法的桥梁
C++20 Ranges 让链式操作更直观
Ranges 是惰性求值，不创建中间容器

下章预告：ch06 文件与 I/O 操作。