第10章 泛型算法

作者

第十章 泛型算法

10.1 概述

  1. 泛型算法只依赖迭代器，不依赖容器。

  2. 算法不会改变容器大小，只能修改或移动已有元素。

  3. 插入器（back_inserter、front_inserter、inserter）让算法间接完成插入操作。

  4. find、count 等算法的核心思想就是：

    • 使用迭代器来访问元素，比较或操作元素，而不关心容器的具体类型。

10.2 初始泛型算法

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <ctime>
#include <cstdio>
​
using namespace std;
​
int main()
{
    vector<int> v = { 1, 2, 3, 4, 5 };
    vector<int> v2 = { 6, 7, 8, 9, 10 };
    vector<int> v3(5);
​
    transform(v.begin(), v.end(), v2.begin(), v3.begin(), std::multiplies<>());
​
    for (auto x : v3) {
        cout << x << " ";
    }
}

10.2.1 只读算法

accumulate

定义在 <numeric> 头文件中：

accumulate(first, last, init);

  • first, last：范围

  • init：初始值（也是返回值的类型）

例子：

vector<int> vec = {1, 2, 3, 4};
int sum = accumulate(vec.begin(), vec.end(), 0); // sum = 10

👉 关键点：

  • 第三个参数的类型决定返回值类型和运算规则

    • init=0 → 返回 int

    • init=0LL → 返回 long long

    • init=0.0 → 返回 double

  • 字符串拼接：

vector<string> v = {"C++", " STL", " 算法"};
string res = accumulate(v.begin(), v.end(), string("")); 
// res = "C++ STL 算法"

⚠️ 如果写成 ""（C 字符串字面量，类型是 const char*），会报错，因为 const char* 没有定义 operator+。

练习10.4

accumulate(v.cbegin(), v.cend(), 0) 对 vector<double> 错误： 👉 初值是 int，导致结果被转为 int（丢小数）。 ✔️ 改为 0.0。

练习10.5

对 vector<const char*> 用 equal： 👉 默认比较指针地址，不比较字符串内容。 ✔️ 用 vector<string> 或自定义比较器（strcmp）。

10.2.2 写容器元素的算法

1️⃣ 插入迭代器（insert iterator）

  • 插入迭代器是一种 向容器添加元素的迭代器。

  • 普通迭代器：赋值会覆盖已有元素。

  • 插入迭代器：赋值会调用容器的 insert 或 push_back 增加新元素。

back_inserter

  • 定义在 <iterator> 中。

  • 绑定容器并返回一个插入迭代器。

  • 赋值运算 → 调用 push_back 添加元素。

  • 常用场景：算法输出到一个可能为空或大小不够的容器中。

#include <vector>
#include <algorithm>
#include <iterator>
​
std::vector<int> vec;
std::fill_n(std::back_inserter(vec), 10, 0);  // 向 vec 添加 10 个 0

✅ 好处：保证 算法输出不会越界，适合空容器或不确定大小的容器。

2️⃣ 拷贝算法 copy

  • 功能：把输入范围 [first, last) 的元素复制到输出范围 [d_first, …)。

  • 输出序列至少要能容纳输入序列元素，否则未定义。

  • 返回值：拷贝完成后输出序列的尾后迭代器。

int a1[] = {1,2,3};
int a2[3];
std::copy(a1, a1+3, a2);  // a2 = {1,2,3}

3️⃣ 拷贝变体（如 replace_copy）

  • 功能：保留原序列，将处理后的结果写入新序列。

  • 示例：将序列中所有 0 替换为 42，生成新序列

std::vector<int> ilst = {0,1,0,2};
std::vector<int> ivec;
std::replace_copy(ilst.begin(), ilst.end(), std::back_inserter(ivec), 0, 42);
// ivec = {42,1,42,2}, ilst 不变

✅ 核心记忆

  1. back_inserter → 自动 push_back，不用担心容器大小。

  2. copy → 输出序列必须够大，否则越界；返回尾后迭代器。

  3. replace_copy / transform_copy → 保留原序列，写到新容器，可用 back_inserter 避免越界。

