Ch 18: 迭代器和标准库算法

本章目标

• 深入理解迭代器的类别和概念
• 熟练使用常用 std::algorithm 函数
• 学会使用算法而非手写循环
• 理解谓词和投影的使用
• 掌握 C++20 范围库的链式操作

18.1 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

# 内置迭代器
list(map(lambda x: x**2, [1,2,3]))  # [1, 4, 9]
[x**2 for x in [1,2,3]]             # [1, 4, 9]
filter(lambda x: x % 2 == 0, range(10))  # 迭代器

Python 的高阶函数

# Python 的 filter/map/reduce
from functools import reduce

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

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

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

# reduce - 累积
sum_of_squares = reduce(lambda acc, x: acc + x**2, numbers, 0)  # 55

# sorted - 排序
sorted(numbers, reverse=True)  # [5, 4, 3, 2, 1]
sorted(numbers, key=lambda x: -x)  # 逆排序

# min/max
max(numbers, key=lambda x: -x)  # 最小
min(numbers)  # 1

18.2 C++ 迭代器类别

迭代器类别层次

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

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::list<int> lst = {1, 2, 3, 4, 5};

    // vector 的迭代器是随机访问迭代器
    auto vit = v.begin();
    vit + 2;     // 支持算术运算
    vit - 2;     // 支持减法
    vit[3];      // 支持下标
    vit - v.begin();  // 支持距离计算

    // list 的迭代器是双向迭代器
    auto lit = lst.begin();
    ++lit;        // 支持前向
    --lit;        // 支持后向
    // lit + 2;   // ❌ 不支持算术运算！

    // 迭代器类别
    // InputIterator   - 输入，只读，单遍
    // OutputIterator  - 输出，只写，单遍
    // ForwardIterator - 前向，可读写，多遍
    // BidirectionalIterator - 双向，支持 --
    // RandomAccessIterator - 随机访问，支持 + - []
    // ContiguousIterator - 连续内存（C++20）

    return 0;
}

迭代器失效

#include <vector>
#include <iostream>

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

    // 获取迭代器
    auto it = v.begin() + 2;  // 指向 3

    // ❌ vector 插入/删除会导致迭代器失效
    v.insert(v.begin(), 0);  // 可能重新分配内存！
    // it 现在是悬空迭代器，使用它会导致未定义行为

    // ✅ 正确做法：修改后重新获取迭代器
    it = v.begin() + 3;  // 重新获取

    // list 的迭代器在删除元素时会失效（被删除的那个）
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto lit = lst.begin();
    ++lit;  // 指向 2
    lst.erase(lit);  // 删除 2，lit 失效
    // lit 不能继续使用，但其他迭代器仍然有效

    return 0;
}

迭代器辅助函数

#include <vector>
#include <iterator>
#include <iostream>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};

    // advance - 前进 N 步（通用）
    auto it = v.begin();
    std::advance(it, 3);  // 指向 40
    std::cout << "3rd after begin: " << *it << "\n";

    // next - 返回前进后的迭代器（不改变原迭代器）
    auto it2 = std::next(v.begin(), 4);  // 指向 50
    std::cout << "4th: " << *it2 << "\n";

    // prev - 返回后退后的迭代器
    auto it3 = std::prev(v.end(), 2);  // 指向 40
    std::cout << "2nd from end: " << *it3 << "\n";

    // distance - 计算距离
    std::ptrdiff_t dist = std::distance(v.begin(), v.end());  // 5

    // 双向迭代器也能用 advance
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto lit = lst.begin();
    std::advance(lit, 2);  // 指向 3

    return 0;
}

18.3 std::algorithm 常用算法

