11 STL进阶之算法库的使用

在前一篇的教程中，我们深入探讨了 STL 容器的高级用法，掌握了如何充分利用 STL 提供的各种容器来存储和管理数据。在这篇文章中，我们将继续扩展我们的知识，专注于 STL 中的算法库的使用。

1. STL 算法库概述

STL 算法库提供了一组通用算法，这些算法可以应用于任何支持迭代器的容器。它们包括排序、搜索、修改和处理容器内容的功能。以下是一些常见的算法分类：

• 排序算法：如 sort、stable_sort、partial_sort 等
• 查找算法：如 find、binary_search 等
• 变换算法：如 transform、replace 等
• 归并算法：如 merge、set_intersection 等

2. 排序算法的使用

排序是最常用的算法之一。我们可以使用 std::sort 函数来对容器中的元素进行排序。下面是一个简单的示例：

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

int main() {
    std::vector<int> vec = {5, 3, 8, 1, 2};
    
    // 使用 std::sort 对 vec 进行排序
    std::sort(vec.begin(), vec.end());

    // 输出排序后的结果
    std::cout << "排序后的结果：";
    for (int n : vec) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

2.1 自定义排序

我们也可以通过提供自定义比较函数来实现复杂的排序逻辑。例如，我们可以按绝对值排序：

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

bool compareByAbs(int a, int b) {
    return abs(a) < abs(b);
}

int main() {
    std::vector<int> vec = {-5, 3, -8, 1, -2};

    // 使用自定义比较函数进行排序
    std::sort(vec.begin(), vec.end(), compareByAbs);

    // 输出排序后的结果
    std::cout << "按绝对值排序后的结果：";
    for (int n : vec) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

3. 查找算法的使用

STL 还提供了多种查找算法，最常用的是 std::find 和 std::binary_search。

3.1 使用 std::find

std::find 用于在容器中搜索特定值：

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

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

    auto it = std::find(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        std::cout << "找到元素: " << *it << std::endl;
    } else {
        std::cout << "未找到元素" << std::endl;
    }

    return 0;
}

3.2 使用 std::binary_search

如果容器是有序的，可以利用二分查找来提高效率：

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

int main() {
    std::vector<int> vec = {1, 2, 3, 5, 8}; // 已经排序的数组

    if (std::binary_search(vec.begin(), vec.end(), 3)) {
        std::cout << "找到元素 3" << std::endl;
    } else {
        std::cout << "未找到元素 3" << std::endl;
    }

    return 0;
}

4. 变换算法的使用

变换算法主要用于对容器中的元素进行修改或变换。常用的变换算法包括 std::transform 和 std::replace。

4.1 使用 std::transform

下面的例子演示了如何将容器中的每个元素平方：

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::vector<int> result(vec.size()); // 用于存储结果

    std::transform(vec.begin(), vec.end(), result.begin(), [](int x) {
        return x * x;
    });

    std::cout << "平方后的结果：";
    for (int n : result) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

4.2 使用 std::replace

std::replace 用于将容器中的某个元素替换为另一个值：

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

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

    // 替换所有值为 2 的元素为 10
    std::replace(vec.begin(), vec.end(), 2, 10);

    std::cout << "替换后的结果：";
    for (int n : vec) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

5. 归并和集合操作算法

归并和集合操作算法包括 std::merge, std::set_union, std::set_intersection 等。它们能够处理两个或多个有序序列。

5.1 使用 std::merge

以下示例展示了如何合并两个有序向量：

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

int main() {
    std::vector<int> vec1 = {1, 3, 5};
    std::vector<int> vec2 = {2, 4, 6};
    std::vector<int> result(vec1.size() + vec2.size());

    // 合并两个有序向量
    std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());

    std::cout << "合并后的结果：";
    for (int n : result) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    return 0;
}

结论

在本文中，我们探讨了 STL 算法库的多种使用技巧，包括排序、