第19章 STL算法与迭代器

进阶 👤 已掌握STL容器的开发者 🔧 高效处理容器数据，编写简洁通用的业务逻辑

本章你将学到

迭代器的本质与五种分类
常用STL算法的使用场景与参数搭配
如何组合算法与迭代器解决实际问题

核心概念迭代器算法

想象一下，你有一个装满各种零件的工具箱（容器），现在你需要从中找出所有生锈的零件、给它们除锈、再按大小排序。如果用手一个个翻找处理，效率很低。STL算法就是一套自动化工具（如筛选器、打磨机、分拣机），而迭代器就是连接工具箱和这些工具的机械臂，它能精准地指向并取出零件。

技术上，迭代器是一种抽象，它提供了访问容器元素的统一方式，屏蔽了不同容器（数组、链表、树）的内部结构差异。STL算法是一组独立于具体容器的通用函数模板，它们通过迭代器来操作数据，实现了“数据”与“操作”的分离。

迭代器：连接容器与算法的桥梁

迭代器不仅仅是“指针的泛化”。在项目中，我曾因为混淆迭代器类型导致编译错误，花了半天才定位。理解它的分类至关重要。根据支持的操作，迭代器分为五个等级，形成一个“能力金字塔”。

随机访问迭代器
(vector, deque, array)

↓

双向迭代器
(list, set, map)

↓

前向迭代器
(forward_list)

↓

输入迭代器
(istream_iterator)

↔

输出迭代器
(ostream_iterator)

上层迭代器拥有下层迭代器的所有能力。例如，std::vector<int>::iterator是随机访问迭代器，你可以对它做加法it + 5；但std::list<int>::iterator只是双向迭代器，只能it++或it--。这是新手常踩的坑。

五种迭代器能力对比
迭代器类别	读(*it)	写(*it=)	递增(++)	递减(--)	随机访问(it+n)	典型代表
输入迭代器	✓	×	✓	×	×	`istream_iterator`
输出迭代器	×	✓	✓	×	×	`ostream_iterator`
前向迭代器	✓	✓	✓	×	×	`forward_list`
双向迭代器	✓	✓	✓	✓	×	`list`, `set`, `map`
随机访问迭代器	✓	✓	✓	✓	✓	`vector`, `deque`, 数组指针

常见误区

误用无效迭代器：在容器插入/删除元素后（尤其是vector），之前保存的迭代器可能失效，继续使用会导致未定义行为。
混淆迭代器与索引：对list或map的迭代器进行it + 2操作会编译失败，应使用std::advance(it, 2)。
忽略算法返回值：像std::remove这样的算法并不真的删除元素，它返回一个指向新逻辑结尾的迭代器，需要结合erase使用。

STL算法：数据处理的瑞士军刀

STL算法大约有100多个，位于<algorithm>等头文件中。它们不直接操作容器，而是通过迭代器范围[first, last)来工作。这个“左闭右开”的区间表示法，是C++标准库的统一约定。

关键点：算法不修改容器结构

绝大多数算法只操作容器内的元素值，或移动它们的位置，但不会增加或删除容器本身的“槽位”。改变容器大小（如真的删除）需要容器自身的成员函数（如erase）配合。

我们通过一个具体例子来看算法如何工作。假设我们有一个存储传感器读数（整数）的vector，需要过滤掉异常值（大于1000），然后计算平均值。

// 示例：使用算法处理数据
#include <algorithm>
#include <vector>
#include <iostream>
#include <numeric> // 包含 accumulate

int main() {
    std::vector<int> sensorData = {450, 1200, 780, 95, 1500, 320};

    // 1. 使用 remove_if “移除”大于1000的元素。注意，它并不真的删除。
    auto newEnd = std::remove_if(sensorData.begin(), sensorData.end(),
                                [](int val) { return val > 1000; });

    // 2. 真正地从容器中删除被“移除”的元素
    sensorData.erase(newEnd, sensorData.end());

    // 3. 使用 accumulate 计算剩余元素的总和
    double sum = std::accumulate(sensorData.begin(), sensorData.end(), 0.0);
    double average = sum / sensorData.size();

    std::cout << "有效数据平均值: " << average << std::endl;
    return 0;
}

这个例子展示了典型的“算法+迭代器+容器成员函数”的组合拳。实际开发中，90%的数据处理需求都能用几种核心算法解决。

查找与判断

find/find_if：按值或条件查找。
count/count_if：统计匹配元素个数。
binary_search：在已排序范围中二分查找。
应用：检查用户ID是否存在，统计日志中错误级别条目。