解答：這個斷言依然是成立的。因為改變容器大小的是 back_inserter 這個迭代器本身，而不是演算法。

  • 標準庫演算法（如 copy, fill_n）是通用的，它們只對迭代器進行操作，並不知道底層容器的具體類型和細節。

  • back_inserter 是一個迭代器配接器 (iterator adaptor)。當演算法嘗試透過這個迭代器賦值時（例如執行 *it = value），back_inserter 會攔截這個操作，並將其轉換為對容器的 push_back(value) 呼叫。

  • 因此，是 back_inserter 的特殊行為導致了容器大小的改變，而演算法本身依然遵守不直接改變容器大小的規則。

练习 10.10：你认为算法不改变容器大小的原因是什么？

这是一个关于 C++ STL 设计哲学的重要问题。标准库中的泛型算法（如 unique, remove 等）通常不直接改变容器的大小，主要有以下几个核心原因：

  1. 解耦与泛化（Decoupling and Generalization）：

    • STL 的核心设计思想是将算法与数据结构（容器）分离。算法通过迭代器来操作数据序列，它们不关心也不需要知道自己正在操作的是 vector、list、deque 还是一个普通的C风格数组。

    • 如果算法被设计为可以改变容器的大小，那么它就必须与特定的容器类型绑定，因为它需要调用该容器的成员函数（如 push_back, erase）来增删元素。这将严重破坏算法的通用性，使其无法应用于所有类型的序列。

  2. 容器自身负责内存管理（Containers Manage Their Own Memory）：

    • 如何改变大小（即如何分配/释放内存、移动元素）是容器自身的职责。不同容器的实现机制天差地别。

    • 例如，std::vector 在删除元素时可能不需要释放内存，只是逻辑上缩小大小；而在内存不足时增加元素则可能需要重新分配一块更大的内存并将所有现有元素复制过去。

    • std::list（双向链表）增删元素则只是修改几个指针，不需要移动其他元素。

    • 泛型算法对这些内部实现一无所知，也无法高效、安全地执行这些操作。将大小变更的权力交给容器自己，是最高效、最安全的设计。

  3. 效率与性能（Efficiency and Performance）：

    • 让算法只负责移动元素，而不进行实际的删除操作，通常效率更高。例如，std::remove 算法将所有要保留的元素移动到序列的前端，这只需要一次遍历。

    • 如果 remove 每找到一个要删除的元素就立即从 vector 中删除它，那么每次删除都可能导致该元素之后的所有元素向前移动一次，从而产生 O(N^2) 的时间复杂度。

    • 而现在的“移动-擦除”范式（erase-remove idiom）将移动和擦除分离：remove 负责 O(N) 的移动，erase 负责 O(N) 的擦除，总复杂度为 O(N)，效率远高于前者。

10.3 定制操作

10.3.1 向算法传递函数

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
​
using namespace std;
​
void print_vector(const std::string& message, const std::vector<std::string>& vec) {
    std::cout << "--- " << message << " ---" << std::endl;
    for (const auto& s : vec) {
        std::cout << s << " ";
    }
    std::cout << "\n" << std::endl;
}
​
void elimDups(vector<string>& words)
{
    sort(words.begin(), words.end()); // 按字母顺序排序
    auto end_unique = std::unique(words.begin(), words.end()); // 删除重复元素
    words.erase(end_unique, words.end()); // 删除多余的元素
}
​
int main()
{
    std::vector<std::string> words = { "the", "quick", "red", "fox", "jumps", "over", "the", "slow", "red", "turtle" };
​
    print_vector("初始数据", words);
​
    elimDups(words);
    print_vector("删除重复元素后", words);
​
    stable_sort(words.begin(), words.end(), [](const string& a, const string& b)
        {
            return a.size() < b.size(); // 按字符串长度排序
        });
​
    print_vector("按长度排序后", words);
​
    return 0;
}

10.4 再探迭代器

10.4.1 插入迭代器

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <algorithm>

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

    std::list<int> lst1, lst2, lst3;

    std::copy(vec.begin(), vec.end(), std::inserter(lst1, lst1.begin()));
    std::copy(vec.begin(), vec.end(), std::back_inserter(lst2));
    std::copy(vec.begin(), vec.end(), std::front_inserter(lst3));

    std::cout << "inserter: ";
    for (auto i : lst1) std::cout << i << " ";
    std::cout << "\nback_inserter: ";
    for (auto i : lst2) std::cout << i << " ";
    std::cout << "\nfront_inserter: ";
    for (auto i : lst3) std::cout << i << " ";
    std::cout << std::endl;
}

