第22章迭代器与算法

课程目录第22章迭代器与算法

第22章迭代器与算法：迭代器分类与常用算法

迭代器，说白了就是STL的“万能胶水”。它把容器和算法粘在一起。我个人觉得，理解迭代器是掌握C++泛型编程的关键一步。你想想看，没有迭代器，std::sort怎么知道从哪里开始排、排到哪里结束？

22.1 迭代器分类

迭代器不是一种，而是五种。每种能干的事不一样。我刚开始学的时候也搞混过，后来在项目里踩了坑才真正记住。

类别	方向	可读	可写	重复遍历	随机访问
输入迭代器	单向	✔	✘	✘	✘
输出迭代器	单向	✘	✔	✘	✘
前向迭代器	单向	✔	✔	✔	✘
双向迭代器	双向	✔	✔	✔	✘
随机访问迭代器	双向	✔	✔	✔	✔

核心规律：后一种迭代器包含前一种的全部能力。随机访问迭代器是最强的，输入/输出是最弱的。

22.1.1 输入迭代器

只能读，不能写。而且只能向前走一次。比如从键盘读数据，你读完了就没了，不能回头再读一遍。我曾在处理网络流数据时用过它——数据流过来，读完就丢弃，正好合适。

22.1.2 输出迭代器

只能写，不能读。也是单向一次。比如std::back_inserter就是个典型的输出迭代器。你只管往里塞数据，不用管它里面原来有什么。

22.1.3 前向迭代器

既能读又能写，还能重复遍历。单向的。比如std::forward_list的迭代器就是前向的。嗯，这里要注意：前向迭代器支持++，但不支持--。

22.1.4 双向迭代器

比前向多了一个能力：可以后退。std::list、std::set、std::map的迭代器都是双向的。你可以用--往回走。

22.1.5 随机访问迭代器

最强的迭代器。支持+、-、[]、<等操作。std::vector、std::deque、std::array的迭代器都属于这一类。你可以直接跳转到任意位置，就像数组下标一样。

避坑指南：我曾经在项目里用std::list的迭代器调用了std::sort，结果编译报错。后来才意识到std::sort要求随机访问迭代器，而std::list只提供双向迭代器。正确的做法是用std::list::sort成员函数。

22.2 常用算法

STL算法大概有上百个，但常用的就那么几个。我个人习惯把算法分成三类：查找、排序、遍历。下面逐个说。

22.2.1 `std::find` — 线性查找

最朴素的查找算法。从头找到尾，找到了就返回迭代器，找不到就返回end()。时间复杂度O(n)。

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

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
    
    auto it = std::find(vec.begin(), vec.end(), 5);
    if (it != vec.end()) {
        std::cout << "找到了: " << *it << std::endl;
    } else {
        std::cout << "没找到" << std::endl;
    }
    return 0;
}

个人经验：如果容器是有序的，别用find，用std::binary_search或std::lower_bound。我在一个性能敏感的项目里，把find换成lower_bound后，查找速度提升了十几倍。

22.2.2 `std::sort` — 排序

默认升序排序。要求随机访问迭代器。底层是内省排序（introsort），综合了快速排序、堆排序和插入排序的优点。

#include <algorithm>
#include <vector>

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

// 升序
std::sort(vec.begin(), vec.end());

// 降序（使用函数对象）
std::sort(vec.begin(), vec.end(), std::greater<int>());

// 自定义排序规则
std::sort(vec.begin(), vec.end(), [](int a, int b) {
    return a % 10 < b % 10;  // 按个位数排序
});

注意：std::sort不是稳定排序。如果需要稳定排序（相等元素的相对顺序不变），请用std::stable_sort。我曾经在排序用户列表时忽略了这一点，结果相同分数的用户顺序每次都不一样，被测试同学提了bug。

22.2.3 `std::for_each` — 遍历

对范围内的每个元素执行操作。说白了就是for循环的函数式版本。

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

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

// 打印每个元素
std::for_each(vec.begin(), vec.end(), [](int n) {
    std::cout << n << " ";
});

// 修改每个元素（传引用）
std::for_each(vec.begin(), vec.end(), [](int& n) {
    n *= 2;
});

22.2.4 `std::accumulate` — 累加

在<numeric>头文件中。默认做加法，也可以自定义操作。

#include <numeric>
#include <vector>

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

