泛型算法 - 从泛型到函数绑定与迭代器拓展

什么是泛型

泛型是一种编程规范，它具有较高的抽象级别。泛型是描述一类函数，任何实现必要方法的对象都可以使用泛型函数。在一些其他语言中，会定义有接口的概念，它实际为一组函数的集合，任何符合全部函数的类都称为符合这个接口的。

在 C++ 标准库中存在大量的泛型函数，它们通常用于操作容器，这些泛型函数具有相同的特性，它们都将迭代器作为其主要参数，因此任何容器只要拥有足够支持的迭代器都可以使用泛型函数。

泛型函数的定义实际比较广泛，而在 C++ 中泛型通常特指迭代器实现的通用算法，其中常用的泛型算法就包括：std::find、std::sort 等，使用过这些函数的都清楚，它们的前两个参数均为迭代器对象。另外，在定义泛型时，还需要模板元语法的支持，不过本章节将着重介绍泛型的使用，我们暂时不会介绍如何定义自己的泛型。

初识迭代器

前面讲到，在 C++ 的泛型函数中，它们几乎都以迭代器作为其参数，而泛型函数要求对象具有相同的支持，换句话说它们必须满足接口（尽管 C++ 中并没有接口的概念）。那么我们首先需要了解一些基本的迭代器，了解它们具有哪些支持，因此可以用于哪些泛型函数。

迭代器类型	迭代器描述	来自哪些容器
随机访问迭代器	支持随机访问，实现 `+=`、`-=`、`*` 方法。	`vector` / `deque` / 数组
双向访问迭代器	支持链式访问，实现 `++`、`--`、`*` 方法。	`list` / `map` / `set`
前向访问迭代器	支持前向访问，实现 `++`、`*` 方法。	`forward_list`
只读迭代器	无法修改迭代器底层。	`const` 容器 / 容器的 `cxx` 迭代器
反向迭代器	内部实现将方向反向。	容器的 `rxx` 迭代器

这里注意到有些迭代器不支持随机访问，有些迭代器不支持修改，它们在一些泛型函数中将不被支持。这些基本猜测算法实现就可以判断，后面也将介绍。

另外值得注意的是：

数组虽然并不存在迭代器，但指针依然支持必要的操作，本文将指针归类为随机访问迭代器。
反向迭代器事实上与是否具有相应支持无关，但它也作为一种迭代器类型存在，必要时可以实现翻转等。
一些容器不被迭代器支持，因此不能用于泛型，如 queue / stack / priority_queue。更确切地，它们属于容器适配器，而非容器。

泛型分类与规范

这里我们将将泛型进行分类，并且列举一些常见的泛型函数，最后总结泛型的通用问题。

泛型分类

只读泛型，只需为只读迭代器
- std::find(begin, end, val)，在 $\left[\text{begin},~\text{end}\right)$ 间返回第一个值与 $\text{val}$ 相同的迭代器，找不到返回 $\text{end}$ 。
- std::accumulate(begin, end, init)，对 $\left[\text{begin},~\text{end}\right)$ 间累加（+=），其初始值为 $\text{init}$ ，计算类型与 $\text{init}$ 一致。
- std::equal(begin, end, begin2)，判断 $\left[\text{begin}, \text{end}\right)$ 是否与 $\text{begin2}$ 开始的区间逐一相等，返回布尔类型。注意， $\text{begin2}$ 被假定与 $\left[\text{begin}, \text{end}\right)$ 有相同的可访问长度（否则可能产生错误），同样比较的长度由 $\left[\text{begin}, \text{end}\right)$ 确定。
赋值泛型，只需为前向迭代器
- std::fill(begin, end, val)，将 $\left[\text{begin},~\text{end}\right)$ 全部赋值为 $\text{val}$ 。
- std::copy(begin, end, begin2)，将 $\left[\text{begin},~\text{end}\right)$ 全部赋值到 $\text{begin2}$ ，同样假设具有足够的可访问长度。
- std::replace(begin, end, old, new)，将 $\left[\text{begin},~\text{end}\right)$ 中值 $\text{old}$ 替换为值 $\text{new}$ 。
重排泛型，最好具有随机访问迭代器，有些只要求前向迭代器
- std::unique(begin, end)，在 $\left[\text{begin},~\text{end}\right)$ 之间去重，返回指向最后一个去重后的迭代器。它假设数据已经是排序的，且它不会作 $\text{.resize}$ 操作，只是返回迭代器。返回迭代器后的元素应该是无效的，其顺序是未定义的。它只要求前向迭代器。
- std::sort(begin, end)，对 $\left[\text{begin},~\text{end}\right)$ 区间排序。用户还可以向最后再传入函数参数，用于自定义排序。它要求随机访问迭代器。
删除泛型，不应该存在删除泛型，因为迭代器不被赋予删除支持。