查找类算法

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    // find - 查找第一个匹配的元素
    auto it = std::find(v.begin(), v.end(), 5);
    if (it != v.end()) {
        std::cout << "Found 5 at index " << (it - v.begin()) << "\n";
    }

    // find_if - 查找第一个满足条件的
    auto it2 = std::find_if(v.begin(), v.end(),
        [](int x) { return x > 4; });
    std::cout << "First > 4: " << *it2 << "\n";  // 5

    // find_if_not - 查找第一个不满足条件的
    auto it3 = std::find_if_not(v.begin(), v.end(),
        [](int x) { return x < 5; });
    std::cout << "First not < 5: " << *it3 << "\n";  // 5

    // count - 统计出现次数
    int ones = std::count(v.begin(), v.end(), 1);
    std::cout << "Count of 1: " << ones << "\n";  // 2

    // count_if - 统计满足条件的数量
    int evens = std::count_if(v.begin(), v.end(),
        [](int x) { return x % 2 == 0; });
    std::cout << "Count of evens: " << evens << "\n";  // 3

    return 0;
}

条件判断算法

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> v = {2, 4, 6, 8, 10};

    // all_of - 所有元素都满足条件
    bool all_even = std::all_of(v.begin(), v.end(),
        [](int x) { return x % 2 == 0; });
    std::cout << "All even: " << std::boolalpha << all_even << "\n";  // true

    // any_of - 任意一个满足条件
    bool any_negative = std::any_of(v.begin(), v.end(),
        [](int x) { return x < 0; });
    std::cout << "Any negative: " << any_negative << "\n";  // false

    // none_of - 所有都不满足条件
    bool none_negative = std::none_of(v.begin(), v.end(),
        [](int x) { return x < 0; });
    std::cout << "None negative: " << none_negative << "\n";  // true

    // 实际应用：验证数据
    std::vector<int> ages = {25, 30, 35, 40};
    bool all_valid = std::all_of(ages.begin(), ages.end(),
        [](int age) { return age >= 0 && age <= 150; });

    return 0;
}

变形算法（修改元素）

#include <vector>
#include <algorithm>
#include <iostream>

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

    // transform - 转换所有元素
    std::vector<int> squares;
    std::transform(v.begin(), v.end(), std::back_inserter(squares),
        [](int x) { return x * x; });
    // squares = {1, 4, 9, 16, 25}

    // 就地转换
    std::transform(v.begin(), v.end(), v.begin(),
        [](int x) { return x * 2; });
    // v = {2, 4, 6, 8, 10}

    // 两个范围操作
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {10, 20, 30};
    std::vector<int> sums;
    std::transform(a.begin(), a.end(), b.begin(), std::back_inserter(sums),
        [](int x, int y) { return x + y; });
    // sums = {11, 22, 33}

    // for_each - 对每个元素执行操作
    std::for_each(v.begin(), v.end(),
        [](int x) { std::cout << x << " "; });
    std::cout << "\n";

    return 0;
}

删除算法

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    // ❌ 常见错误：直接调用 remove
    // v.remove_if(...)  // ❌ vector 没有这个成员函数！

    // ✅ 正确方式：remove + erase 惯用法
    v.erase(
        std::remove_if(v.begin(), v.end(),
            [](int x) { return x % 2 == 0; }),
        v.end());
    // v = {1, 3, 5, 7, 9}

    // 重建 vector
    v = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    // 另一种方式：copy_if 到新容器
    std::vector<int> filtered;
    std::copy_if(v.begin(), v.end(), std::back_inserter(filtered),
        [](int x) { return x % 2 != 0; });
    // filtered = {1, 3, 5, 7, 9}

    // unique - 删除连续重复元素（需要先排序）
    v = {1, 1, 2, 2, 2, 3, 3, 1, 1};
    v.erase(std::unique(v.begin(), v.end()), v.end());
    // v = {1, 2, 3, 1}

    // 删除所有特定值
    v = {1, 2, 3, 2, 4, 2, 5};
    v.erase(std::remove(v.begin(), v.end(), 2), v.end());
    // v = {1, 3, 4, 5}

    std::cout << "Result: ";
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";

    return 0;
}

排序算法

