第10章 泛型算法

”算法“：实现了一些经典算法的公共接口，如排序和搜索。

”泛型”：可以用于不同类型的元素和多种容器类型。

1. 初识

除了少数例外，标准库算法都对一个范围内的元素进行操作，称其为“输入范围”。接受输入范围的算法总是使用前两个参数来表示此范围，两个参数分别是指向要处理的第一个元素和尾元素之后位置的迭代器。

算法永远不会改变底层容器的大小。算法本身不会执行容器的操作，它们只会运行于迭代器之上，执行迭代器的操作。

1.1 只读算法

只读取其输入范围内的元素，而不改变元素。

accumulate(vec.begin(), vec.end(), 0)：求和函数

accumulate的第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型。

equal(vec1.cbegin(), vec1.cend(), vec2.cbegin())：相等函数

equal假定第二个序列不比第一个序列短。那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列不短于第一个序列

1.2 写容器元素的算法

算法不检查写操作

一些算法将新值赋予序列中的元素。当我们使用这类算法时，必须注意确保序列原大小不小于我们要求算法写入的元素数目。因为算法本身并不检查写操作，且其自身不可能改变容器的大小。

fill_n(dest, n, val)函数接受一个迭代器、一个计数值和一个值。它将给定值赋予迭代器指向的元素开始的指定个元素。其假定写入指定个元素是安全的：

vector<int> vec;  // 空向量
// 错误，修改vec中的10个不存在的元素
fill_n(vec.begin(), vec.size(), 0);

插入迭代器

一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器。插入迭代器是一种向容器中添加元素的迭代器。通常情况，当我们通过一个 迭代器向容器元素赋值时，值被赋予迭代器指向的元素。而当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素被添加到容器中。

vector<int> vec; 
auto it = back_inserter(vec); 
*it = 42; // vec中现在有一个元素，值为42
fill_n(back_inserter(vec), 10, 0); // 添加10个0到vec的末尾

拷贝算法

拷贝算法是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法。其接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。传递给copy的目的序列至少要包含与输入序列一样多的元素

int a1[] = {0,1,2,3,4};
int a2[sizeof(a1)/sizeof(*a1)];  // a2与a1大小一样
auto ret = copy(begin(a1), end(a1), a2); // 把a1的内容拷贝给a2

1.3 重排容器元素的算法

某些算法会重排容器中元素的顺序，一个明显的例子是sort。假定己有一个 vector, 保存了多个单词，现化简这个vector，使得每个单词只出现一次。

输入：the quick red fox jumps over the slow red turtle

目标输出：fox jumps over quick red slow the turtle

void elimDups(vector<string> &words) {
    sort(words.begin(), words.end());
    auto end_unique = unique(words.begin(), words.end());
    words.erase(end_unique, words.end());
}

消除重复单词

为了消除重复单词，首先将 vector 排序，使得重复的单词都相邻出现。 完成sort后，words的顺序如下：

fox jumps over quick red red slow the the turtle

使用unique

unique算法重排输入序列，将相邻的重复项“消除”，并返回一个指向不重复值范围末尾的迭代器。调用unique后，vector将变成：

fox jumps over quick red slow the turtle ??? ???

words的大小并未改变，它仍有10个元素。但这些元素的顺序改变了——相邻的重复元素被“删除”了。我们将删除打引号是因为 unique 并不真的删除任何元素，它只是覆盖相邻的重复元素，使得不重复元素出现在序列开始部分。unique 返回的迭代器指向最后一个不重复元素之后的位置。此位置之后的元素仍然存在，但我们不知道它们的值是什么。

标准库算法对迭代器而不是容器进行操作。因此，算法不能（直接）添加或删除元素。

使用容器操作删除元素

为了真正地删除无用元素，必须使用容器操作。使用erase删除从end_unique开始直至words末尾的范围内的所有元素。值得注意的是，即使 words 中没有重复单词，这样调用 erase 也是安全的。

2. 定制操作

现需要单词按其长度排序，大小相同的再按字典序排序，为此使用sort的第二个版本，其接受第三个参数，是一个谓词。

谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：一元谓词（unary predicate, 意味着它们只接受单一参数）和二元谓词（binary predicate, 意味着它们有两个参数）。接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型。

接受一个二元谓词参数的 sort 版本用这个谓词代替v来比较元素。提供给 sort的谓词必须满足将在 11.2.2 节中所介绍的条件。当前，只需知道，此操作必须在输入序列中所有可能的元素值上定义一个一致的序。

bool isShorter(const string &s1, const string &s2) {
    return s1.size() < s2.size();
}
sort(words.begin(), words.end(), isShorter);

2.2 lambda表达式

现出现一个新问题：求大于等于一个给定长度的单词有多少，并输出，将此函数命名为biggies。

为了解决此问题，只需要找到第一个大于给定长度的元素，可以使用find_if函数完成此功能，find_if接受一对迭代器以及一个一元谓词，其对输入序列中的每个元素调用这个谓词，但是只接受一个参数的函数无法完成比较给定string和一个长度的大小，为此引入lambda。

一个 lambda 表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。与任何函数类似，一个 lambda 具有一个返回类型、一个参数列表和一个函数体。但与函数不同，lambda 可能定义在函数内部。一个 lambda 表达式具有如下形式 ：

[capture list] (parameter list) -> return type { function body }

