第22章 - 算法和迭代器

嗨，朋友！我是长安。

STL提供了强大的算法库，让我们可以高效地处理容器数据。这一章学习迭代器和常用算法。

🔍 迭代器（Iterator）

迭代器是访问容器元素的通用方式，类似于指针。

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

int main() {
    vector<int> nums = {10, 20, 30, 40, 50};
    
    // begin() 和 end()
    cout << "使用迭代器遍历：";
    for (auto it = nums.begin(); it != nums.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 反向迭代器
    cout << "反向遍历：";
    for (auto it = nums.rbegin(); it != nums.rend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    return 0;
}

输出：

使用迭代器遍历：10 20 30 40 50
反向遍历：50 40 30 20 10

🔧 常用算法

所有算法都在 <algorithm> 头文件中。

1. 排序 - sort()

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

int main() {
    vector<int> nums = {30, 10, 50, 20, 40};
    
    // 升序排序
    sort(nums.begin(), nums.end());
    cout << "升序：";
    for (int n : nums) cout << n << " ";
    cout << endl;
    
    // 降序排序
    sort(nums.begin(), nums.end(), greater<int>());
    cout << "降序：";
    for (int n : nums) cout << n << " ";
    cout << endl;
    
    return 0;
}

2. 查找 - find()

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

int main() {
    vector<int> nums = {10, 20, 30, 40, 50};
    
    auto it = find(nums.begin(), nums.end(), 30);
    
    if (it != nums.end()) {
        cout << "找到 30，位置：" << (it - nums.begin()) << endl;
    } else {
        cout << "未找到" << endl;
    }
    
    return 0;
}

3. 统计 - count()

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

int main() {
    vector<int> nums = {10, 20, 10, 30, 10, 40};
    
    int cnt = count(nums.begin(), nums.end(), 10);
    cout << "10 出现了 " << cnt << " 次" << endl;
    
    return 0;
}

4. 反转 - reverse()

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

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    
    reverse(nums.begin(), nums.end());
    
    cout << "反转后：";
    for (int n : nums) cout << n << " ";
    cout << endl;
    
    return 0;
}

5. 最值 - max_element, min_element

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

int main() {
    vector<int> nums = {30, 10, 50, 20, 40};
    
    auto maxIt = max_element(nums.begin(), nums.end());
    auto minIt = min_element(nums.begin(), nums.end());
    
    cout << "最大值：" << *maxIt << endl;
    cout << "最小值：" << *minIt << endl;
    
    return 0;
}

6. 累加 - accumulate()

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

int main() {
    vector<int> nums = {10, 20, 30, 40, 50};
    
    int sum = accumulate(nums.begin(), nums.end(), 0);
    cout << "总和：" << sum << endl;
    
    return 0;
}

🌟 实战案例1：学生成绩处理

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

struct Student {
    string name;
    double score;
};

int main() {
    vector<Student> students = {
        {"张三", 85.5},
        {"李四", 92.0},
        {"王五", 78.5},
        {"赵六", 95.0},
        {"孙七", 88.0}
    };
    
    // 按成绩降序排序
    sort(students.begin(), students.end(), 
         [](const Student& a, const Student& b) {
             return a.score > b.score;
         });
    
    cout << "成绩排名：" << endl;
    for (int i = 0; i < students.size(); i++) {
        cout << i + 1 << ". " << students[i].name 
             << " - " << students[i].score << endl;
    }
    
    // 计算平均分
    double sum = 0;
    for (auto& s : students) {
        sum += s.score;
    }
    double avg = sum / students.size();
    cout << "\n平均分：" << avg << endl;
    
    // 统计及格人数
    int passCount = count_if(students.begin(), students.end(),
                             [](const Student& s) {
                                 return s.score >= 60;
                             });
    cout << "及格人数：" << passCount << endl;
    
    return 0;
}

🎯 实战案例2：数据去重

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

int main() {
    vector<int> nums = {10, 20, 10, 30, 20, 40, 10};
    
    cout << "原始数据：";
    for (int n : nums) cout << n << " ";
    cout << endl;
    
    // 排序
    sort(nums.begin(), nums.end());
    
    // 去重
    auto last = unique(nums.begin(), nums.end());
    nums.erase(last, nums.end());
    
    cout << "去重后：";
    for (int n : nums) cout << n << " ";
    cout << endl;
    
    return 0;
}

📚 常用算法总结

算法	功能	头文件
`sort()`	排序	algorithm
`find()`	查找	algorithm
`count()`	统计	algorithm
`reverse()`	反转	algorithm
`max_element()`	最大值	algorithm
`min_element()`	最小值	algorithm
`accumulate()`	累加	numeric
`unique()`	去重	algorithm
`count_if()`	条件统计	algorithm

🎯 Lambda表达式

Lambda表达式可以作为算法的参数，非常方便。

// 基本语法
[捕获列表](参数列表) { 函数体 }

// 示例
sort(nums.begin(), nums.end(), 
     [](int a, int b) { return a > b; });  // 降序排序

🎉 恭喜！

你已经完成了所有STL的学习！现在你可以：

熟练使用各种容器
掌握常用算法
提高编程效率

🚀 下一步

太棒了！理论知识已经学完了！

现在是时候通过实战项目来巩固所学知识了！

➡️ 实战项目