快速测验

编程练习

算法前提条件

• 排序前提: `binary_search`, `lower_bound`, `upper_bound`, `equal_range`, `merge`, `inplace_merge`, `includes`, `set_union`, `set_intersection`, `set_difference`, `set_symmetric_difference` 都要求输入范围（或至少相关部分）是 **已排序** 的。
• `unique`: 只移除 **相邻** 的重复元素。如果想移除所有重复元素，通常需要先排序。
• 迭代器有效性: 大部分修改序列的算法（如 `sort`, `partition`, `remove` 等）可能会使传入的迭代器失效（除了 `end()` 返回的迭代器）。`stable_*` 版本的算法通常能更好地保持迭代器（相对于未移动的元素）。

时间复杂度

• 注意区分 **平均** 时间复杂度和 **最坏** 时间复杂度。例如，`sort` 通常是 O(N log N)，但某些旧实现或特定数据下可能退化。`nth_element` 平均是 O(N)，但最坏是 O(N²)。
• 复杂度中的 N 通常指范围内的元素数量。

边界情况处理

• 处理 **空序列**：确保算法在空范围上行为正确或有定义（通常是无操作）。
• 迭代器范围: 确保 `[first, last)` 是一个有效范围 (`first` 不在 `last` 之后)。
• 参数检查: 对于 `nth_element(first, nth, last)`，确保 `nth` 在 `[first, last)` 范围内。对于 `partial_sort(first, middle, last)`，确保 `middle` 在 `[first, last]` 范围内。

返回值

• 许多算法返回迭代器，如 `find`, `lower_bound`, `partition`, `remove`, `unique` 等。理解这些迭代器的含义非常重要（例如，`remove` 和 `unique` 返回的是 **新的逻辑结尾**）。
• 一些算法（如 `sort`, `reverse`）返回 `void`。
• 谓词函数应保持 **纯粹**，不应修改传入的元素或有副作用。

C++20 `<ranges>` 库

C++20 引入了 `<ranges>` 库，提供了对算法的重大改进：

• 可以直接对 **容器本身** 调用算法，无需 `begin()` 和 `end()`，例如 `ranges::sort(myVector);`
• 支持 **投影 (Projections)**：允许在比较或操作前对元素应用一个转换函数，例如按对象的某个成员排序。
• 更好的 **组合性**：通过管道操作符 `|` 连接视图 (views) 和算法，写出更简洁、声明式的代码。
• **视图 (Views)**：惰性求值的序列适配器，如 `filter`, `transform`, `take` 等，可以高效地处理数据流而无需创建中间容器。

自定义比较器与谓词

许多算法接受可选的最后一个参数，用于自定义比较逻辑 (Comparison function) 或条件判断 (Predicate function)：

• 比较器: 用于 `sort`, `stable_sort`, `lower_bound`, `max_element` 等。必须满足严格弱序 (Strict Weak Ordering) 要求。通常是一个接收两个参数并返回 `bool` 的函数或 Lambda 表达式 (`[](const auto& a, const auto& b) { return a < b; }`)。
• 谓词: 用于 `find_if`, `count_if`, `partition`, `remove_if` 等。通常是一个接收一个参数并返回 `bool` 的函数或 Lambda 表达式 (`[](const auto& x) { return x > 10; }`)。

并行算法 (`<execution>`)

C++17 引入了执行策略，允许指定算法并行执行：

• `execution::seq`: 顺序执行（默认）。
• `execution::par`: 并行执行，可能无序。
• `execution::par_unseq`: 并行执行，可能无序，且允许向量化（交错执行）。

例如: `sort(execution::par, v.begin(), v.end());`

注意: 并行化并非总能带来性能提升，且需要注意数据竞争问题（自定义操作必须线程安全）。编译器和标准库的支持程度也可能不同。