其中，capture list(捕获列表) 是一个 lambda 所在函数中定义的局部变量的列表 (通常为空)；return type、parameter 和function body与任何普通函数一样，分别表示返回类型参数列表和函数体。但是，与普通函数不同，lambda 必须使用尾置返回来指定返回类型。可以忽略参数列表和返回类型。

如果lambda的函数体包含任何单一return语句之外的内容，且未指定返回类型，则返回void。

本例中，lambda捕获sz，将string的大小与sz的值相比较：

[sz] (const string &a) 
	{ return a.size() >= sz; };

再调用find_if查找第一个长度大于等于sz的元素：

auto wc = find_if(words.begin(), words.end(), [sz] (const string &a) { return a.size() >= sz; });

最后输出所有满足条件的元素：

for_each(wc, words.end(), [](const string &a) {cout<< s <<" "; });

最终，完整的biggies如下：

void biggies(vector<string> &words, vector<string>::size_type sz) {
    elimDups(words);
    stable_sort(words.begin(), words.end(), [] (const string &a, const string &b) { return a.size() < b.size();});
    // 获取一个迭代器，指向第一个满足size()>=sz的元素
    auto wc = find_if(words.begin(), words.end(), [sz] (const string &a) { return a.size() >= sz; });
    // 计算满足size >= sz的元素的数目
    auto count = words.end() - wc;
    // 打印长度大于等于给定值的单词
    for_each(wc, words.end(), [](const string &s) {cout << s << " ";});
}

2.3 lambda捕获和返回

当定义一个 lambda 时，编译器生成一个与 lambda 对应的新的（未命名的）类类型 。默认情况下，从 lambda 生成的类都包含一个对应该 lambda 所捕获的变量的数据成员。类似任何普通类的数据成员，lambda 的数据成员也在 lambda 对象创建时被初始化 。

类似参数传递，变量的捕获方式也可以是值或引用。此外，还可以隐式捕获，即在捕获列表中写一个&或=，分别表示捕获引用或值捕获。

显示捕获和隐式捕获可以混合使用，但当两者混合时，捕获列表中的第一个元素必须为&或=,且显示捕获的变量必须使用与隐式捕获不同的方式。

当以引用方式捕获一个变量时，必须保证在 lambda 执行时变量是存在的。应当尽量保持 lambda 的变量捕获简单化。

默认情况下，对于一个值被拷贝的变量，lambda 不会改变其值。如果我们希望能改变一个被捕获的变量的值，就必须在参数列表首加上关键字 mutable。

void fcn() {
    size _t v1 = 42;
    auto f = [v1] () mutable {return ++v1; };
    v1 = 0;
    auto j = f(); //j为43
}

默认情况下，如果一个 lambda 体包含 return 之外的任何语句，则编译器假定此 lambda 返回 void 。当需要为一个 lambda 定义返回类型时，必须使用尾置返回类型：

[] (int i) -> int { if (i>0) return i; else return -i;}; //指定返回类型为int

2.4 参数绑定

回顾本节介绍lambda的原因，是因为当时向find_if函数传递的可调用对象必须接受单一参数，但是这又无法完成长度比较的目的。那为了使用函数替代 lambda ，就需要解决利用bind来进行参数绑定。调用bind的一般形式为：

auto newCallable = bind(callable, arg_list);

其中， newCallable本身是一个可调用对象， 是一个逗号分隔的参数列表，对应给定的 callable 的参数。即，当我们调用 newCallable 时，newCallable会调用 callable, 并传 递给它 arg_list 中的参数。

arg_list中的参数可能包含形如_n的名字，其中 n 是一个整数。这些参数是“占位符” ，表示newCallable的参数，_1为newCallable的第一个参数，依此类推。例如：

// check6是一个可调用对象，接受一个string类型的参数
// 并用此string和6来调用check_size
auto check6 = bind(check_size, _1, 6);
string s = "hello";
bool b1 = check6(s); // check6(s)会调用check_size(s,6)

3. 再探迭代器

除了为每个容器定义的迭代器之外，还有额外几种迭代器：

• 插入迭代器：这些迭代器被绑定到一个容器上，可用来向容器插入元素。
• 流迭代器：这些迭代器被绑定到输入或输出流上，可用来遍历所关联的IO流。
• 反向迭代器：这些迭代器向后移动。
• 移动迭代器：移动迭代器中的元素。

3.1 插入迭代器

插入器有三种类型，差异在于元素插入的位置 ：

• back_inserter：创建一个使用push_back的迭代器
• front_inserter：创建一个使用push_front的迭代器
• inserter：创建一个使用insert的迭代器

3.2 iostream迭代器

虽然iostream类型不是容器，但标准库定义了可用于这些IO类型对象的迭代器。istream_iterator读取输入流，ostream_iterator向一个输出流写数据。

3.3 反向迭代器

反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。对于反向迭代器，递增（以及递减）操作的含义会颠倒过来。递增一个反向迭代器（++it）会移动到前一个元素；递减一个迭代器（–it）会移动到下一个元素 。

4. 泛型算法结构

算法所要求的迭代器操作可以分为5个迭代器类别：

大多数算法具有如下4种形式之一：

alg(beg, end, othrt args);

alg(beg, end, dest, other args);

alg(beg, end, beg2, other args);

alg(beg, end, beg2, end2, other args);

与其他容器不同，链表类型 list 和 forward_list 定义了几个成员函数形式的算法。