泛型规范

在前面我们列举的众多泛型函数中，它们有着相同规范，不管是标准库支持的泛型还是用户定义泛型，都应该满足这样的泛型规范。它们可以列举为：

func(begin, n, args...)， $n$ 通常表示长度，这一类泛型通常命名为 $\text{xxx\_n}$ 。
func(begin, end, args...)，只需指定一个区间的泛型。
func(begin, end, begin2, args...)，需要指定两个区间的泛型，这将假设第二区间与第一区间大小相同。
func(begin, end, begin2, end2, args...)，需要指定两个区间的泛型，并且这两个区间通常不要求同样长。

（这里 args 指一些与区间描述无关的参数）

最后，需要注意的是，由于泛型用于通用支持，其实现也是通用的，但通用算法并不是最优的。如果对象存在专用算法，即成员方法，那么它通常是更优的，例如 std::list 的 unique。

匿名函数

在前面我们注意到，一些泛型支持用户传入自定义函数，这使得泛型函数具有更好的拓展性和通用性。然而，泛型中的函数定义通常是短小的，这为编写者带来一些麻烦。本节将介绍匿名函数（lambda 表达式），下面先提供两个例子：

std::vector<std::string> vec{
    "Mike", 
    "John", 
    "JamhusTao", 
    "GreatLiangpi", 
    "Jan", 
    "Matin"
};
std::for_each(vec.begin(), vec.end(), [](const std::string &s) { 
    cout << s << endl; 
});  // 打印列表
std::sort(vec.begin(), vec.end(), [](const std::string &x, const std::string &y) -> bool { 
    return x.size() < y.size(); 
});  // 升序排序

基础语法

匿名函数的基础语法可以说是相当抽象。例如：[](){} 定义了一个合法的匿名函数，我们可以简化为 []{}；而 []{}() 首先定义一个匿名函数，然后调用它。我们将在下面介绍它的具体语法：

1
2
3

[捕获列表](参数列表) -> 返回类型 {代码块};  // 完整结构
[捕获列表](参数列表) {代码块};  // 自动推导返回值, 建议显式指定
[捕获列表] -> 返回类型 {};  // 如果参数列表为空

// 匿名函数可赋值, 这样做可以让函数体嵌入上下文 (但一般不这么做)
std::function<int(int)> func = [](int x) { return x & 3; };
cout << func(3) << endl;
int(*func)(int) = [](int x) { return x & 3; };  // 同样合法
// 定义匿名函数时调用也是合法的 (cpper 似乎不喜欢这么做)
cout << [](int x) { return x & 3; }(10) << endl;

捕获列表

匿名函数可以访问所有全局变量，这与函数是一样的。但另一方面，匿名函数还可以捕获局部变量，这是其相对函数的优势之一。但另一方面匿名函数可以访问全局变量，但默认不可访问局部变量，这种让匿名函数具有访问局部变量方式的称为捕获列表。

int x = 0;
int main() {
    []() { x++; }();  // 正确, 全局变量可访问
    return 0;
}

int x = 0;
// ! 此处均为定义时调用, 仅用作演示, 一般不这么做
[]() { x++; }();   // 错误, 局部变量 x 未捕获
[&]() { x++; }();  // 正确

符号	功能
`[]`	空捕获列表
`[&, var, ...]`	按拷贝捕获 `var` 等变量（可为空），其余全部按引用捕获
`[=, &var, ...]`	按引用捕获 `var` 等变量（可为空），其余全部按拷贝捕获
`[&var1, var2, ...]`	全部指定捕获方式，其余不捕获

最后，按拷贝捕获的变量，在匿名函数内部默认是 const 的，如果需要修改它必须加上 mutable 关键字。这里注意区分类 const 函数、类 mutable 变量和匿名 mutable 函数，它们确实很容易混淆。

1
2
3

int x = 0;
[=]() -> void { x++; }();  // 错误, 按拷贝捕获默认是 const 的
[]() mutable -> void { x++; }();  // 正确

Bind 参数绑定

std::bind 可以理解为从一个函数到另一个绑定映射，它在泛型中有与匿名函数相似的作用。

1 2	using namespace std::placeholders; std::sort(words.begin(), words.end(), std::bind(isShorter, _2, _1)); // 逆序排序

std::bind 函数绑定需要引入 std::placeholders 来取代原本参数的位置，就如上面一个示例所示 std::placeholders::_1 表示绑定函数的第一个参数等。在使用 std::bind 是一定记得引入 std::placeholders，我们后面将不再提醒。