// 求和：1+2+3+4+5 = 15
int sum = std::accumulate(vec.begin(), vec.end(), 0);

// 求积：1*2*3*4*5 = 120
int product = std::accumulate(vec.begin(), vec.end(), 1, 
                              [](int a, int b) { return a * b; });

// 字符串拼接
std::vector<std::string> words = {"Hello", " ", "World", "!"};
std::string result = std::accumulate(words.begin(), words.end(), std::string());

22.3 Lambda表达式

Lambda是C++11引入的匿名函数对象。说白了就是临时写一个函数，用完了就扔。我刚开始觉得这玩意儿花里胡哨的，后来用顺手了才发现真香。

22.3.1 基本语法

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

捕获列表控制lambda能访问外部哪些变量。嗯，这里要注意：

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

#include <algorithm>
#include <vector>

int threshold = 5;
std::vector<int> vec = {3, 7, 2, 8, 1, 6};

// 按值捕获 threshold
auto count = std::count_if(vec.begin(), vec.end(), 
    [threshold](int n) { return n > threshold; });

// 按引用捕获，可以在lambda内部修改
std::for_each(vec.begin(), vec.end(), 
    [&threshold](int& n) { n += threshold; });

避坑指南：我曾经在lambda里按引用捕获了一个临时变量，结果lambda执行时那个变量已经销毁了。程序崩溃得莫名其妙。记住：按引用捕获要确保变量的生命周期足够长。

22.3.2 Lambda与算法结合

Lambda最大的用处就是配合算法使用。你想想看，以前写排序要单独写一个函数或函数对象，现在一行lambda搞定。

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

struct Person {
    std::string name;
    int age;
};

std::vector<Person> people = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 35}
};

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

// 查找第一个年龄大于30的人
auto it = std::find_if(people.begin(), people.end(),
    [](const Person& p) { return p.age > 30; });

22.3.3 泛型Lambda（C++14）

C++14允许lambda参数使用auto，变成模板化的lambda。我个人觉得这个特性特别实用。

// 泛型lambda，可以接受任意类型
auto add = [](auto a, auto b) { return a + b; };

std::cout << add(3, 4) << std::endl;        // 7
std::cout << add(3.14, 2.86) << std::endl;  // 6.0
std::cout << add(std::string("Hello "), "World") << std::endl;  // Hello World

22.4 综合示例：算法与Lambda实战

下面这个例子综合了本章讲的大部分内容。我在一个日志分析工具里写过类似的代码。

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

struct LogEntry {
    std::string level;   // "INFO", "WARN", "ERROR"
    int code;
    std::string message;
};

int main() {
    std::vector<LogEntry> logs = {
        {"INFO", 200, "Request processed"},
        {"ERROR", 500, "Internal server error"},
        {"WARN", 400, "Bad request"},
        {"ERROR", 503, "Service unavailable"},
        {"INFO", 200, "Health check passed"}
    };
    
    // 1. 统计ERROR数量
    int error_count = std::count_if(logs.begin(), logs.end(),
        [](const LogEntry& e) { return e.level == "ERROR"; });
    std::cout << "错误数: " << error_count << std::endl;
    
    // 2. 按错误码排序
    std::sort(logs.begin(), logs.end(),
        [](const LogEntry& a, const LogEntry& b) {
            return a.code < b.code;
        });
    
    // 3. 提取所有错误码
    std::vector<int> codes;
    std::transform(logs.begin(), logs.end(), std::back_inserter(codes),
        [](const LogEntry& e) { return e.code; });
    
    // 4. 计算平均错误码
    double avg = std::accumulate(codes.begin(), codes.end(), 0.0) / codes.size();
    std::cout << "平均错误码: " << avg << std::endl;
    
    // 5. 打印所有ERROR级别的日志
    std::for_each(logs.begin(), logs.end(), [](const LogEntry& e) {
        if (e.level == "ERROR") {
            std::cout << "[" << e.code << "] " << e.message << std::endl;
        }
    });
    
    return 0;
}

个人习惯：我一般把复杂的lambda单独提取成具名变量，这样代码可读性更好。比如：auto is_error = [](const LogEntry& e) { return e.level == "ERROR"; }; 然后直接传is_error给算法。

好了，迭代器与算法这块就讲到这里。记住：迭代器是桥梁，算法是工具，lambda是粘合剂。三者配合好了，写出来的代码既简洁又高效。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录