目录
概述
<algorithm> 是 C++ 标准模板库（STL）中的算法库，提供了一系列通用的、非修改容器结构的算法。这些算法通过迭代器操作容器，支持多种数据结构（如数组、<vector>、<list> 等）。它包含排序、查找、修改、计数等功能，广泛应用于数据处理。
包含头文件
#include <algorithm>
#include <iostream>
#include <vector> // 示例中常用容器
基本格式
算法通常以函数模板形式提供，接受迭代器和可选的比较器或谓词：
std::algorithm_name(迭代器开始, 迭代器结束, [可选参数]);
基本特性
- 通用性：适用于任何支持迭代器的容器。
- 高效性：多数算法优化为 O(n log n) 或更低复杂度。
- 灵活性：支持自定义比较器和谓词。
- 非侵入性：不修改容器结构，仅操作元素。
基本用法
排序算法
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {5, 2, 9, 1, 5};
std::sort(v.begin(), v.end()); // 默认升序排序
std::cout << "Sorted: ";
for (int x : v) std::cout << x << " "; // 输出：1 2 5 5 9
std::cout << std::endl;
std::sort(v.begin(), v.end(), std::greater<int>()); // 降序
std::cout << "Reverse sorted: ";
for (int x : v) std::cout << x << " "; // 输出：9 5 5 2 1
std::cout << std::endl;
return 0;
}
sort()：O(n log n)，需要随机访问迭代器。stable_sort()：保持相等元素的相对顺序。
查找算法
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 3, 5, 7, 9};
auto it = std::find(v.begin(), v.end(), 5); // 线性查找
if (it != v.end()) {
std::cout << "Found: " << *it << std::endl; // 输出：Found: 5
}
std::sort(v.begin(), v.end()); // 二分查找需有序
if (std::binary_search(v.begin(), v.end(), 7)) {
std::cout << "7 exists" << std::endl; // 输出：7 exists
}
return 0;
}
find()：O(n)，线性查找。binary_search()：O(log n)，需有序序列。
修改算法
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4};
std::fill(v.begin(), v.begin() + 2, 0); // 填充
std::cout << "Filled: ";
for (int x : v) std::cout << x << " "; // 输出：0 0 3 4
std::cout << std::endl;
std::replace(v.begin(), v.end(), 0, 9); // 替换
std::cout << "Replaced: ";
for (int x : v) std::cout << x << " "; // 输出：9 9 3 4
std::cout << std::endl;
return 0;
}
fill()：O(n)，填充范围。replace()：O(n)，替换指定值。
比较和计数算法
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {1, 2, 3};
if (std::equal(v1.begin(), v1.end(), v2.begin())) {
std::cout << "Vectors are equal" << std::endl; // 输出：Vectors are equal
}
std::vector<int> v3 = {1, 2, 2, 3};
int count = std::count(v3.begin(), v3.end(), 2);
std::cout << "Count of 2: " << count << std::endl; // 输出：Count of 2: 2
return 0;
}
equal()：O(n)，比较两个范围。count()：O(n)，计数指定值。
集合操作
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v1 = {1, 2, 3, 4};
std::vector<int> v2 = {2, 4, 6};
std::vector<int> result(10); // 预分配空间
auto it = std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
result.resize(it - result.begin());
std::cout << "Intersection: ";
for (int x : result) std::cout << x << " "; // 输出：2 4
std::cout << std::endl;
return 0;
}
set_intersection()：O(n log n)，需有序输入。- 其他：
set_union、set_difference。
最小/最大值算法
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {5, 2, 9, 1};
std::cout << "Min: " << std::min(3, 7) << std::endl; // 输出：3
std::cout << "Max: " << std::max(3, 7) << std::endl; // 输出：7
auto minmax = std::minmax_element(v.begin(), v.end());
std::cout << "Min in v: " << *minmax.first << ", Max in v: " << *minmax.second << std::endl; // 输出：Min in v: 1, Max in v: 9
return 0;
}
min()/max()：O(1)，比较两个值。minmax_element()：O(n)，查找范围内的最小和最大值。
其他常用算法
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 2, 3};
std::reverse(v.begin(), v.end()); // 反转
std::cout << "Reversed: ";
for (int x : v) std::cout << x << " "; // 输出：3 2 2 1
std::cout << std::endl;
auto it = std::unique(v.begin(), v.end()); // 去重（需排序）
v.resize(it - v.begin());
std::cout << "Unique (after sort): ";
std::sort(v.begin(), v.end()); // 先排序
it = std::unique(v.begin(), v.end());
v.resize(it - v.begin());
for (int x : v) std::cout << x << " "; // 输出：1 2 3
std::cout << std::endl;
return 0;
}
reverse()：O(n)，反转范围。unique()：O(n)，移除连续重复元素（需先排序）。
与其他库的对比
| 特性 | <algorithm> | <numeric> | 自定义实现 |
|---|---|---|---|
| 功能范围 | 通用算法 | 数值计算 | 特定需求 |
| 性能 | 优化实现 | 优化实现 | 视实现而定 |
| 通用性 | 高（迭代器） | 中（数值容器） | 低 |
| 学习成本 | 中等 | 较低 | 高 |
注意事项
- 迭代器要求：不同算法需要特定类型的迭代器（如
sort需随机访问）。 - 范围有效性：确保迭代器范围合法，避免未定义行为。
- 自定义比较器：需满足严格弱序（strict weak ordering）。
- 性能依赖：部分算法（如
sort）依赖底层容器特性。
实用示例：学生成绩处理
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
struct Student {
std::string name;
int score;
};
int main() {
std::vector<Student> students = {{"Alice", 95}, {"Bob", 87}, {"Charlie", 92}};
// 按成绩降序排序
std::sort(students.begin(), students.end(),
[](const Student& a, const Student& b) { return a.score > b.score; });
std::cout << "Students by score (descending):\n";
for (const auto& s : students) {
std::cout << s.name << ": " << s.score << "\n";
}
// 查找分数为 92 的学生
auto it = std::find_if(students.begin(), students.end(),
[](const Student& s) { return s.score == 92; });
if (it != students.end()) {
std::cout << "Found student with score 92: " << it->name << "\n";
}
return 0;
}
输出：
Students by score (descending):
Alice: 95
Charlie: 92
Bob: 87
Found student with score 92: Charlie
小练习
问题
写一个 C++ 程序：
- 定义一个
std::vector<int>，初始化为 {4, 2, 7, 1, 4}。 - 对其升序排序并移除重复元素。
- 输出最终序列和最大值。
参考答案
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {4, 2, 7, 1, 4};
// 升序排序
std::sort(v.begin(), v.end());
// 移除重复元素
auto it = std::unique(v.begin(), v.end());
v.resize(it - v.begin());
// 输出结果
std::cout << "Final sequence: ";
for (int x : v) std::cout << x << " "; // 输出：1 2 4 7
std::cout << std::endl;
std::cout << "Max value: " << *std::max_element(v.begin(), v.end()) << std::endl; // 输出：7
return 0;
}
参考资料
- C++ Standard Library Reference:
<algorithm>的官方文档。
- ISO/IEC 14882:2011 (C++11 Standard)
- cppreference.com: 提供
<algorithm>的详细说明和示例。 - The C++ Programming Language (4th Edition) by Bjarne Stroustrup: C++ STL 权威书籍。
- Effective STL by Scott Meyers: STL 算法实用建议。
出站链接
- cppreference.com: – 官方文档和示例。
- C++ Reference: – 接口说明。
- GeeksforGeeks: Algorithms in C++ STL – 教程和代码示例。
- LearnCpp: STL Algorithms – 初学者教程。
下一步
- 如果你想试试练习，请提交代码，我会帮你检查。
- 如果需要更深入内容（如自定义谓词、算法复杂度分析），或设计测验题，请告诉我！
- 你也可以提出具体问题，如“如何用
<algorithm>实现归并排序？”或“<algorithm>和<numeric>的区别？”。
现在，你想做什么？试试练习，还是有其他需求？
发表回复