#include <vector>
#include <algorithm>
#include <iostream>
#include <random>

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    // sort - 升序
    std::sort(v.begin(), v.end());
    // v = {1, 2, 3, 4, 5, 6, 7, 8, 9}

    // 降序
    std::sort(v.begin(), v.end(), std::greater<int>());
    // v = {9, 8, 7, 6, 5, 4, 3, 2, 1}

    // 自定义比较函数
    std::sort(v.begin(), v.end(),
        [](int a, int b) { return a > b; });  // 降序

    // 稳定排序（保持相等元素的相对顺序）
    std::vector<std::pair<int, char>> data = {{1, 'a'}, {2, 'b'}, {1, 'c'}};
    std::stable_sort(data.begin(), data.end(),
        [](const auto& a, const auto& b) { return a.first < b.first; });
    // 相同 first 的元素保持原有顺序

    // 部分排序 - 只排前 N 个
    v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    std::partial_sort(v.begin(), v.begin() + 3, v.end());
    // 前 3 个是最小的 3 个元素

    // nth_element - 找第 N 小的元素
    v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    std::nth_element(v.begin(), v.begin() + 4, v.end());
    // v[4] 是第 5 小的元素（中间值）

    // is_sorted - 检查是否已排序
    bool sorted = std::is_sorted(v.begin(), v.end());

    return 0;
}

二分查找

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // binary_search - 检查是否存在
    bool found = std::binary_search(v.begin(), v.end(), 5);
    std::cout << "5 exists: " << std::boolalpha << found << "\n";  // true

    // lower_bound - 第一个 >= 5 的位置
    auto lb = std::lower_bound(v.begin(), v.end(), 5);
    std::cout << "First >= 5 at index: " << (lb - v.begin()) << "\n";  // 4

    // upper_bound - 第一个 > 5 的位置
    auto ub = std::upper_bound(v.begin(), v.end(), 5);
    std::cout << "First > 5 at index: " << (ub - v.begin()) << "\n";  // 5

    // equal_range - 两个边界
    auto range = std::equal_range(v.begin(), v.end(), 5);
    std::cout << "5 range: [" << (range.first - v.begin())
              << ", " << (range.second - v.begin()) << ")\n";  // [4, 5)

    // 查找并验证
    auto it = std::lower_bound(v.begin(), v.end(), 5);
    if (it != v.end() && *it == 5) {
        std::cout << "Found 5!\n";
    }

    return 0;
}

18.4 数值算法

#include <vector>
#include <numeric>
#include <iostream>
#include <functional>

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

    // accumulate - 求和
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "Sum: " << sum << "\n";  // 15

    // accumulate - 乘积
    long long product = std::accumulate(v.begin(), v.end(), 1LL,
        [](long long acc, int x) { return acc * x; });
    std::cout << "Product: " << product << "\n";  // 120

    // partial_sum - 前缀和
    std::vector<int> prefix;
    std::partial_sum(v.begin(), v.end(), std::back_inserter(prefix));
    // prefix = {1, 3, 6, 10, 15}

    // 差分
    std::vector<int> diff;
    std::adjacent_difference(v.begin(), v.end(), std::back_inserter(diff));
    // diff = {1, 1, 1, 1, 1}

    // count + accumulate = inner_product
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {4, 5, 6};
    int dot_product = std::inner_product(a.begin(), a.end(), b.begin(), 0);
    std::cout << "Dot product: " << dot_product << "\n";  // 1*4 + 2*5 + 3*6 = 32

    // iota - 生成递增序列
    std::vector<int> seq(5);
    std::iota(seq.begin(), seq.end(), 10);  // {10, 11, 12, 13, 14}

    return 0;
}