std::function<bool(const std::string &, const std::string &)> func = std::bind(isShorter, _2， _1);
// 这两者是等价的
func("abc", "def");
isShorter("def", "abc");

1 2	// 它也可以用来缩减一些参数 std::for_each(vec.begin(), vec.end(), std::bind(printf, "%.2f ", _1));

最后，仅仅使用 std::bind 无法传递一些语义，必须借助一些包装器（wrapper）将其传入。它们是 std::ref 和 std::cref 分别用于包装引用和常引用，值得注意的是占位量不需要包装。

std::string test = "Test Stream.";
std::ostream &print(std::ostream &os, const std::string &s);

int main() {
    std::bind(print, std::cout);  // 将拷贝
    std::bind(print, std::ref(std::cout), _1);  // 正确, 包装 std::cout
    std::bind(print, _1, std::cref(test));  // 正确, 包装 test
    std::bind(print, std::ref(std::cout), std::cref(_1))  // _1 无需包装
    return 0;
}

拓展迭代器

插入迭代器

插入迭代器总是插入元素，也就是说它的访问操作始终在做插入操作。插入迭代器主要分为以下三种：

类型	描述
`back_inserter`	迭代器赋值操作实际被重载为 `.push_back`
`front_inserter`	迭代器赋值操作实际被重载为 `.push_front`
`inserter`	迭代器赋值操作实际被重载为 `.insert`，当然它初始化时需额外指定插入迭代器

另外，需要注意的是，在插入迭代器中，其 *it / ++it / it++ 方法都将返回本身（没有 --it 方法），不删除这些方法是这用于支持泛型。当然也因此插入迭代器只能插入而无法取值。插入迭代器唯一有效的方法是 it = x，它将调用 push_back / push_front / insert 方法。

std::vector<int> vec1{1, 2, 3, 4};
std::vector<int> vec2{0};
std::copy(vec1.begin(), vec1.end(), std::back_inserter(vec2));  // 从 vec1 拷贝到 vec2
// {0, 1, 2, 3, 4}
// std::copy(vec1.begin(), vec1.end(), vec2.begin());  // 错误: 访问越界. 与上一个对比
std::copy(vec1.begin(), vec1.end(), std::front_inserter(vec2));  // 语法正确, 但 CE, vector 没有 push_front
std::copy(vec1.begin(), vec1.end(), std::inserter(vec2, vec2.begin()));  // 总在 vec2.begin() 前插入
// {1, 2, 3, 4, 0}

最后简单提一下 insert_iterator 和 inserter 的区别。std::inserter 是一个构造器，用于构造一个 std::insert_iterator 对象；它俩的关系就好像 std::make_shared 和 std::shared_ptr 的关系。

流迭代器

流迭代器主要分为 std::istream_iterator 和 std::ostream_iterator 两类。它们将流对象模拟成容器从中读取，流迭代器与插入迭代器一样，是前向访问迭代器，它们都无法反向。

另外，值得注意的是，流迭代器的默认初始化表示流的结束，这与我们常见的容器迭代器是不同的。常见容器迭代器使用 .end（尾后迭代器）表示结束，而其默认迭代器则是不可用的。

std::ifstream ifs("example.txt", std::ios::in);
std::istream_iterator<int> it(ifs);  // 流迭代器只能指定一种类型, 这里指定为 int
std::vector<int> vec(it, decltype(it)());  // decltype(it)() 使用默认初始化, 表示流结束
for (int x : vec) cout << x << ' '; cout << endl;

std::ofstream ofs("example.txt", std::ios::out);
std::ostream_iterator<int> it(ofs);  // 同样只能指定一种类型
std::vector<int> vec{1, 2, 3, 4, 5};
std::copy(vec.begin(), vec.end(), it);  // 输出到流
// 12345

// 基础用法
std::istream_iterator<int> it1(ifs);
int x = *it1++;
std::ostream_iterator<int> it2(ofs);
*it2++ = x;

移动迭代器

在进行拷贝操作时，我们通常会调用类的拷贝赋值函数。而移动迭代器则提供了一种将所有拷贝操作替换为移动语义的迭代器，该方法是 std::make_move_iterator。下面是一个简单实验：

std::vector<Cls> src(10);  // 这里 Cls 是某个自定义类
std::vector<Cls> dst(10);
std::copy(src.begin(), src.end(), dst.begin());  // 调用拷贝赋值函数
std::copy(std::make_move_iterator(src.begin()), std::make_move_iterator(src.end()), dst.begin());  // 调用移动赋值函数

事实上，移动迭代器也可以认为是一个包装器（wrapper），它实际重写了原迭代器的 operator* 方法，在其外面套了一层 std::move。