修改与填充

copy/copy_if：复制元素到另一位置。
fill/generate：填充或生成数据。
transform：对每个元素应用函数，结果存到另一处。
应用：数据格式转换，初始化缓冲区，生成测试数据。

排序与重排

sort/stable_sort：排序（要求随机访问迭代器）。
partial_sort：部分排序（如取Top N）。
reverse/rotate：反转或旋转序列。
应用：排行榜排序，打乱题目顺序，循环移位。

集合与归约

set_union/set_intersection：求集合并集/交集。
accumulate：累加（可自定义二元操作，实现归约）。
inner_product：计算内积。
应用：合并标签系统，计算总和/平均值，向量点乘。

编者提示：本章的transform、remove_if等算法中使用的匿名函数是Lambda表达式。如果你想深入了解其强大和灵活的语法，可以在后续学习中重点关注第27章 Lambda表达式。

迭代器适配器：赋予迭代器新能力

迭代器适配器是包装了现有迭代器的特殊迭代器，它们改变了迭代器的默认行为。最常用的有三种，它们能极大简化代码。

原始迭代器

→

迭代器适配器包装

→

具有新行为的迭代器

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

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

    // 1. 反向迭代器 (reverse_iterator)
    // 从后向前遍历
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << " "; // 输出: 5 4 3 2 1
    }

    // 2. 插入迭代器 (inserter, back_inserter, front_inserter)
    // 将复制操作变为插入操作，避免目标容器空间不足
    std::vector<int> target;
    std::copy(vec.begin(), vec.end(), std::back_inserter(target));

    // 3. 流迭代器 (istream_iterator, ostream_iterator)
    // 直接从流读取或向流写入，非常简洁
    std::cout << "\n向量内容: ";
    std::copy(target.begin(), target.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    return 0;
}

我在一个日志分析项目中大量使用了back_inserter。当时需要从多个文件读取日志ID并合并去重，使用copy加back_inserter到vector，再配合sort和unique，代码比手动循环清晰得多，性能也更好。

性能考量：算法选择与迭代器类别

算法的效率常与迭代器类别相关。std::sort要求随机访问迭代器，因为它需要快速跳到任意位置。如果你对std::list调用sort，编译会通过（因为list有成员函数sort()），但如果你错误地使用了全局的std::sort(list.begin(), list.end())，编译器会报出一大堆模板错误。对于链表，应使用其成员函数list.sort()，它使用了归并排序，更适合链表结构。

动手试一试

创建一个std::vector<std::string>，包含一些单词，如{"apple", "banana", "cherry", "date", "elderberry"}。
使用std::find_if和Lambda表达式，查找第一个长度大于5的单词。
使用std::transform将所有单词转换为大写，并将结果存储到一个新的vector中。（提示：使用::toupper，注意函数指针或Lambda的用法）。
使用std::copy_if和std::back_inserter，将所有以字母‘a’或‘A’开头的单词复制到第三个vector中。
使用std::accumulate计算所有单词的总字符数。

通过这个练习，你将熟悉算法、迭代器、Lambda和适配器的联合使用。

检验你的理解

给定std::list<int> myList，以下哪项操作是无效的？
A. auto it = myList.begin(); ++it;
B. auto it = myList.begin(); it = it + 2;
C. std::sort(myList.begin(), myList.end());
D. myList.sort();
std::remove算法执行后，容器的大小会改变吗？如果不改变，如何真正地删除元素？
std::back_inserter(container)返回的是什么类型的迭代器？它主要解决了什么问题？

本章小结

迭代器是泛型指针，分为输入、输出、前向、双向、随机访问五类，不同容器提供不同能力的迭代器，这决定了哪些算法可用。
STL算法通过迭代器范围工作，遵循[first, last)左闭右开约定，它们通常不改变容器结构，修改容器大小需配合erase等成员函数。
掌握核心算法家族：查找（find）、排序（sort）、修改（transform、copy）、归约（accumulate），能解决绝大多数数据处理任务。
迭代器适配器是强大工具：反向迭代器、插入迭代器、流迭代器能极大简化特定场景下的代码，如反向遍历、动态插入、流式IO。
组合使用是关键：高效C++代码的典型模式是“容器 + 算法 + 迭代器（适配器） + Lambda”，这比手写循环更安全、更清晰、更易维护。

意见反馈

C++ 教程

C++基础

面向对象

STL与进阶

现代C++

实战进阶

第19章 STL算法与迭代器