18.5 集合操作

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5};
    std::vector<int> b = {4, 5, 6, 7, 8};

    // 并集
    std::vector<int> result;
    std::set_union(a.begin(), a.end(), b.begin(), b.end(),
        std::back_inserter(result));
    // result = {1, 2, 3, 4, 5, 6, 7, 8}

    // 交集
    result.clear();
    std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
        std::back_inserter(result));
    // result = {4, 5}

    // 差集（A - B）
    result.clear();
    std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
        std::back_inserter(result));
    // result = {1, 2, 3}

    // 对称差集（A ^ B）
    result.clear();
    std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
        std::back_inserter(result));
    // result = {1, 2, 3, 6, 7, 8}

    // includes - 检查是否包含
    std::vector<int> subset = {1, 2, 3};
    bool contains = std::includes(a.begin(), a.end(),
        subset.begin(), subset.end());

    return 0;
}

18.6 投影和自定义比较

#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <tuple>

struct Student {
    std::string name;
    int age;
    double gpa;
};

int main() {
    std::vector<Student> students = {
        {"Alice", 20, 3.8},
        {"Bob", 19, 3.5},
        {"Charlie", 21, 3.9}
    };

    // 按姓名排序
    std::sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.name < b.name;
        });

    // 按 GPA 降序
    std::sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return a.gpa > b.gpa;
        });

    // 按多键排序（先年龄，再 GPA）
    std::sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            if (a.age != b.age) return a.age < b.age;
            return a.gpa > b.gpa;
        });

    // 使用 std::tie 实现多键排序（C++11）
    std::sort(students.begin(), students.end(),
        [](const Student& a, const Student& b) {
            return std::tie(a.age, a.gpa) < std::tie(b.age, b.gpa);
        });

    // 投影排序（按结构体成员的某个属性）
    // C++20 可以用 std::views::transform，但这里用 Lambda

    return 0;
}

18.7 C++20 范围库（Ranges）

范围库基础

# Python - 链式操作
result = [x**2 for x in range(10) if x % 2 == 0]
# 或者用 filter/map
from functools import reduce
result = reduce(lambda acc, x: acc + x,
    map(lambda x: x**2,
    filter(lambda x: x % 2 == 0, range(10))))

#include <vector>
#include <ranges>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // C++20 范围库 - 惰性求值
    auto evens = v | std::views::filter([](int x) { return x % 2 == 0; });
    auto squared = evens | std::views::transform([](int x) { return x * x; });

    // 遍历（惰性求值）
    std::cout << "Squared evens: ";
    for (int x : squared) {
        std::cout << x << " ";  // 4 16 36 64 100
    }
    std::cout << "\n";

    // 链式操作
    std::cout << "First 3 doubled: ";
    for (int x : v
        | std::views::filter([](int x) { return x % 2 == 0; })
        | std::views::transform([](int x) { return x * 2; })
        | std::views::take(3)) {
        std::cout << x << " ";  // 4 8 12
    }
    std::cout << "\n";

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

    return 0;
}

常用视图操作

#include <vector>
#include <ranges>
#include <iostream>

int main() {
    // drop/skip 前 N 个
    std::vector<int> v = {1, 2, 3, 4, 5};
    for (int x : v | std::views::drop(2)) {
        std::cout << x << " ";  // 3 4 5
    }
    std::cout << "\n";

    // take/前 N 个
    for (int x : v | std::views::take(3)) {
        std::cout << x << " ";  // 1 2 3
    }
    std::cout << "\n";

    // reverse
    for (int x : v | std::views::reverse) {
        std::cout << x << " ";  // 5 4 3 2 1
    }
    std::cout << "\n";

    // split（C++23）- 字符串分割
    // for (auto word : std::string_view("hello world") | std::views::split(' '))

    // filter + transform 组合
    auto result = v
        | std::views::filter([](int x) { return x % 2 == 0; })
        | std::views::transform([](int x) { return x * x; });

    // 转换为 vector
    std::vector<int> vec(result.begin(), result.end());

    // enumerate（C++23 有内置，C++20 变通）
    // for (auto [i, val] : v | std::views::enumerate)
    // C++20 自己实现
    int idx = 0;
    for (auto val : v) {
        std::cout << idx++ << ": " << val << "\n";
    }

    return 0;
}