10.4.2 iostream迭代器

想象一下，C++ 的世界里有两大独立的“部落”：

  1. 容器部落 (Containers)：如 vector, list, deque 等。它们擅长存储数据，并且通过一种叫做迭代器 (iterator) 的“通用语言”来暴露自己的成员，让大家可以统一地访问（遍历、读写）。

  2. 流部落 (Streams)：如 cin, cout, ifstream, ofstream 等。它们是数据流动的“管道”，负责与外部世界（键盘、屏幕、文件）打交道。

在没有 IO 迭代器之前，这两个部落老死不相往来。如果你想把 cin 的数据装进 vector，你得写一个 while 循环，手动 >> 读取，再手动 push_back。

IO 迭代器的诞生，就是为了给这两个部落架起一座桥梁。 它们是一种特殊的“适配器”或“翻译官”，它能让流（cin, cout）伪装成一个容器，说出迭代器这种“通用语言”。

这样一来，那些只会和迭代器打交道的泛型算法（如 copy, accumulate, sort）就突然发现：“哇！我不仅能操作 vector，现在连 cin 和 cout 都能直接操作了！”

  1. istream_iterator：把输入流变成一个“只读”容器

istream_iterator 就像一个智能的“水龙头”，你把它装在输入流（如 cin 或文件流）上。

  • 它的工作：每当你需要一个数据时，它就自动从流里 >> 读取一个数据出来给你。

  • 它的“末端”：当流里没有数据了（遇到文件结尾 EOF，或者输入了错误类型的数据导致流状态出错），这个“水龙头”就自动变成了“已关紧”状态。这个状态就是所谓的尾后迭代器。

解读关键代码

传统方式（手动循环）：

vector<int> vec;
int val;
while (cin >> val) {
    vec.push_back(val);
}

这很直观，但不够“泛型”。

使用 istream_iterator 的方式 1 (模拟循环)：

istream_iterator<int> in_iter(cin); // 把水龙头装在 cin 上
istream_iterator<int> eof;          // 一个代表“已关紧”状态的空水龙头

while (in_iter != eof) {
    vec.push_back(*in_iter++); // 最烧脑的一行
}

我们来深度剖析 *in_iter++ 这一行：

  1. in_iter++ (后置递增): 这是核心动作。它告诉水龙头：“请从流中读取下一个整数，并做好准备。” 但因为是后置递增，这个表达式本身返回的是递增前的迭代器状态，也就是包含了刚刚读出来的值的那个状态。

  2. \* (解引用): 这个动作说：“把我刚才读出来的那个值给我！”

所以，*in_iter++ 连起来的完整含义是：“从流中读取一个新值备用，并返回上一个刚读好的值。” 这确保了我们能拿到当前值，同时迭代器也前进了。

使用 istream_iterator 的方式 2 (最优雅的方式)：

C++

istream_iterator<int> in_iter(cin);
istream_iterator<int> eof;
vector<int> vec(in_iter, eof); // 用一对迭代器直接构造 vector

这行代码完美体现了 IO 迭代器的价值。它对 vector 的构造函数说： “你好，vector。现在我给你一个范围，它的开头是 in_iter（连接着 cin 的水龙头），结尾是 eof（水龙头关紧的状态）。请你把自己填满，数据源就是这个范围。” vector 的构造函数就会自动地、不断地从 in_iter 取水，直到 in_iter 到达 eof 状态为止。代码极其简洁、优雅。

与算法结合：

C++

// 计算从标准输入读取的所有整数的和
int sum = accumulate(istream_iterator<int>(cin), istream_iterator<int>(), 0);

accumulate 算法根本不知道 cin 是什么东西，它只认识迭代器。通过 istream_iterator，我们成功地让 cin “说”了算法能听懂的语言。

