《C++Primer》第十章 泛型算法

概述

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

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

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

泛型算法类型

1. 只读算法

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

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

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

2. 写容器元素的算法

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

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

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

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

replace(ilist.cbegin(), ilist.cend(), back_innserter(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(words.begin(), words.end(), 
    [] (const string &a, const string &b)
    { return a.size() < b.size(); });

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

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

3. for_each算法

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

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

lambda捕获和返回

1. 值捕获

注意lambda的值捕获具有如下两个特点：

• 采用值捕获的前提是变量可以拷贝
• 被捕获的变量是在创建时拷贝，而不是调用时拷贝

void fcn1()
{
    size_t v1 = 42; // 局部变量
    // 将v1拷贝到名为f的可调用对象
    auto f = [v1] {return v1; };
    v1 = 0;
    auto j = f(); // j=42; f保存了我们创建它时v1的拷贝
}

2. 引用捕获

我们也可以将上述的程序修改成：

void fcn2()
{
    size_t v1 = 42; // 局部变量
    // 对象f2包含v1的引用
    auto f2 = [&v1] { return v1; };
    v1 = 0;
    auto j = f2(); // j为0
}

当以引用方式捕获一个变量时，必须保证在lambda执行时变量是存在的。而且如果可能的话应尽量避免捕获指针或者引用。

3. 隐式捕获

除了显式列出我们希望使用所在函数的变量外，还可以让编译器根据lambda体中的代码来推断我们要使用哪种变量。为了指示编译器推断捕获列表，应在捕获列表中写一个&或者=，前者表示引用捕获，后者表示值捕获。

4. 可变lambda

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

void fcn3() {
    size_t v1 = 42; // 局部变量
    // f可以改变它所捕获的变量的值
    auto f = [v1] () mutable { return ++v1; };
    v1 = 0;
    auto j = f(); // j 为43
}

5. 指定lambda返回类型

默认情况下，如果一个lambda包含return以外的任何语句，则编译器假定此lambda。

// 错误：不能推断lambda的返回类型
// 编译器推断lambda返回void, 但是它返回了一个int值
transform(vi.begin(), vi.end(), vi.begin(),
    [](int i) { if (i < 0) return -i; else return i; });

当我们需要为一个lambda定义返回类型时，需要使用尾置返回类型：

transform(vi.begin(), vi.end(), vi.begin(),
    [](int i) -> int
    { if (i < 0) return -i; else return i; });

参数绑定

1. bind函数的使用

lambda表达式一般用于只在一两个地方使用的简单操作，如果我们需要在很多地方都使用相同的操作，那么通常函数是最佳的选择。

对于捕获局部变量的lambda，用函数替换它就不是很简单了。比如我们用在find_if调用中的lambda比较一个string和一个给定大小，我们也可以编写一个完成相同工作的函数：

bool check_size(const string &s, string::size_type sz)
{
    return s.size() >= sz;
}

但是这个函数是没法作为find_if的参数的（因为它只能接收一个一元谓词，所以传递给它的可调用对象必须接收单一参数），一种解决思路是我们传递给find_if的lambda使用捕获列表来保存sz：

// words类型为vector<string>, 返回第一个长度大于等于sz的string元素, 找不到则返回words.end()的一个拷贝
auto wc = find_if(words.begin(), words.end(), 
    [sz](const string &a)
        { return a.size() >= sz; });

如果我们想用check_size来代替lambda的话，必须解决如何向sz传递一个参数的问题。C++提供标准库bind函数来解决这个问题。

bind函数可以看成一个通用的函数适配器，它接收一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表，一般形式为：

auto NewCallable = bind(callable, arg_list);

• arg_list是一个逗号分割开的参数列表，对应给定的callable参数
• arg_list中的参数可能包含形如_n的名字，这些参数是占位符，表示newCallable的参数

这样我们通过bind函数生成一个调用check_size的对象，它用一个定值作为它的大小参数来调用check_size：

// check6是一个可调用对象, 接收一个string参数, 用此string参数和6来调用check_size
using namespace std::placeholders;
auto check6 = bind(check_size, _1, 6);

现在原本基于lambda的find_if调用可以替换成使用bind函数的版本：

auto wc = find_if(words.begin(), words.end(), 
    bind(check_size, _1, sz));

2. bind的参数

假设f是一个有5个参数的可调用对象，g是一个有2的参数的可调用对象，我们构造下述bind的调用：

auto g = bind(f, a, b, _2, c, 1);

• 新生成的g可调用对象有两个参数，分别用占位符_2和_1表示
• 新的可调用对象g将它自己的参数作为第三个和第五个参数传递给f
• f的第一个、第二个和第四个参数分别被绑定到给定的值a、b和c上

总结一下：bind调用会将g(_1, _2)映射成f(a, b, _2, c, _1)，通过占位符我们也可以重排参数顺序。

3. 绑定引用参数

有时候我们希望以引用的方式传递绑定的参数，或是绑定的参数无法拷贝，比如构造一个以引用方式捕获ostream的lambda：

// os是一个局部变量, 引用一个输出流
// c是一个局部变量, 类型为char
for_each(words.begin(), words.end(), 
    [&os, c](const string &s) { os << s << c; });

我们可以编写一个函数完成这个功能：

ostream &print(ostream &os, const string &s, char c)
{
    return os << s << c;
}

不过需要注意bind不能拷贝一个ostream，当我们希望传递给bind一个对象而又不拷贝它，就必须用标准库函数ref：

// 错误用法：os无法被拷贝
for_each(words.begin(), words.end(), bind(print, os, _1, ' '));

// 正确用法：使用ref
for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));

