第26章：迭代器与算法——C++标准库的“万能接口”

说实话，我刚开始学C++那会儿，对迭代器这东西挺不屑的。不就是个指针的包装吗？后来真上了项目，才发现自己太年轻了。迭代器就像一把万能钥匙，把容器和算法这两座宝库给串了起来。今天咱们就来聊聊这个核心话题。

迭代器分类：五大家族

迭代器不是铁板一块。C++标准库把迭代器分成了五类，每一类都有自己的“超能力”。我习惯把它们想象成不同级别的驾照：

类别	能力	典型代表	我能用它干嘛
输入迭代器	只读，单向	istream_iterator	从流里读数据，读完就没了
输出迭代器	只写，单向	ostream_iterator	往流里写数据，一次性的
前向迭代器	读写，单向	forward_list的迭代器	可以反复遍历，但只能往前走
双向迭代器	读写，双向	list、set的迭代器	能++也能--，灵活多了
随机访问迭代器	读写，任意跳转	vector、deque的迭代器	想跳哪跳哪，跟数组一样爽

你想想看，为什么要有这么多分类？说白了，就是给算法提供“能力保证”。算法知道自己需要什么级别的迭代器，就能选择最高效的实现方式。

常用算法：三板斧

标准库里的算法少说上百个，但常用的就那么几个。我挑三个最有代表性的说说。

sort：排序界的扛把子

sort要求随机访问迭代器，所以vector、deque、数组都能用，但list不行。list有自己的sort成员函数。

#include <algorithm>
#include <vector>

std::vector<int> vec = {4, 2, 5, 1, 3};
std::sort(vec.begin(), vec.end());
// 结果：1, 2, 3, 4, 5

// 自定义排序规则
std::sort(vec.begin(), vec.end(), std::greater<int>());
// 结果：5, 4, 3, 2, 1

我记得有一次项目里要对几十万条记录排序，一开始用的冒泡排序，跑一次要十几秒。换成std::sort后，秒出结果。嗯，这就是算法的力量。

find：大海捞针

find只需要输入迭代器，所以几乎所有容器都能用。它返回一个迭代器，指向找到的第一个元素。如果没找到，就返回end()。

std::vector<std::string> names = {"Alice", "Bob", "Charlie"};
auto it = std::find(names.begin(), names.end(), "Bob");
if (it != names.end()) {
    // 找到了！
    std::cout << *it << " is in the list\n";
}

copy：复制粘贴的专家

copy把一段范围内的元素复制到另一个地方。它需要输入迭代器和输出迭代器。

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(5);
std::copy(src.begin(), src.end(), dst.begin());

// 更酷的用法：直接输出到流
std::copy(src.begin(), src.end(), 
          std::ostream_iterator<int>(std::cout, " "));
// 输出：1 2 3 4 5

accumulate：累加的艺术

accumulate在<numeric>头文件里，不是<algorithm>。它把一段范围内的元素累加起来。

#include <numeric>

std::vector<int> nums = {1, 2, 3, 4, 5};
int sum = std::accumulate(nums.begin(), nums.end(), 0);
// sum = 15

// 自定义操作：累乘
int product = std::accumulate(nums.begin(), nums.end(), 1, 
                              std::multiplies<int>());
// product = 120

Lambda与算法：天作之合

C++11引入lambda后，算法用起来就顺手多了。以前写个自定义排序规则，得单独写个函数或函数对象，麻烦得很。现在一行lambda搞定。

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

// 按绝对值排序
std::sort(vec.begin(), vec.end(), 
          [](int a, int b) { return std::abs(a) < std::abs(b); });

// 找到第一个大于5的元素
auto it = std::find_if(vec.begin(), vec.end(), 
                       [](int x) { return x > 5; });

// 把所有偶数翻倍
std::transform(vec.begin(), vec.end(), vec.begin(),
               [](int x) { return x % 2 == 0 ? x * 2 : x; });

我曾经在代码审查时看到有人写了个50行的函数对象，就为了做个简单的过滤。我建议他换成lambda，代码瞬间从50行缩到3行。你想想看，哪个维护起来更爽？

知识体系总览

下面这张图把迭代器、算法和lambda的关系梳理清楚了。我画图时特意把迭代器分类放在中间，因为它是连接容器和算法的桥梁。

实战：把知识串起来

光说不练假把式。咱们来个综合例子，把今天讲的东西都用上。

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

int main() {
    // 原始数据
    std::vector<int> scores = {85, 92, 78, 95, 88, 76, 91};
    
    // 1. 用lambda和sort排序（降序）
    std::sort(scores.begin(), scores.end(), 
              [](int a, int b) { return a > b; });
    
    // 2. 用copy输出排序结果
    std::cout << "排序后: ";
    std::copy(scores.begin(), scores.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
    
    // 3. 用find_if找到第一个低于80分的
    auto it = std::find_if(scores.begin(), scores.end(),
                           [](int x) { return x < 80; });
    if (it != scores.end()) {
        std::cout << "第一个低于80分的是: " << *it << "\n";
    }
    
    // 4. 用accumulate算平均分
    int sum = std::accumulate(scores.begin(), scores.end(), 0);
    double avg = static_cast<double>(sum) / scores.size();
    std::cout << "平均分: " << avg << "\n";
    
    // 5. 用transform给所有人加5分
    std::transform(scores.begin(), scores.end(), scores.begin(),
                   [](int x) { return std::min(x + 5, 100); });
    
    std::cout << "加分后: ";
    std::copy(scores.begin(), scores.end(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
    
    return 0;
}

这个例子我特别喜欢，因为它把今天讲的核心知识点都串起来了。你想想看，如果没有迭代器，没有算法，没有lambda，这段代码得写多长？

好了，迭代器与算法这块就聊到这儿。记住一句话：迭代器是C++标准库的“通用接口”，算法是“通用操作”，lambda是“灵活定制”。这三者配合起来，写出的代码既简洁又高效。

---

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