22、STL算法与迭代器：算法库（sort、find、copy）、迭代器分类、lambda表达式

好，咱们今天来聊聊STL里最实用的两个东西——算法和迭代器。说实话，我刚学C++那会儿，觉得STL就是个黑盒子，用起来方便，但总搞不清里面怎么回事。后来做项目多了，才慢慢摸到门道。今天我就把这点经验分享给你。

算法库：sort、find、copy

STL算法库，说白了就是一堆现成的函数模板，帮你处理容器里的数据。你不需要自己写循环，不需要自己管理指针，直接调用就行。我个人习惯把算法库分成三类：修改操作、非修改操作、排序相关操作。

sort——排序利器

std::sort 是我用得最多的算法之一。它默认按升序排列，底层用的是快速排序的改进版——内省排序。我在项目中遇到过一个问题：用 sort 对自定义对象排序时，忘了提供比较函数，结果编译报错。嗯，这里要注意，sort 要求随机访问迭代器，所以 list 不能用，得用 list::sort 成员函数。

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

int main() {
    std::vector<int> vec = {4, 2, 5, 1, 3};
    
    // 默认升序
    std::sort(vec.begin(), vec.end());
    
    // 降序：用 lambda 表达式
    std::sort(vec.begin(), vec.end(), [](int a, int b) {
        return a > b;
    });
    
    for (int v : vec) std::cout << v << " ";
    return 0;
}

find——查找元素

std::find 是线性查找，复杂度 O(n)。它返回一个迭代器，指向第一个匹配的元素。如果没找到，就返回 end()。你想想看，如果容器已经排序了，用 std::binary_search 或 std::lower_bound 会快得多。我曾经在日志分析程序里用 find 在百万级数据里找东西，结果慢得不行，后来换成 unordered_set 才解决问题。

std::vector<int> vec = {10, 20, 30, 40, 50};
auto it = std::find(vec.begin(), vec.end(), 30);
if (it != vec.end()) {
    std::cout << "找到了: " << *it << std::endl;
}

copy——复制数据

std::copy 把一段区间的内容复制到另一个地方。它有三个参数：源起始、源结束、目标起始。注意目标容器要有足够的空间，不然会越界。我建议用 std::back_inserter 来自动扩展空间。

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst;

// 自动扩展目标容器
std::copy(src.begin(), src.end(), std::back_inserter(dst));

迭代器分类

迭代器是算法和容器之间的桥梁。说白了，迭代器就像指针的升级版，让你能用统一的方式遍历不同容器。STL 把迭代器分成五类，每一类支持的操作不同。

迭代器类别	支持操作	典型容器
输入迭代器	只读、单向移动（++）	istream_iterator
输出迭代器	只写、单向移动（++）	ostream_iterator
前向迭代器	读写、单向移动	forward_list
双向迭代器	读写、双向移动（++/--）	list、set、map
随机访问迭代器	读写、任意跳转（+n/-n/[]）	vector、deque、array

为什么会这样分类？因为不同容器的内存布局不同。比如 vector 是连续内存，可以随意跳转；list 是链表，只能一步步走。算法会根据迭代器类型选择最优实现。我记得有一次面试，面试官问我 std::sort 为什么不能用在 list 上，我回答因为 list 的迭代器是双向的，不支持随机访问，面试官点了点头。

lambda表达式

lambda 表达式是 C++11 引入的匿名函数对象。说白了，就是临时写一个函数，用完了就扔。我刚开始觉得这玩意儿花里胡哨的，后来发现它在算法里太好用了。

基本语法：[捕获列表](参数列表) -> 返回类型 { 函数体 }

// 最简单的 lambda
auto add = [](int a, int b) { return a + b; };
std::cout << add(3, 4) << std::endl;  // 输出 7

// 捕获外部变量
int threshold = 30;
std::vector<int> scores = {25, 35, 40, 20};
auto count = std::count_if(scores.begin(), scores.end(), 
    [threshold](int s) { return s > threshold; });
std::cout << "超过阈值的人数: " << count << std::endl;

捕获列表有几种方式：

• []：不捕获任何外部变量
• [=]：按值捕获所有外部变量
• [&]：按引用捕获所有外部变量
• [x, &y]：x 按值捕获，y 按引用捕获

知识体系结构图

综合示例：用算法和lambda处理数据

最后，我给你看一个综合例子。这个例子把 sort、find、copy 和 lambda 全用上了。我在做数据分析工具时经常这么写。

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

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"Alice", 85}, {"Bob", 72}, {"Charlie", 90}, {"David", 65}
    };
    
    // 按分数降序排序
    std::sort(students.begin(), students.end(), 
        [](const Student& a, const Student& b) {
            return a.score > b.score;
        });
    
    // 查找第一个分数大于80的学生
    auto it = std::find_if(students.begin(), students.end(),
        [](const Student& s) { return s.score > 80; });
    
    if (it != students.end()) {
        std::cout << "第一个高分学生: " << it->name << std::endl;
    }
    
    // 复制所有及格学生到新容器
    std::vector<Student> passed;
    std::copy_if(students.begin(), students.end(), 
        std::back_inserter(passed),
        [](const Student& s) { return s.score >= 60; });
    
    std::cout << "及格人数: " << passed.size() << std::endl;
    return 0;
}

嗯，到这里你应该对 STL 算法和迭代器有个整体认识了。说白了，算法是工具，迭代器是接口，lambda 是灵活配置。三者配合好了，写出来的代码既简洁又高效。我建议你多写几个小例子练练手，光看是学不会的。