C++中STL算法的应用：从排序到数值运算

欢迎来到C++ STL算法大讲堂！

各位同学，今天我们来聊聊C++中的STL（Standard Template Library）算法。STL就像一个神奇的魔法盒，里面装满了各种工具，从排序到数值运算无所不能！如果你还没掌握它，那你可就亏大了！今天我们就以轻松诙谐的方式，带大家走进STL的世界。

---

第一部分：排序——让数据乖乖排好队

排序是编程中最常见的需求之一。想象一下，你有一堆乱七八糟的数字，想把它们从小到大排列整齐。这时候，std::sort就是你的救星！

1. 基础用法

#include <iostream>
#include <vector>
#include <algorithm> // std::sort 的头文件

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};
    std::sort(numbers.begin(), numbers.end()); // 默认升序排序
    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

输出：

1 2 5 5 6 9

2. 自定义排序规则

有时候，默认的升序排序可能不符合你的需求。比如你想按降序排序，或者根据某个复杂的规则来排序。这时候可以传入一个自定义的比较函数或lambda表达式。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};

    // 使用 lambda 表达式实现降序排序
    std::sort(numbers.begin(), numbers.end(), [](int a, int b) {
        return a > b; // 如果 a > b，则交换位置
    });

    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

输出：

9 6 5 5 2 1

3. 国外技术文档小贴士

在C++标准库中，std::sort使用的是快速排序（QuickSort）和插入排序（InsertionSort）的混合实现，称为IntroSort。这种算法的时间复杂度为O(n log n)，非常高效！

---

第二部分：查找——大海捞针的艺术

排序完成后，我们经常需要查找某个特定的值。STL提供了多种查找算法，比如std::find、std::binary_search等。

1. std::find：线性查找

std::find是一个简单的线性查找算法，适用于未排序的数据。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};
    auto it = std::find(numbers.begin(), numbers.end(), 9); // 查找值为9的元素

    if (it != numbers.end()) {
        std::cout << "找到了，索引为: " << std::distance(numbers.begin(), it) << std::endl;
    } else {
        std::cout << "没找到" << std::endl;
    }
    return 0;
}

2. std::binary_search：二分查找

如果数据已经排序，那么可以使用更高效的二分查找。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {1, 2, 5, 5, 6, 9};
    bool found = std::binary_search(numbers.begin(), numbers.end(), 5);

    if (found) {
        std::cout << "找到了!" << std::endl;
    } else {
        std::cout << "没找到..." << std::endl;
    }
    return 0;
}

国外技术文档小贴士

std::binary_search的时间复杂度为O(log n)，比线性查找快得多，但要求数据必须是有序的。

---

第三部分：数值运算——数学家的最爱

STL还提供了许多用于数值运算的算法，比如求和、累乘、最大值/最小值等。

1. std::accumulate：求和与累乘

std::accumulate是一个强大的工具，不仅可以求和，还可以进行累乘或其他操作。

#include <iostream>
#include <vector>
#include <numeric> // std::accumulate 的头文件

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // 求和
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
    std::cout << "总和: " << sum << std::endl;

    // 累乘
    int product = std::accumulate(numbers.begin(), numbers.end(), 1, std::multiplies<int>());
    std::cout << "乘积: " << product << std::endl;

    return 0;
}

2. std::max_element 和 std::min_element：寻找最大值和最小值

这两个算法可以帮助你快速找到容器中的最大值和最小值。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 2, 9, 1, 5, 6};

    // 找到最大值
    auto max_it = std::max_element(numbers.begin(), numbers.end());
    std::cout << "最大值: " << *max_it << std::endl;

    // 找到最小值
    auto min_it = std::min_element(numbers.begin(), numbers.end());
    std::cout << "最小值: " << *min_it << std::endl;

    return 0;
}

国外技术文档小贴士

std::accumulate支持自定义操作符，因此可以用它实现几乎任何累积操作。

---

第四部分：变换与过滤——数据加工的艺术

有时候我们需要对数据进行一些变换或过滤。STL提供了std::transform和std::copy_if等算法。

1. std::transform：数据变换

std::transform可以将一个容器中的数据通过某种规则转换成另一个容器。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::vector<int> squares(numbers.size());

    // 将每个数平方
    std::transform(numbers.begin(), numbers.end(), squares.begin(), [](int x) {
        return x * x;
    });

    for (int num : squares) {
        std::cout << num << " ";
    }
    return 0;
}

2. std::copy_if：数据过滤

std::copy_if可以将满足条件的元素复制到另一个容器中。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::vector<int> evens;

    // 过滤出偶数
    std::copy_if(numbers.begin(), numbers.end(), std::back_inserter(evens), [](int x) {
        return x % 2 == 0;
    });

    for (int num : evens) {
        std::cout << num << " ";
    }
    return 0;
}

---

总结表格：常用STL算法一览

算法名称	功能描述	示例代码片段
std::sort	排序	std::sort(vec.begin(), vec.end())
std::find	线性查找	std::find(vec.begin(), vec.end(), 5)
std::binary_search	二分查找	std::binary_search(vec.begin(), vec.end(), 5)
std::accumulate	求和或累乘	std::accumulate(vec.begin(), vec.end(), 0)
std::max_element	找到最大值	*std::max_element(vec.begin(), vec.end())
std::min_element	找到最小值	*std::min_element(vec.begin(), vec.end())
std::transform	数据变换	std::transform(vec.begin(), vec.end(), result.begin(), [](int x){return x*x;})
std::copy_if	数据过滤	std::copy_if(vec.begin(), vec.end(), std::back_inserter(result), [](int x){return x%2==0;})

---

今天的课程就到这里啦！希望大家能熟练掌握这些STL算法，让你的代码更加简洁高效！下课前别忘了完成作业哦：尝试用STL算法解决一个实际问题，比如统计一段文本中每个单词出现的次数。祝大家编程愉快！