懒惰求值 (Lazy Evaluation) 这是一个实现细节，但很重要。意思是，当你创建 istream_iterator<int> in(cin); 时，程序不一定马上就从 cin 读取第一个数。它可能会“偷懒”，等到你第一次真正需要数据（即第一次做 *in 操作）时，才去读取。这在大多数情况下没区别，但在一些高级应用中（比如多线程同步读取同一个流）需要注意。

  1. ostream_iterator：把输出流变成一个“只写”容器

ostream_iterator 则像一个“自动写入器”，你把它连接到输出流（如 cout 或文件流）上。

  • 它的工作：你每给它一个值，它就自动用 << 把这个值写入到流中。

  • 它的特点

    ：

    • 没有“尾后”状态，因为它永远可以接受写入。

    • 创建时必须绑定到一个流。

    • 可以额外提供一个分隔符（一个C风格字符串），每次写入数据后，它会自动跟着写入这个分隔符。

解读关键代码

传统方式：

C++

for (int val : vec) {
    cout << val << " ";
}

使用 ostream_iterator 的方式：

C++

// 创建一个写入器，连接到 cout，每次写入后自动加一个空格
ostream_iterator<int> out_iter(cout, " ");

for (int val : vec) {
    *out_iter++ = val; // 最标准、最清晰的写法
}

我们来剖析 *out_iter++ = val;：

  1. = val: 这是核心动作，赋值操作触发了 ostream_iterator 的 operator=。这个运算符重载的内部实现就是 stream << val;。

  2. * 和 ++: 对于 ostream_iterator 来说，解引用 * 和递增 ++ 实际上什么也不做。它们只是为了在形式上与其他迭代器保持一致，让代码看起来更“像”一个标准的迭代器循环。这使得你的代码可以轻松地在不同类型的迭代器之间切换。

所以，你甚至可以写成 out_iter = val;，效果完全一样，但不推荐，因为它破坏了泛型代码的一致性。

与算法结合（最优雅的方式）：

C++

// 把 vec 里的所有元素拷贝到 out_iter，out_iter 会自动把它们写入 cout
copy(vec.cbegin(), vec.cend(), ostream_iterator<int>(cout, " "));

copy 算法愉快地将 vec 的内容“拷贝”到了 cout，它根本不知道自己操作的是屏幕输出流，它只知道自己是在操作一个合法的、满足要求的“输出迭代器”。

总结：iostream 迭代器的精髓

  1. 适配器模式：它们是连接“容器/算法”世界和“IO流”世界的桥梁。

  2. 泛型编程的体现：它们让流能够参与到泛型算法中，极大地提高了代码的复用性和优雅性。

  3. 抽象化：它们将底层的 >> 和 << 操作，抽象成了标准的迭代器操作（*, ++, ==, !=），隐藏了实现细节。

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

int main(int argc, char *argv[])
{
    if (argc != 2)
    {
        std::cerr << "用法：" << argv[0] << " <输入文件>" << std::endl;
        return 1;
    }

    std::ifstream infile(argv[1]);
    if (!infile)
    {
        std::cerr << "无法打开文件：" << argv[1] << std::endl;
        return -1;
    }

    std::istream_iterator<std::string> in_iter(infile);
    std::istream_iterator<std::string> eof;

    std::vector<std::string> svec(in_iter, eof);

    std::cout << "读取到的字符串有：" << std::endl;
    
    copy(svec.cbegin(), svec.cend(), std::ostream_iterator<std::string>(std::cout, " "));
    std::cout << std::endl;

    return 0;
}

10.4.3 反向迭代器

#include <iostream>
#include <list>
#include <algorithm> // for std::find

int main() {
    std::list<int> lst = { 0, 1, 2, 0, 3, 4, 0, 5 };

    // 使用 rbegin() 和 rend() 定义一个反向的搜索范围
    // find 会在这个反向范围中查找第一个 0
    auto last_zero_rit = std::find(lst.rbegin(), lst.rend(), 0);

    // 检查是否找到了
    if (last_zero_rit != lst.rend())
    {
        auto last_zero_it = --(last_zero_rit.base());
		std::cout << "Last zero found at position: " << *std::next(last_zero_it) << std::endl;
    }

    return 0;
}

发表评论