9.1 泛型算法¶

概述¶

标准库没有为每个顺序容器都定义成员函数来实现诸如查找特定元素、替换或删除一个特定值、重排元素顺序等操作，而是定义了一组泛型算法generic algrithm，大多数算法都定义在头文件algorithm中，标准库还在头文件numeric中定义了一组数值泛型算法：

算法：实现了一些经典算法的公共接口，如排序和搜索
泛型：可以用于不同类型的元素和多种容器类型，不仅包括vector和list等标准库类型，还包括内置的数组类型

Tips：泛型算法永远都不会执行容器的操作，它们只会运行于迭代器之上，执行迭代器的操作。这意味着泛型算法永远不会改变底层容器的大小，但可能改变容器中保存的元素。标准库定义了一类特殊的迭代器，称为插入器inserter，当给这类迭代器赋值时，它们会在底层的容器上执行插入操作。因此当一个算法操作这样一个迭代器时，迭代器可以完成容器添加元素的效果，但算法自身永远不会做这样的操作。

泛型算法类型¶

1. 只读算法¶

一些算法只会读取其输入范围内的元素而不会改变元素，比如find、count和accumulate。对于只读取而不改变元素的算法，通常最好使用cbegin()和cend()。
有一些算法比如equal可以用于确定两个序列是否保存相同的值，接收三个迭代器，前两个表示第一个序列中的元素范围，第三个参数表示第二个序列的首元素：

// roster2中的元素数目至少要和roster1一样多
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

Tips：像equal这种只接收一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少和第一个序列一样长。确保算法不会试图访问第二个序列中不存在的元素是程序员的责任。

2. 写容器元素的算法¶

算法不执行写操作：一个初学者非常容易犯错的地方是在一个空容器上调用fill_n或其他类型的写算法，这种情况下是未定义的
back_inserter：当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素会被添加到容器中
拷贝算法：copy算法是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法，参数中前两个迭代器表示一个输入范围，第三个参数表示目的序列的起始位置

很多算法都提供所谓的“拷贝”版本，这些算法计算新元素的值但是不会将它们放置在输入序列的末尾，而是创建一个新序列保存结果，这样就不会被覆盖掉。例如replace算法可以以将容器所有值为0的元素改成42：

replace(ilist.begin(), ilist.end(), 0, 42);

如果我们希望原序列保持不变，那我们可以使用“拷贝”版本，该算法接受第三个迭代器参数，指出调整后序列的保存位置：

replace_copy(ilist.cbegin(), ilist.cend(), back_inserter(ivec), 0, 42);

3. 重排容器元素的算法¶

有些算法会重排容器中元素的顺序，一个明显的例子是sort，它是利用元素的<运算符来实现排序的。

定制操作¶

1. 向算法传递函数¶

为了让vector支持按长度排序，我们需要使用sort的第二个重载版本，它接收第三个参数，该参数是一个谓词predicate。

谓词是一个可调用的表达式，其返回结果是一个能用做条件的值。

接受一个二元谓词（有两个参数）的sort版本用这个谓词代替<来比较元素：

// 比较函数，用于按长度排序
bool isShorter(const string &s1, cosnt string &s2) {
    return s1.size() < s2.size();
}
// 按长度由短至长排序words
sort(words.begin(), words.end(), isShorter);

2. lambda表达式¶

我们可以向一个算法传递任何类型的可调用对象callable object，到目前为止我们仅使用过两种可调用对象：函数和函数指针。还包括其他两种可调用对象：14章介绍的重载了函数调用运算符的类和lambda表达式。一个lambda表达式表示一个可调用的代码单元，我们将其理解为一个未命名的内联函数，具有返回类型、一个函数列表和一个函数体：

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

我们可以忽略参数列表和返回类型，但必须包括捕获列表和函数体，我们定义一个可调用对象f，它不接受参数直接返回42：

auto f = [] { return 42; }
cout << f() << endl;  // 打印42

我们可以构造一个按长度排序，长度相同的单词维持字典序，空捕获列表表示此lambda不使用它所在函数中的任何局部变量。

// stable_sort稳定排序算法: 维持相等元素的原有顺序
stable_sort(words.begin(), words.end(), 
    [] (const string &a, const string &b)
    { return a.size() < b.size(); });

我们将lambda放在一个函数内，通过捕获列表获取函数中的局部变量，例如我们可以查找第一个长度大于等于sz的元素：

// 获取一个迭代器, 指向第一个满足size() >= sz的元素
auto wc = find(words.begin(), words.end(), 
    [sz](const string &a)
        { return a.size() >= sz; });

3. for_each算法¶

for_each算法接受一个可调用对象，并对输入序列中每个元素调用此对象：

// 获取一个迭代器, 指向第一个满足size() >= sz的元素
auto wc = find(words.begin(), words.end(), 
    [sz](const string &a)
        { return a.size() >= sz; });

