Course: 斯坦福大学: C++标准库编程 | C++ Standard Library Programming

🎮 CS106L Lecture 4.3 — Functions and Algorithms

🏛 课程：Stanford CS106L — Standard C++ Programming Language

📍 主题：函数、谓词与算法（Functions, Predicates & Algorithms）

🎯 目标：理解函数与算法的协作机制，掌握谓词与 lambda 在 STL 算法中的应用，并学习典型算法惯用法（如 erase-remove）。

🧭 课程定位

本讲是「模板与算法」单元的收官篇。

它从函数模板延伸到 STL 算法的行为本质，讲解了：

• 函数式参数（函数指针、谓词、Lambda）
• 算法接口思想：容器无关、基于迭代器
• 常见算法模式与优化写法

“STL 算法 = 可重用的 for 循环。”

🏷 关键词速记

Predicate｜谓词函数

Lambda｜匿名函数

Algorithm｜算法库

Erase-Remove Idiom｜删除惯用法

Functor｜函数对象

Higher-Order Function｜高阶函数

🎮 30 秒课程摘要

“在 C++ 里，函数是一等公民。

你可以把它像变量一样传递、组合，让算法变成通用逻辑。”

📚 核心内容讲解

🧩 1️⃣ 什么是谓词（Predicate）？

谓词是返回布尔值的函数，用于判断元素是否满足条件。

📦 示例 1：一元谓词（Unary Predicate）

bool isEven(int x) {
    return x % 2 == 0;
}
std::vector<int> nums = {1, 2, 3, 4, 5, 6};
int count = std::count_if(nums.begin(), nums.end(), isEven);
std::cout << "Even numbers: " << count;

📤 输出： Even numbers: 3

🧩 讲解：

• count_if 是 STL 的算法函数。
• 它接受一个“判断条件”函数（谓词）。
• 当谓词返回 true 时，计数 +1。

🧩 2️⃣ 二元谓词（Binary Predicate）

接收两个参数的布尔函数，用于排序或比较。

📦 示例 2：二元谓词

bool longer(const std::string& a, const std::string& b) {
    return a.size() > b.size();
}
std::vector<std::string> names = {"Ada", "Bjarne", "Linus"};
std::sort(names.begin(), names.end(), longer);
for (auto& n : names) std::cout << n << " ";

📤 输出： Bjarne Linus Ada

🧩 讲解：

• STL 算法常将比较逻辑抽象成二元谓词。
• 用户可传入不同谓词，动态改变算法行为。

🧩 3️⃣ Lambda 表达式（Lambda Expressions）

Lambda 是“匿名函数”，让你在调用处直接定义函数。

📦 示例 3：Lambda 谓词

std::vector<int> v = {1, 2, 3, 4, 5};
int count = std::count_if(v.begin(), v.end(),
                          [](int x){ return x % 2 == 1; });
std::cout << count;

📤 输出： 3

🧩 讲解：

[](int x){...} 定义一个匿名函数对象：

• [] 捕获外部变量
• (int x) 参数列表
• { return x % 2 == 1; } 函数体

🧩 4️⃣ 捕获（Capture）机制

Lambda 可通过捕获列表与外部变量交互。

📦 示例 4：捕获变量

int limit = 3;
std::for_each(v.begin(), v.end(),
              [limit](int x){
                  if (x > limit) std::cout << x << " ";
              });

📤 输出： 4 5

🧩 捕获方式说明：

🧩 5️⃣ 算法与函数结合

📦 示例 5：使用 Lambda 与 std::transform

std::vector<int> src = {1, 2, 3};
std::vector<int> dst(src.size());
std::transform(src.begin(), src.end(), dst.begin(),
               [](int x){ return x * x; });
for (int n : dst) std::cout << n << " ";

📤 输出： 1 4 9

🧩 讲解：

• transform 将输入序列映射到输出序列
• 第四个参数是函数（可为 lambda、谓词或普通函数）

🧩 6️⃣ 高阶算法与组合

函数可以返回函数，也可以作为参数传入函数。

📦 示例 6：组合谓词

auto isOdd = [](int x){ return x % 2 == 1; };
auto greaterThan = [](int x){ return x > 3; };
auto complexPred = [&](int x){ return isOdd(x) && greaterThan(x); };

std::vector<int> nums = {1, 2, 3, 4, 5, 6};
auto it = std::find_if(nums.begin(), nums.end(), complexPred);
std::cout << *it;

📤 输出： 5

🧩 讲解：

• Lambda 也能组合成复杂条件函数。
• 这种“函数组合”是函数式编程思想在 C++ 的体现。

🧩 7️⃣ STL 算法实战

📦 示例 7：过滤与拷贝

std::vector<int> v = {1,2,3,4,5,6};
std::vector<int> filtered;
std::copy_if(v.begin(), v.end(), std::back_inserter(filtered),
             [](int x){ return x % 2 == 0; });
for (int n : filtered) std::cout << n << " ";

📤 输出： 2 4 6

🧩 8️⃣ Erase–Remove 惯用法

STL remove_if 不直接删除元素，而是移动满足条件的元素到末尾。

需要配合 .erase() 真正删除。

📦 示例 8：正确删除写法

std::vector<int> v = {1,2,3,4,5,6};
v.erase(std::remove_if(v.begin(), v.end(),
                       [](int x){ return x % 2 == 0; }),
        v.end());
for (int n : v) std::cout << n << " ";

📤 输出： 1 3 5

🧩 讲解：

• remove_if() 返回“新结尾迭代器”
• erase() 根据该迭代器删除尾部多余元素

称为 Erase–Remove Idiom（擦除-移除惯用法）

🧩 9️⃣ 算法哲学：解耦与组合

“容器存储，算法操作，迭代器沟通。”

STL 的目标是让算法完全独立于容器。

只要容器提供 begin() / end()，就能使用算法。

📦 示例 9：算法泛用性

std::set<int> s = {3,1,4,2};
std::for_each(s.begin(), s.end(),
              [](int x){ std::cout << x << " "; });

📤 输出： 1 2 3 4

🧩 同一个算法可同时适用于 vector, list, set，因为它们共享迭代器接口。

🧠 记忆口诀

“谓词定逻辑，lambda速起；

算法分工明，erase remove齐。”

🧪 实践练习

✅ 练习 1：奇数计数器

用 count_if + lambda 统计奇数数量。

✅ 练习 2：字符串过滤

给定 vector<string>，用 remove_if 删除所有长度 < 3 的字符串。

✅ 练习 3：自定义排序

使用 sort + lambda 按字符串长度降序排列。

✅ 练习 4：组合条件过滤

用多个 lambda 组合条件筛选数据。

🪄 创作与工程建议

• 优先使用算法库而非手写循环（可读性与性能兼得）。
• 使用 lambda 而非单独定义谓词函数。
• 对可删除算法使用 erase-remove 惯用法。
• 不要在循环中修改容器结构（会导致迭代器失效）。
• 组合算法：先过滤 (copy_if)，再转换 (transform)，最后聚合 (accumulate)。

✅ 小结表

“STL 算法 = 代码复用的最高境界。

写一次谓词，通吃所有容器。”