注意：标准库中还有一个cref函数可以生成一个保存const引用的类。

再探迭代器

除了为每个容器定义的迭代器外，标准库在头文件iterator中还定义了额外几种迭代器：

• 插入迭代器：用于向容器中插入元素
• 流迭代器：绑定到输入或者输出流上，用于遍历所有关联的IO流
• 反向迭代器：向后而不是向前移动，除了forward_list外的标准库容器都有反向迭代器

1. 插入迭代器

插入迭代器对应的操作包括：

// 1) 在it指定的当前位置插入值t，假定c是it绑定的容器，依赖于插入迭代器的不同种类，此赋值会分别调用c.push_back(t)、c.push_front(t)或c.insert(t,p)，其中p为传递给inserter的迭代器位置
it = t 

// 2) 这些操作虽然存在，但不会对it做任何事情，每个操作都返回it
*it,++it,it++

迭代器的种类包括：

• back_inserter：使用push_back的迭代器
• front_inserter：使用push_front的迭代器
• inserter：创建一个使用insert的迭代器，此函数接收第二个参数，这个参数必须是一个指向给定容器的迭代器，元素将被插入到给定迭代器所表示的元素之前

使用back_insert需要容器支持push_back，使用front_inserter需要容器支持push_front

当我们调用inserter(c, iter)时，我们得到一个迭代器，并将元素插入到iter原来所指向的元素之前的位置。比如it是inserter生成的迭代器，那么当我们执行*it = val给它赋值时，相当于：

it = c.insert(it, val); // it指向新加入的元素
++it; // 递增it使它指向原来的元素

当我们使用front_inserter时，元素总是插入到容器第一个元素之前；而即使我们传递给inserter的位置原来指向第一个元素，只要我们在此元素之前插入一个新元素，那么这个元素就不再是新元素了。

看下面这个例子理解front_inserter和inserter的不同：

list<int> lst = {1,2,3,4};
list<int> lst2, lst3; // 空list
// 拷贝完成之后, lst2包含4, 3, 2, 1
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
// 拷贝完成之后, lst3包含1, 2, 3, 4
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

2. iostream迭代器

当创建一个流迭代器时，必须制定迭代器将要读写的对象类型，一个istream_iterator使用>>来读取流，因此istream_iterator要读取的类型必须定义了输入运算符：

istream_iterator<int> int_it(cin); // 从cin读取int
istream_iterator<int> int_eof; // 尾后迭代器

ifstream in("afile");
istream_iterator<string> str_it(in); // 从"afile"中读取字符串

我们使用一个istream_iterator例子从标准输入中读取数据并存入一个vector：