// 打印单词，并在每个单词后面接一个空格
for_each(wc, words.end(),
    [](const string &s) {cout << s << " ";});

泛型算法结构¶

1. 5类迭代器¶

算法所要求的迭代器操作可以分为5个迭代器类别，每个算法都会对它的每个迭代器参数指明须提供哪类迭代器：

输入迭代器：只读，不写；单遍扫描，只能递增
输出迭代器：只写，不读；单遍扫描，只能递增
前向迭代器：可读写；多遍扫描，只能递增
双向迭代器：可读写；多遍扫描，可递增递减
随机访问迭代器：可读写，多遍扫描，支持全部迭代器运算

2. 算法形参模式¶

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

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

2.1 接收单个目标迭代器的算法¶

Tips：向输出迭代器写入数据的算法都假定目标空间足够容纳写入的数据，即不管写入多少个元素都是安全的。

如果dest是一个直接指向容器的迭代器，那么算法将输出数据写到容器中已存在的元素内。更常见的是dest被绑定到一个插入迭代器或是一个ostream_iterator。插入迭代器会将新元素添加到元素中，因此保证空间足够，而后者会将数据写入到一个输入流，不管写入多少个元素都是没问题的。

2.2 接收第二个输入序列的算法¶

接收单独的beg2或是接收beg2和end2的算法用这些迭代器来表示第二个输入范围。接受单独beg2的算法假定从beg2开始的范围与beg和end所表示的范围至少一样大。

3. 算法命名规范¶

3.1 使用重载形式传递一个谓词¶

unique(beg, end);        // 使用==运算符比较元素
unique(beg, end, comp);  // 使用comp比较元素

这两个调用都会重整给定序列，将相邻的重复元素删除。两个版本的函数在参数个数上不相等，因此具体调用哪个版本不会产生歧义。

3.2 _if版本¶

接收一个元素值的算法通常有另一个不同名（非重载）版本呢，该版本接收一个谓词来代替元素值：

find(beg, end, val); // 查找输入范围内val第一次出现的位置
find_if(beg, end, pred); // 查找第一个令pred为真的元素

3.3 区分拷贝元素的版本和不拷贝元素的版本¶

reverse(beg, end);             // 反转输入与范围中元素的顺序
reverse_copy(beg, end, dest);  // 将元素逆序拷贝到dest

有一些函数算法同时支持_copy和_if版本：

// 从v1中删除奇数元素
remove_if(v1.begin(), v1.end(),
    [](int i) { return i % 2 });
    
// 将偶数元素从v1拷贝到v2
remove_copy_if(v1.begin(), v1.end(), back_inserter(v2),
    [](int i) { return i % 2 });

特定容器算法¶

1. 链表提供的成员函数算法¶

通用算法sort要求随机访问迭代器，但是list和forward_list分别提供双向迭代器和前向迭代器，因此无法使用。除了sort外的其他算法通用版本虽然可以应用于链表，但是性能不佳。因为这些算法需要交换输入序列中的元素，一个链表可以通过改变元素间的链接而不是真的交换它们的值来快速“交换元素”，因此：

Tips：对于list和forward_list，应该优先使用成员内函数版本的算法而不是通用算法。

下面列举了list和forward_list成员函数版本的算法，这些操作都返回void：

// 将来自lst2的元素合入lst，要求这两个链表必须有序，元素将从lst2中删除，合并之后lst2为空。第一个版本使用<运算符，第二个版本呢使用给定的比较操作。
lst.merge(lst2);
lst.merge(lst2, comp);

// 调用erase删除掉与给定值相等或者令一元谓词为真的每个元素
lst.remove(val);
lst.remove_if(pred);

// 反转元素
lst.reverse();

// 使用<或者给定比较操作排序元素
lst.sort();
lst.sort(comp);

//调用erase删除同一个值的连续拷贝，第一个版本使用==，第二个版本使用给定的二元谓词
lst.unique();
lst.unique(pred);

2. splice成员¶

链表定义了splice算法，是链表所特有的：

lst.splice(args)或flst.splice_after(args)

参数args包括：

(p, lst2)：p是一个指向lst中元素的迭代器或指向flst首前位置的迭代器。函数将lst2的所有元素移动到lst中p之前的位置或是flst中p之后的位置，将元素从lst2中删除
(p, lst2, p2)：p2是一个指向lst2中位置的有效迭代器，将p2指向的元素移动到lst中，或者将p2之后的元素移动到flst中
(p, lst2, b, e)：b和e表示lst2中的合法范围，将给定范围中的元素从lst2移动到lst或者flst

3. 链表特有的操作会改变容器¶

多数链表特有的算法都与其通用版本很相似，但不完全相同。链表特有版本与通用版本间的一个至关重要的区别是链表版本会改变底层的容器：

remove的链表版本会删除指定的元素
unique的链表版本会删除第二个和后续的重复元素
merge和splice会销毁给定的链表