第三节 · 瑞士军刀 · 泛型算法

标准库不仅提供了容器，还提供了一套强大的算法。这些算法可以作用于几乎任何容器，就像一把瑞士军刀，一套工具解决多种问题。

---

算法的基本使用

算法定义在 <algorithm> 头文件中，通过迭代器操作容器：

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main()
{
    vector<int> v = {5, 2, 8, 1, 9, 3, 7};
    
    // 排序
    sort(v.begin(), v.end());
    // v: 1, 2, 3, 5, 7, 8, 9
    
    // 查找
    auto it = find(v.begin(), v.end(), 5);
    if (it != v.end())
        cout << "找到 5，位置: " << (it - v.begin()) << endl;
    
    // 反转
    reverse(v.begin(), v.end());
    // v: 9, 8, 7, 5, 3, 2, 1
    
    return 0;
}

---

只读算法

这些算法不修改容器内容：

vector<int> v = {1, 2, 3, 4, 5, 2, 3, 2};

// 计数
int count2 = count(v.begin(), v.end(), 2);
cout << "2 出现了 " << count2 << " 次" << endl;  // 3

// 条件计数
int countEven = count_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
});
cout << "偶数个数: " << countEven << endl;  // 3

// 查找
auto it = find(v.begin(), v.end(), 3);
auto it2 = find_if(v.begin(), v.end(), [](int x) {
    return x > 4;
});

// 全部/任一/无一满足
bool allPositive = all_of(v.begin(), v.end(), [](int x) { return x > 0; });
bool anyEven = any_of(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
bool noneNegative = none_of(v.begin(), v.end(), [](int x) { return x < 0; });

// 遍历
for_each(v.begin(), v.end(), [](int x) {
    cout << x << " ";
});
cout << endl;

// 累加（在 <numeric> 中）
#include <numeric>
int sum = accumulate(v.begin(), v.end(), 0);
cout << "总和: " << sum << endl;

---

修改算法

这些算法会修改容器或输出容器：

vector<int> v = {1, 2, 3, 4, 5};

// 填充
fill(v.begin(), v.end(), 0);  // 全部填充为 0

// 替换
vector<int> v2 = {1, 2, 3, 2, 5};
replace(v2.begin(), v2.end(), 2, 100);  // 将所有 2 替换为 100
// v2: 1, 100, 3, 100, 5

// 条件替换
replace_if(v2.begin(), v2.end(), [](int x) { return x > 50; }, 0);

// 变换
vector<int> v3 = {1, 2, 3, 4, 5};
transform(v3.begin(), v3.end(), v3.begin(), [](int x) {
    return x * x;
});
// v3: 1, 4, 9, 16, 25

// 复制
vector<int> src = {1, 2, 3, 4, 5};
vector<int> dest(5);
copy(src.begin(), src.end(), dest.begin());

// 条件复制
vector<int> evens;
copy_if(src.begin(), src.end(), back_inserter(evens), [](int x) {
    return x % 2 == 0;
});
// evens: 2, 4

// 移除（不会真正删除，只是移动到末尾）
vector<int> v4 = {1, 2, 3, 2, 5, 2};
auto newEnd = remove(v4.begin(), v4.end(), 2);
v4.erase(newEnd, v4.end());  // 真正删除
// v4: 1, 3, 5

// 去重（需要先排序）
vector<int> v5 = {1, 2, 2, 3, 3, 3, 4};
auto uniqueEnd = unique(v5.begin(), v5.end());
v5.erase(uniqueEnd, v5.end());
// v5: 1, 2, 3, 4

---

排序算法

vector<int> v = {5, 2, 8, 1, 9, 3, 7};

// 完全排序
sort(v.begin(), v.end());  // 升序
sort(v.begin(), v.end(), greater<int>());  // 降序

// 稳定排序（保持相等元素的相对顺序）
stable_sort(v.begin(), v.end());

// 部分排序（只排序前 N 个）
partial_sort(v.begin(), v.begin() + 3, v.end());
// 前 3 个是最小的 3 个，且有序

// 找第 N 个元素（nth_element）
vector<int> v2 = {5, 2, 8, 1, 9, 3, 7};
nth_element(v2.begin(), v2.begin() + 3, v2.end());
// v2[3] 是第 4 小的元素，左边都比它小，右边都比它大

// 判断是否有序
bool sorted = is_sorted(v.begin(), v.end());

---

二分查找算法

用于已排序的序列：

vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};

// 查找是否存在
bool found = binary_search(v.begin(), v.end(), 5);  // true

// 查找下界（第一个不小于 target 的位置）
auto lower = lower_bound(v.begin(), v.end(), 5);
// lower 指向 5

// 查找上界（第一个大于 target 的位置）
auto upper = upper_bound(v.begin(), v.end(), 5);
// upper 指向 6

// 查找范围
auto range = equal_range(v.begin(), v.end(), 5);
// range.first 指向 5，range.second 指向 6

---

最值算法

vector<int> v = {5, 2, 8, 1, 9, 3, 7};

// 最大最小值
auto maxIt = max_element(v.begin(), v.end());
auto minIt = min_element(v.begin(), v.end());
cout << "最大: " << *maxIt << ", 最小: " << *minIt << endl;

// 同时获取
auto [minmax] = minmax_element(v.begin(), v.end());
// minmax.first 是最小，minmax.second 是最大

// 两个值的最大最小
int a = 5, b = 3;
cout << max(a, b) << endl;  // 5
cout << min(a, b) << endl;  // 3

// 限制范围（C++17）
int x = 15;
cout << clamp(x, 0, 10) << endl;  // 10（限制在 0-10 之间）

---

排列算法

vector<int> v = {1, 2, 3};

// 下一个排列
do {
    for (int x : v)
        cout << x << " ";
    cout << endl;
} while (next_permutation(v.begin(), v.end()));
// 1 2 3
// 1 3 2
// 2 1 3
// 2 3 1
// 3 1 2
// 3 2 1

// 上一个排列
prev_permutation(v.begin(), v.end());

// 随机打乱
#include <random>
random_device rd;
mt19937 g(rd());
shuffle(v.begin(), v.end(), g);

---

自定义比较函数

大多数算法都支持自定义比较：

struct Person
{
    string name;
    int age;
};

vector<Person> people = {
    {"Alice", 25},
    {"Bob", 30},
    {"Carol", 20}
};

// 按年龄排序
sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.age < b.age;
});

// 按名字排序
sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.name < b.name;
});

// 查找
auto it = find_if(people.begin(), people.end(), [](const Person& p) {
    return p.name == "Bob";
});

---

习题

• 使用算法找出数组中第二大的元素。

• 使用算法统计字符串中各字符出现的次数。

• 使用 next_permutation 生成字符串的所有排列。