C++ 编程入门 - Day 4

引言

在今天的学习中，我们将深入探索 C++ 标准库中的 <algorithm> 头文件。这是 C++ 标准库中非常强大的一部分，提供了大量的算法函数，使我们能够高效地操作数据集合。

1. `<algorithm>` 详细介绍

<algorithm> 是 C++ 标准库中提供的算法集合头文件。它包含了各种常用的算法，如排序、查找、复制、删除等。这些算法可以与各种容器（如 vector、数组等）配合使用，提供了高效的操作方式。

主要算法分类：

排序算法：sort()、stable_sort()、partial_sort() 等
查找算法：find()、binary_search()、lower_bound() 等
删除和复制算法：remove()、copy()、swap() 等
变换算法：transform()、merge()、replace() 等
堆操作：make_heap()、push_heap()、pop_heap() 等
排列和生成：next_permutation()、prev_permutation() 等

2. 经典示例

示例 1：排序和查找

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

using namespace std;

int main() {
    vector<int> numbers = {5, 2, 8, 1, 9, 3};

    // 排序
    sort(numbers.begin(), numbers.end());
    cout << "Sorted numbers: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // 二分查找
    int target = 8;
    if (binary_search(numbers.begin(), numbers.end(), target)) {
        cout << "Found " << target << endl;
    } else {
        cout << "Did not find " << target << endl;
    }

    // 查找第一个大于等于 6 的元素
    auto it = lower_bound(numbers.begin(), numbers.end(), 6);
    if (it != numbers.end()) {
        cout << "First element >= 6: " << *it << endl;
    }

    return 0;
}

示例 2：删除和替换

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

using namespace std;

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

    cout << "Original numbers: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // 统计值为 2 的元素数量
    int count = count(numbers.begin(), numbers.end(), 2);
    cout << "Number of 2's: " << count << endl;

    // 删除所有值为 2 的元素
    auto last = remove(numbers.begin(), numbers.end(), 2);
    numbers.erase(last, numbers.end());

    cout << "After removing 2's: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

示例 3：变换和合并

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

using namespace std;

int main() {
    vector<int> numbers1 = {1, 3, 5, 7};
    vector<int> numbers2 = {2, 4, 6, 8};
    vector<int> merged;

    // 合并两个已排序的向量
    merge(numbers1.begin(), numbers1.end(), 
          numbers2.begin(), numbers2.end(),
          back_inserter(merged));

    cout << "Merged numbers: ";
    for (int num : merged) {
        cout << num << " ";
    }
    cout << endl;

    // 对每个元素进行变换（乘以 2）
    vector<int> doubled;
    transform(merged.begin(), merged.end(), 
              back_inserter(doubled),
              [](int x) { return x * 2; });

    cout << "Doubled numbers: ";
    for (int num : doubled) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

示例 4：排列和生成

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

using namespace std;

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

    cout << "Permutations of 1, 2, 3:" << endl;

    // 输出所有排列
    do {
        for (int num : numbers) {
            cout << num << " ";
        }
        cout << endl;
    } while (next_permutation(numbers.begin(), numbers.end()));

    return 0;
}

3. 常见的问题和回答

问题 1：如何自定义排序标准？

可以使用自定义比较函数或 Lambda 表达式：

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

using namespace std;

// 自定义比较函数，按降序排序
bool compare(int a, int b) {
    return a > b;
}

int main() {
    vector<int> numbers = {5, 2, 8, 1, 9, 3};

    // 使用自定义比较函数
    sort(numbers.begin(), numbers.end(), compare);
    cout << "Sorted in descending order: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    // 使用 Lambda 表达式
    sort(numbers.begin(), numbers.end(), 
         [](int a, int b) { return a < b; });
    cout << "Sorted in ascending order: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

问题 2：如何使用算法操作自定义类型？

可以为自定义类型实现比较运算符，或者提供自定义比较函数：

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

using namespace std;

struct Person {
    string name;
    int age;
};

// 自定义比较函数，按年龄排序
bool compareAge(const Person& p1, const Person& p2) {
    return p1.age < p2.age;
}

int main() {
    vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35}
    };

    sort(people.begin(), people.end(), compareAge);

    cout << "Sorted by age: " << endl;
    for (const Person& p : people) {
        cout << p.name << " (" << p.age << ")" << endl;
    }

    return 0;
}

问题 3：如何避免算法操作中的常见错误？

边界错误：确保迭代器范围是有效的
内存管理：使用算法时要注意内存的正确分配和释放
未初始化对象：确保对象在使用前已正确初始化
性能考虑：根据数据规模选择合适的算法

总结

在今天的学习中，我们深入探索了 C++ 标准库中的 <algorithm> 头文件。我们学习了：

<algorithm> 的基本概念和主要算法分类
四个经典示例：排序和查找、删除和替换、变换和合并、排列和生成
常见问题的解答，包括自定义排序标准、操作自定义类型和避免常见错误

<algorithm> 是 C++ 标准库中非常强大的一部分，掌握好这些算法将使您的程序更加高效和简洁。

练习建议： 1. 使用算法实现一个简单的统计程序 2. 编写一个程序，使用算法处理学生成绩 3. 实现一个简单的数据过滤和转换程序