c++ algorithm库

C++ 标准库中的 <algorithm> 库是一个功能强大且灵活的工具集，提供了大量的算法和操作，用于处理各种容器（如数组、向量、列表等）中的元素。<algorithm> 库中的算法可以用于排序、查找、遍历、修改、合并、计数等操作，极大地简化了编程工作，提高了代码的可读性和效率。本文将详细介绍 <algorithm> 库中的常用算法，并探讨其在实际编程中的应用。

1. 排序算法

排序是计算机科学中最基本的问题之一，<algorithm> 库提供了多种排序算法，其中最常用的是 std::sort。

1.1 std::sort

std::sort 是一种高效的排序算法，通常使用快速排序（QuickSort）或混合排序（Hybrid Sorting）算法实现。它的基本用法如下：

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {4, 2, 5, 3, 1};
    std::sort(vec.begin(), vec.end());
    // vec 现在是 {1, 2, 3, 4, 5}
    return 0;
}

std::sort 默认使用 < 运算符进行升序排序，但也可以通过传递自定义的比较函数来实现降序排序或其他复杂的排序规则。

bool compare(int a, int b) {
    return a > b; // 降序排序
}

int main() {
    std::vector<int> vec = {4, 2, 5, 3, 1};
    std::sort(vec.begin(), vec.end(), compare);
    // vec 现在是 {5, 4, 3, 2, 1}
    return 0;
}

1.2 std::stable_sort

std::stable_sort 是一种稳定的排序算法，即它保持相等元素的相对顺序。这在某些应用场景中非常重要，例如在对对象进行多条件排序时。

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {4, 2, 5, 3, 1};
    std::stable_sort(vec.begin(), vec.end());
    // vec 现在是 {1, 2, 3, 4, 5}
    return 0;
}

2. 查找算法

查找算法用于在容器中查找特定元素或满足特定条件的元素。

2.1 std::find

std::find 用于在容器中查找特定元素，返回指向该元素的迭代器。如果未找到，则返回 end() 迭代器。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = std::find(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    return 0;
}

2.2 std::binary_search

std::binary_search 用于在已排序的容器中执行二分查找。它返回一个布尔值，表示是否找到目标元素。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    bool found = std::binary_search(vec.begin(), vec.end(), 3);
    if (found) {
        std::cout << "Found" << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    return 0;
}

3. 遍历和修改算法

<algorithm> 库提供了多种遍历和修改容器的算法。

3.1 std::for_each

std::for_each 用于对容器中的每个元素执行指定的操作。

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

void print(int n) {
    std::cout << n << " ";
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::for_each(vec.begin(), vec.end(), print);
    // 输出: 1 2 3 4 5
    return 0;
}

3.2 std::transform

std::transform 用于对容器中的每个元素进行转换，并将结果存储到另一个容器中。

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

int square(int n) {
    return n * n;
}

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(), square);
    // result 现在是 {1, 4, 9, 16, 25}
    return 0;
}

4. 合并和划分算法

合并和划分算法用于将容器中的元素进行合并或划分。

4.1 std::merge

std::merge 用于将两个已排序的容器合并为一个已排序的容器。

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

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());
    // result 现在是 {1, 2, 3, 4, 5, 6}
    return 0;
}

4.2 std::partition

std::partition 用于将容器中的元素划分为满足特定条件的部分和不满足条件的部分。

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

bool is_even(int n) {
    return n % 2 == 0;
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5, 6};
    auto it = std::partition(vec.begin(), vec.end(), is_even);
    // vec 现在是 {2, 4, 6, 1, 3, 5}
    return 0;
}

5. 计数和统计算法

计数和统计算法用于对容器中的元素进行计数或统计。

5.1 std::count

std::count 用于统计容器中等于特定值的元素个数。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 2, 2, 4};
    int count = std::count(vec.begin(), vec.end(), 2);
    std::cout << "Count: " << count << std::endl; // 输出: 3
    return 0;
}

5.2 std::accumulate

std::accumulate 用于对容器中的元素进行累加或其他累积操作。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    std::cout << "Sum: " << sum << std::endl; // 输出: 15
    return 0;
}

6. 其他常用算法

<algorithm> 库还提供了许多其他常用算法，如 std::min_element、std::max_element、std::reverse、std::unique 等。

6.1 std::min_element 和 std::max_element

std::min_element 和 std::max_element 分别用于查找容器中的最小元素和*元素。

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

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9};
    auto min_it = std::min_element(vec.begin(), vec.end());
    auto max_it = std::max_element(vec.begin(), vec.end());
    std::cout << "Min: " << *min_it << ", Max: " << *max_it << std::endl;
    // 输出: Min: 1, Max: 9
    return 0;
}

6.2 std::reverse

std::reverse 用于反转容器中的元素顺序。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::reverse(vec.begin(), vec.end());
    // vec 现在是 {5, 4, 3, 2, 1}
    return 0;
}

6.3 std::unique

std::unique 用于移除容器中的连续重复元素，通常与 std::sort 结合使用以移除所有重复元素。

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

int main() {
    std::vector<int> vec = {1, 2, 2, 3, 3, 3, 4, 5, 5};
    auto last = std::unique(vec.begin(), vec.end());
    vec.erase(last, vec.end());
    // vec 现在是 {1, 2, 3, 4, 5}
    return 0;
}

7. 自定义算法

<algorithm> 库中的算法通常可以通过传递自定义的函数或 lambda 表达式来实现更复杂的操作。例如，std::sort 可以接受自定义的比较函数，std::transform 可以接受自定义的转换函数等。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::sort(vec.begin(), vec.end(), [](int a, int b) {
        return a > b; // 降序排序
    });
    // vec 现在是 {5, 4, 3, 2, 1}
    return 0;
}

8. 总结

<algorithm> 库是 C++ 标准库中非常重要的组成部分，提供了丰富的算法和操作，能够极大地简化编程工作。通过熟练掌握 <algorithm> 库中的各种算法，程序员可以编写出更加高效、简洁和可维护的代码。本文介绍了 <algorithm> 库中的常用算法，包括排序、查找、遍历、修改、合并、划分、计数和统计等操作，并探讨了其在实际编程中的应用。希望本文能够帮助读者更好地理解和使用 <algorithm> 库，提升编程技能和代码质量。