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 侯捷

介绍​

常用算法分类​

非修改性序列操作​

1. std::find - 查找元素​

2. std::count - 计数​

3. std::for_each - 应用函数于每个元素​

修改性序列操作​

1. std::transform - 变换元素​

2. std::copy - 复制元素​

3. std::replace - 替换元素​

排序和相关操作​

1. std::sort - 排序​

2. std::binary_search - 二分查找​

3. std::max_element 和 std::min_element - 查找最大和最小元素​

数值操作​

1. std::accumulate - 累加​

2. std::inner_product - 内积​

实际应用案例​

案例1：学生成绩统计​

案例2：文本处理​

总结​

练习​

附加资源​

介绍