C++ 常用算法示例
介绍
C++标准模板库(STL)提供了大量高效、通用的算法,帮助开发者处理各种常见的编程任务。这些算法被设计为与STL容器和迭代器协同工作,使得代码更加简洁、高效且可读性强。本文将介绍一些C++ STL中最常用的算法,配合示例代码帮助初学者理解和掌握这些算法的使用方法。
要使用STL算法,首先需要包含相应的头文件:
#include <algorithm> // 大多数算法
#include <numeric> // 数值算法,如accumulate
#include <functional> // 函数对象
常用算法分类
STL算法可以大致分为以下几类:
- 非修改性序列操作:不改变序列中元素的值或位置
- 修改性序列操作:改变元素的值或位置
- 排序和相关操作:排序、合并、搜索等
- 数值操作:数学运算相关
让我们逐一探索这些类别中的常用算法。
非修改性序列操作
1. std::find
- 查找元素
find
算法搜索指定范围内的第一个与给定值相等的元素。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {10, 20, 30, 40, 50};
// 查找值为30的元素
auto it = std::find(vec.begin(), vec.end(), 30);
if (it != vec.end()) {
std::cout << "找到元素: " << *it << ",位置: " << (it - vec.begin()) << std::endl;
} else {
std::cout << "未找到元素" << std::endl;
}
return 0;
}
输出:
找到元素: 30,位置: 2
2. std::count
- 计数
count
算法计算指定范围内等于给定值的元素个数。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};
// 计算值为2的元素个数
int count = std::count(vec.begin(), vec.end(), 2);
std::cout << "值为2的元素个数: " << count << std::endl;
return 0;
}
输出:
值为2的元素个数: 3
3. std::for_each
- 应用函数于每个元素
for_each
算法对范围内的每个元素应用指定的函数。
#include <algorithm>
#include <iostream>
#include <vector>
void printElement(int n) {
std::cout << n << " ";
}
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::cout << "容器中的元素: ";
std::for_each(vec.begin(), vec.end(), printElement);
std::cout << std::endl;
// 使用lambda表达式
std::cout << "每个元素的平方: ";
std::for_each(vec.begin(), vec.end(), [](int n) {
std::cout << n * n << " ";
});
std::cout << std::endl;
return 0;
}
输出:
容器中的元素: 1 2 3 4 5
每个元素的平方: 1 4 9 16 25
修改性序列操作
1. std::transform
- 变换元素
transform
算法将一个操作应用于一个范围的每个元素,并将结果存储在另一个范围中。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec1 = {1, 2, 3, 4, 5};
std::vector<int> vec2(5); // 预分配空间
// 将vec1中的每个元素平方后存入vec2
std::transform(vec1.begin(), vec1.end(), vec2.begin(),
[](int x) { return x * x; });
std::cout << "原始数组: ";
for (int num : vec1) {
std::cout << num << " ";
}
std::cout << std::endl;
std::cout << "平方后: ";
for (int num : vec2) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
输出:
原始数组: 1 2 3 4 5
平方后: 1 4 9 16 25
2. std::copy
- 复制元素
copy
算法将一个范围内的元素复制到另一个范围。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5); // 预分配空间
// 将source中的元素复制到destination
std::copy(source.begin(), source.end(), destination.begin());
std::cout << "目标数组: ";
for (int num : destination) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
输出:
目标数组: 1 2 3 4 5
3. std::replace
- 替换元素
replace
算法将范围内所有等于给定值的元素替换为新值。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 2, 5};
std::cout << "替换前: ";
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
// 将所有值为2的元素替换为20
std::replace(vec.begin(), vec.end(), 2, 20);
std::cout << "替换后: ";
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
输出:
替换前: 1 2 3 2 5
替换后: 1 20 3 20 5
排序和相关操作
1. std::sort
- 排序
sort
算法对指定范围内的元素进行排序。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {5, 2, 8, 1, 9, 3};
std::cout << "排序前: ";
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
// 默认升序排序
std::sort(vec.begin(), vec.end());
std::cout << "升序排序后: ";
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
// 降序排序
std::sort(vec.begin(), vec.end(), std::greater<int>());
std::cout << "降序排序后: ";
for (int num : vec) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
输出:
排序前: 5 2 8 1 9 3
升序排序后: 1 2 3 5 8 9
降序排序后: 9 8 5 3 2 1
2. std::binary_search
- 二分查找
binary_search
算法检查已排序范围内是否存在某个元素。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// 检查元素5是否存在
bool exists = std::binary_search(vec.begin(), vec.end(), 5);
std::cout << "元素5" << (exists ? "存在" : "不存在") << "于排序数组中" << std::endl;
// 检查元素10是否存在
exists = std::binary_search(vec.begin(), vec.end(), 10);
std::cout << "元素10" << (exists ? "存在" : "不存在") << "于排序数组中" << std::endl;
return 0;
}
输出:
元素5存在于排序数组中
元素10不存在于排序数组中
binary_search
要求范围内的元素已经按照非降序排序!
3. std::max_element
和 std::min_element
- 查找最大和最小元素
这两个算法分别查找范围内的最大和最小元素。
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {5, 2, 8, 1, 9, 3};
// 查找最小元素
auto min = std::min_element(vec.begin(), vec.end());
std::cout << "最小元素: " << *min << std::endl;
// 查找最大元素
auto max = std::max_element(vec.begin(), vec.end());
std::cout << "最大元素: " << *max << std::endl;
return 0;
}
输出:
最小元素: 1
最大元素: 9
数值操作
1. std::accumulate
- 累加
accumulate
算法计算范围内所有元素的总和或执行其他二元操作。
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 计算总和
int sum = std::accumulate(vec.begin(), vec.end(), 0);
std::cout << "元素总和: " << sum << std::endl;
// 计算乘积
int product = std::accumulate(vec.begin(), vec.end(), 1, std::multiplies<int>());
std::cout << "元素乘积: " << product << std::endl;
return 0;
}
输出:
元素总和: 15
元素乘积: 120
2. std::inner_product
- 内积
inner_product
算法计算两个范围内元素的内积。
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};
// 计算内积:1*4 + 2*5 + 3*6
int result = std::inner_product(v1.begin(), v1.end(), v2.begin(), 0);
std::cout << "向量内积: " << result << std::endl;
return 0;
}
输出:
向量内积: 32
实际应用案例
让我们通过几个实际案例来展示这些算法的应用场景。
案例1:学生成绩统计
假设我们有一组学生的成绩,需要进行统计分析:
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<double> grades = {85.5, 92.0, 76.5, 88.0, 95.5, 73.0, 91.0};
// 计算平均成绩
double sum = std::accumulate(grades.begin(), grades.end(), 0.0);
double average = sum / grades.size();
// 查找最高分和最低分
auto maxIt = std::max_element(grades.begin(), grades.end());
auto minIt = std::min_element(grades.begin(), grades.end());
// 计算及格(>=60)人数
int passingCount = std::count_if(grades.begin(), grades.end(),
[](double grade) { return grade >= 60.0; });
// 按成绩排序(从高到低)
std::sort(grades.begin(), grades.end(), std::greater<double>());
std::cout << "成绩统计:" << std::endl;
std::cout << "班级平均分:" << average << std::endl;
std::cout << "最高分:" << *maxIt << std::endl;
std::cout << "最低分:" << *minIt << std::endl;
std::cout << "及格人数:" << passingCount << "(共" << grades.size() << "人)" << std::endl;
std::cout << "成绩排名(从高到低):";
for (double grade : grades) {
std::cout << grade << " ";
}
std::cout << std::endl;
return 0;
}
输出:
成绩统计:
班级平均分:85.9286
最高分:95.5
最低分:73
及格人数:7(共7人)
成绩排名(从高到低):95.5 92 91 88 85.5 76.5 73
案例2:文本处理
假设我们需要分析一段文本中各个单词的出现频率:
#include <algorithm>
#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>
int main() {
std::string text = "C++ STL algorithms are powerful C++ provides many useful algorithms";
// 将文本分割为单词
std::istringstream iss(text);
std::vector<std::string> words;
std::string word;
while (iss >> word) {
// 转换为小写(可选)
std::transform(word.begin(), word.end(), word.begin(),
[](unsigned char c) { return std::tolower(c); });
words.push_back(word);
}
// 统计每个单词出现的频率
std::map<std::string, int> wordFreq;
for (const auto& w : words) {
wordFreq[w]++;
}
// 输出结果
std::cout << "单词频率统计:" << std::endl;
for (const auto& pair : wordFreq) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
// 找出出现次数最多的单词
auto maxElement = std::max_element(wordFreq.begin(), wordFreq.end(),
[](const auto& a, const auto& b) {
return a.second < b.second;
});
std::cout << "\n出现频率最高的单词是:" << maxElement->first
<< "(出现" << maxElement->second << "次)" << std::endl;
return 0;
}
输出:
单词频率统计:
algorithms: 1
are: 1
c++: 2
many: 1
powerful: 1
provides: 1
stl: 1
useful: 1
出现频率最高的单词是:c++(出现2次)
总结
STL算法库是C++编程的强大工具,它提供了丰富的通用算法,可以高效处理各种常见的编程任务。通过合理使用这些算法,你可以:
- 简化代码:无需自己实现常见的算法逻辑
- 提高效率:STL算法通常比手写循环更高效
- 减少错误:经过广泛测试的标准库比自己编写的代码更可靠
- 增强可读性:使用标准算法,代码意图更明确
学习和掌握STL算法对于提升C++编程能力至关重要。本文介绍的只是STL算法库中的一部分,建议进一步学习其他算法,例如partition
、unique
、shuffle
等,以便在实际项目中能够选择最合适的工具。
记住,算法的选择和使用应该基于特定问题的需求和约束条件。有时候,最简单的算法可能是最好的解决方案。
练习
为帮助巩固所学知识,尝试完成以下练习:
- 编写程序,使用
std::remove_if
和erase
删除向量中的所有偶数 - 使用
std::stable_partition
将一组学生按照成绩及格与否分为两组 - 利用
std::transform
和std::back_inserter
实现两个向量的元素相加并存储在第三个向量中 - 使用
std::merge
合并两个已排序的向量 - 实现一个简单的文本分析工具,统计一篇文章中每个字母出现的频率
附加资源
- C++ Reference - Algorithm library
- 《Effective STL》by Scott Meyers
- 《C++ STL标准库开发指南》
- 《STL源码剖析》by 侯捷