STL 算法
C++ 标准模板库 (STL) 提供了一组丰富的通用算法，这些算法作用于元素范围。这些算法旨在高效且通过迭代器与各种容器类型配合使用。它们提供了强大的排序、搜索、转换和数据操作功能，通常比手动实现提供更优化的解决方案。本模块将这些算法与常见的 JavaScript 数组方法进行比较。
算法库概述
STL 算法通常位于 <algorithm> 标头中。它们是通用的，这意味着它们可以与不同的数据类型和容器类型配合使用，只要提供的迭代器符合算法的要求即可。算法与容器的分离是 STL 的一个关键设计原则，促进了可重用性和灵活性。
排序算法
排序算法以特定顺序排列元素。
std::sort
- 默认情况下，以升序排序范围内的元素。
- 通常使用内省排序 (快速排序、堆排序和插入排序的混合) 实现平均 O(N log N) 的复杂度。
正在加载...
std::stable_sort
- 在排序元素的同时，保留等效元素的相对顺序。
- 通常使用合并排序或类似算法，复杂度为 O(N log N)。
std::partial_sort
- 仅排序范围的一部分，特别是前
n个元素。
搜索算法
搜索算法在范围内寻找元素。
std::find
- 搜索值的第一次出现。
- 返回指向第一个匹配元素的迭代器，如果未找到则返回
last。 - 线性搜索，O(N) 复杂度。
正在加载...
std::binary_search
- 检查已排序范围中是否存在元素。
- 如果找到则返回
true，否则返回false。 - 二分搜索，O(log N) 复杂度。
std::lower_bound / std::upper_bound
lower_bound：返回指向已排序范围中第一个不小于 (即大于或等于) 给定值的元素的迭代器。upper_bound：返回指向已排序范围中第一个大于给定值的元素的迭代器。
修改算法
修改算法会更改范围内的元素。
std::copy
- 将元素从一个范围复制到另一个范围。
正在加载...
std::transform
- 对范围中的每个元素应用函数，并将结果存储在另一个范围中。
正在加载...
std::replace
- 将范围中特定值的所有出现替换为另一个值。
数值算法
数值算法位于 <numeric> 标头中。
std::accumulate
- 计算范围中元素的总和，或累加应用二元运算。
正在加载...
std::inner_product
- 计算两个范围的内积 (对应元素乘积的总和)。
与 JavaScript 数组方法的比较
JavaScript 的 Array.prototype 提供了许多内置方法，这些方法提供了与 STL 算法类似的功能。但是，存在关键差异：
| 特性 | JavaScript 数组方法 | C++ STL 算法 |
|---|---|---|
| 泛型 | 通过动态类型实现 | 通过模板和迭代器实现 |
| 类型安全 | 运行时类型检查 | 编译时类型检查 |
| 性能 | 通常内部优化，但动态类型/GC 带来开销 | 高度优化，直接内存访问，编译时优化 |
| 灵活性 | 仅限于数组 (和类似数组的对象) | 适用于任何提供迭代器的容器 |
| 错误处理 | 抛出运行时错误 | 类型不匹配的编译时错误，无效迭代器的运行时错误 |
算法性能分析
STL 算法通常经过高度优化，并提供强大的性能保证。它们的复杂度通常以其操作范围中的元素数量 (N) 表示。
- O(N) (线性)：
std::find、std::copy、std::transform、std::accumulate。 - O(N log N) (对数线性)：
std::sort、std::stable_sort。 - O(log N) (对数)：
std::binary_search(在已排序范围上)。
了解这些复杂度有助于为给定任务选择最合适的算法，尤其是在性能关键的应用程序中。
练习题：
- 解释
std::sort和std::stable_sort之间的区别。何时会优先选择其中一个？ - C++ 中的
std::transform与 JavaScript 的Array.prototype.map()如何比较？提供一个简单的示例，其中使用std::transform将向量中的每个元素加倍。 - 讨论使用 STL 算法相较于在 C++ 中手动实现类似功能的优点。
项目构想：
- 创建一个 C++ 程序，从文件中读取数字列表，对其进行排序，移除重复项，然后计算其总和和平均值。使用适当的 STL 容器和算法 (
std::vector、std::sort、std::unique、std::accumulate)。将其性能与手动实现的排序和求和版本进行比较。