跳到主要内容

C++ 常用算法示例

介绍

C++标准模板库(STL)提供了大量高效、通用的算法,帮助开发者处理各种常见的编程任务。这些算法被设计为与STL容器和迭代器协同工作,使得代码更加简洁、高效且可读性强。本文将介绍一些C++ STL中最常用的算法,配合示例代码帮助初学者理解和掌握这些算法的使用方法。

要使用STL算法,首先需要包含相应的头文件:

cpp
#include <algorithm>  // 大多数算法
#include <numeric> // 数值算法,如accumulate
#include <functional> // 函数对象

常用算法分类

STL算法可以大致分为以下几类:

  1. 非修改性序列操作:不改变序列中元素的值或位置
  2. 修改性序列操作:改变元素的值或位置
  3. 排序和相关操作:排序、合并、搜索等
  4. 数值操作:数学运算相关

让我们逐一探索这些类别中的常用算法。

非修改性序列操作

1. std::find - 查找元素

find算法搜索指定范围内的第一个与给定值相等的元素。

cpp
#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算法计算指定范围内等于给定值的元素个数。

cpp
#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算法对范围内的每个元素应用指定的函数。

cpp
#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算法将一个操作应用于一个范围的每个元素,并将结果存储在另一个范围中。

cpp
#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算法将一个范围内的元素复制到另一个范围。

cpp
#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算法将范围内所有等于给定值的元素替换为新值。

cpp
#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算法对指定范围内的元素进行排序。

cpp
#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算法检查已排序范围内是否存在某个元素。

cpp
#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_elementstd::min_element - 查找最大和最小元素

这两个算法分别查找范围内的最大和最小元素。

cpp
#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算法计算范围内所有元素的总和或执行其他二元操作。

cpp
#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算法计算两个范围内元素的内积。

cpp
#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:学生成绩统计

假设我们有一组学生的成绩,需要进行统计分析:

cpp
#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:文本处理

假设我们需要分析一段文本中各个单词的出现频率:

cpp
#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++编程的强大工具,它提供了丰富的通用算法,可以高效处理各种常见的编程任务。通过合理使用这些算法,你可以:

  1. 简化代码:无需自己实现常见的算法逻辑
  2. 提高效率:STL算法通常比手写循环更高效
  3. 减少错误:经过广泛测试的标准库比自己编写的代码更可靠
  4. 增强可读性:使用标准算法,代码意图更明确

学习和掌握STL算法对于提升C++编程能力至关重要。本文介绍的只是STL算法库中的一部分,建议进一步学习其他算法,例如partitionuniqueshuffle等,以便在实际项目中能够选择最合适的工具。

提示

记住,算法的选择和使用应该基于特定问题的需求和约束条件。有时候,最简单的算法可能是最好的解决方案。

练习

为帮助巩固所学知识,尝试完成以下练习:

  1. 编写程序,使用std::remove_iferase删除向量中的所有偶数
  2. 使用std::stable_partition将一组学生按照成绩及格与否分为两组
  3. 利用std::transformstd::back_inserter实现两个向量的元素相加并存储在第三个向量中
  4. 使用std::merge合并两个已排序的向量
  5. 实现一个简单的文本分析工具,统计一篇文章中每个字母出现的频率

附加资源