istream_iterator<int> in_iter(cin); // 从cin中读取int
istream_iterator<int> eof; // istream尾后迭代器, 当关联的流遇到文件尾或者IO错误则in_iter等于尾后迭代器
while (in_iter != eof)
    // 后置递增运算读取流: 返回迭代器的旧值
    // 解引用迭代器，获得从流读取的前一个值
    vec.push_back(*in_iter++);

另外一种写法更能体现istream_iterator的作用：

// 这个构造函数从cin中读取数据，直至遇到文件尾或者遇到一个不是int的数据为止
istream_iterator<int> in_iter(cin), eof; // 从cin中读取int
vector<int> vec(in_iter, eof); // 从迭代器范围构造vec

istream_iterator的操作包括：

// 1) in从输入流is读取类型为T的值
istream_iterator<T> in(is); 

// 2) 读取类型为T的istream_iterator迭代器, 表示尾后为止
istream_iterator<T> end;

// 3) in1和in2必须读取相同类型, 如果它们都是尾后迭代器或者绑定到相同的输入则两者相等
in1 == int2
in1 != int2

// 4) 等价于(*in).mem
in->mem

// 5) 使用元素类型所定义的>>运算符从输入流中读取下一个值，前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值
++in, in++

我们可以对任何具有输出运算符<<的类型定义ostream_iteerator，当创建一个ostream_iteerator时我们可以提供（可选的）第二个字符串参数，它表示在输出每个月元素后都会打印该字符串。此字符串必须是一个C风格字符串（一个字符串字面常量或者一个指向以空字符串结尾的字符数组的指针）。

ostream_iteerator支持的操作为：

// 1) out将类型为T的值写入输出流os中
ostream_iterator<T> out(os);

// 2) out将类型为T的值写入输出流os中，每个值后面都输出一个d
ostream_iterator<T> out(os, d);

// 3) 用<<将val写入到与out绑定的ostream_iterator
out = val;

// 4) 这些运算符存在，但不对out做任何事情，都是返回out
*out, ++out, out++

使用ostream_iterator输出序列e的值有几种方式：

// 方法一：和其他迭代器的使用方式保持一致，推荐使用
ostream_iterator<int> out_iter(cout, " ");
for (auto e : vec)
    *out_iter++ = e; // 将值写到cout
cout << endl;

// 方法二：运算符*和++实际上不会对ostream_iterator对象有任何作用
for (auto e : vec)
    out_iter = e;
cout << endl;

// 方法三：使用copy来打印vec中的元素，推荐使用
copy(vec.begin(), vec.end(), out_iter);
cout << endl;

反向迭代器

反向迭代器是在容器中从尾部向首部反向移动的迭代器，对于反向迭代器而言，++it会移动到前一个元素，--it会移动到下一个元素。反向迭代器可以使得我们用算法透明地向前或者向后处理容器，比如向sort传递一堆反向迭代器将vector降序：

// 升序
sort(vec.begin(), vec.end()); 

// 降序
sort(vec.rbegin(), vec.rend());

我们可以通过reverse_iterator的base成员函数将其转换为一个普通迭代器，但是他们指向的不是同一元素了。举个例子，我们需要在一个逗号分隔的string中打印最后一个元素：

string line = "FIRST, MIDDLE, LAST";

// rcomma会指向line中最后一个逗号，如何找不到则指向line.crend()
auto rcomma = find(line.crbegin(), line.crend(), ',');

// 如果我们要打印这个单词, 那么会反向输出TSAL，因为反向迭代器会反向遍历line
cout << string(line.crbegin(), rcomma) << endl;

// 我们将rcomma转化为普通迭代器以便在line中正向移动
cout << string(rcomma.base(), line.cend()) << endl;

需要注意的是[line.crbegin(), rcomma)和rcomma.base(), line.cend()指向的是同一个元素范围。因此rcomma和rcomma.base()必须指向相邻的位置而非同一个位置，crbegin()和cend()也是相邻位置。

image.png

泛型算法结构

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 接收单个目标迭代器的算法

如果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 });

特定容器算法

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

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

// 将来自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);

链表定义了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

需要特别注意的是：多数链表特有的算法版本会改变底层的容器，比如remove的链表版本会删除指定的元素，unique的链表版本会删除第二个和后续的重复元素。merge和splice会销毁给定的链表。