范围库注意事项

#include <vector>
#include <ranges>
#include <iostream>

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

    // view 是惰性的，不保存数据
    auto v2 = v | std::views::filter([](int x) { return x % 2 == 0; });

    // 修改原容器，view 可能失效
    v.push_back(6);
    // v2 现在可能有问题（取决于实现）

    // 安全的做法：先转换为容器
    std::vector<int> vec_copy(v.begin(), v.end());
    auto safe_view = vec_copy | std::views::filter([](int x) { return x % 2 == 0; });

    // view 只能遍历一次（单向迭代器特性）
    // 不能两次遍历

    // 正确的用法
    for (int x : safe_view) {
        std::cout << x << " ";
    }
    std::cout << "\n";

    return 0;
}

18.8 完整示例：数据处理管道

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <ranges>
#include <fstream>

struct Product {
    std::string name;
    double price;
    int stock;
};

double calculate_total_value(const std::vector<Product>& products) {
    // 过滤有库存的商品，统计总价值
    double total = 0;
    for (const auto& p : products) {
        if (p.stock > 0) {
            total += p.price * p.stock;
        }
    }
    return total;
}

// C++20 版本
double calculate_total_value_cpp20(const std::vector<Product>& products) {
    auto in_stock = products
        | std::views::filter([](const Product& p) { return p.stock > 0; })
        | std::views::transform([](const Product& p) { return p.price * p.stock; });

    return std::accumulate(in_stock.begin(), in_stock.end(), 0.0);
}

int main() {
    std::vector<Product> inventory = {
        {"Apple", 1.50, 100},
        {"Banana", 0.75, 50},
        {"Cherry", 3.00, 0},
        {"Date", 2.25, 75},
        {"Elderberry", 4.50, 25}
    };

    // 找出最贵的 3 个有库存商品
    std::vector<Product*> ptrs;
    for (const auto& p : inventory) {
        if (p.stock > 0) {
            ptrs.push_back(const_cast<Product*>(&p));
        }
    }

    std::sort(ptrs.begin(), ptrs.end(),
        [](Product* a, Product* b) { return a->price > b->price; });

    std::cout << "Top 3 expensive in-stock products:\n";
    for (int i = 0; i < 3 && i < ptrs.size(); ++i) {
        std::cout << "  " << ptrs[i]->name << ": $" << ptrs[i]->price << "\n";
    }

    // 计算总库存价值
    std::cout << "\nTotal inventory value: $" << calculate_total_value_cpp20(inventory) << "\n";

    // 按价格范围分组
    auto expensive = inventory | std::views::filter([](const Product& p) { return p.price > 2.0; });
    auto cheap = inventory | std::views::filter([](const Product& p) { return p.price <= 2.0; });

    std::cout << "\nExpensive items (> $2.00): ";
    for (const auto& p : expensive) {
        std::cout << p.name << " ";
    }
    std::cout << "\n";

    std::cout << "Cheap items (<= $2.00): ";
    for (const auto& p : cheap) {
        std::cout << p.name << " ";
    }
    std::cout << "\n";

    return 0;
}

18.9 章节总结

算法类别	常用函数
查找	find, find_if, find_if_not, count, count_if
判断	all_of, any_of, none_of
变形	transform, for_each, copy, move
删除	remove, remove_if, unique
排序	sort, stable_sort, partial_sort, nth_element
二分查找	binary_search, lower_bound, upper_bound, equal_range
数值	accumulate, partial_sum, inner_product, iota
集合	set_union, set_intersection, set_difference

使用原则：

• 优先使用标准算法而非手写循环（更清晰、更优化）
• remove/remove_if 必须配合 erase 使用
• 二分查找前必须确保范围已排序
• C++20 范围库提供惰性求值的链式操作

---

下章预告：ch19 学习类和对象基础。