跳转至

第十章 泛型算法

标准库并未给每个容器都定义成员函数来实现一些特殊的操作，如查找元素、替换或删除元素、重排元素等。而是定义了一组泛型算法。它们实现了一些经典算法的公共接口，可以用于不同类型的元素和多种容器类型，包括内置的数组类型。

概述

大多数算法定义在头文件algorithm中，头文件numeric中定义了一组数值泛型算法。

通常，算法并不直接操作容器，而是遍历由两个迭代器指定的一个元素范围来进行操作。

算法不依赖于容器，但依赖于元素类型的操作。比如，find用元素类型的==运算符完成序列中的元素与给定值的比较。大多数算法提供了一种方法，允许我们使用自定义的操作来代替默认的运算符（即使用谓词）。

初识泛型算法

附录A按照操作方式列出了所有的算法。

除了少数例外，标准库算法都对一个范围内的元素进行操作。我们将此元素范围称为“输入范围”。

理解算法的最基本的方法就是了解它们是否读取元素、改变元素或是重排元素顺序。

只读算法

一些算法只会读取其输入范围内的元素，而从不改变元素。比如find。

操作两个序列的算法

举一个列子：equal算法，它比较两个序列中的元素。此算法接受三个迭代器：前两个表示第一个序列中的元素的范围，第三个表示第二个序列的首元素：

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

这样的算法基于一个非常重要的假设：它假定第二个序列至少与第一个序列一样长。

写容器元素的算法

一些算法将新值赋予序列中的元素。当我们使用这类算法时，必须注意确保序列原大小至少不小于我们要求算法写入元素数目（note：如容器大小足够）。

这样的算法比如fill。

介绍back_inserter

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

重排元素的算法

某些算法会重排容器中元素的顺序，比如sort，它利用元素类型的<运算符来实现排序。

定义操作

很多算法都会比较输入序列中的元素。默认情况下，这类算法使用元素类型的<或==运算符完成比较。标准库为这些算法定义了额外的版本，允许我们提供自己定义的操作来替代默认运算符。

向算法传递函数

sort接受第三个参数，此参数是一个谓词（predicate）。

谓词

谓词是一个可调用的表达式，其调用结果是一个能用作条件的值。标准库算法使用的谓词分为两类：

  • 一元谓词，意味着它们只接受单一参数

  • 二元谓词，意味着它们有两个参数

接受谓词的算法对输入序列中的元素调用谓词。

lambda表达式

我们传递给算法的谓词必须严格接受一个或两个参数，但是有时我们希望进行的操作需要更多的参数，超出了算法对谓词的限制。

介绍lambda

我们可以向一个算法传递任何类别的可调用对象，对于一个对象或一个表达式，如果可以对其使用可调用运算符，则称它为可调用的。

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

一个lambda表达式具有如下形式：

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

其中，capture list是一个lambda所在函数中定义的局部变量的列表。

可以忽略返回类型，这时会自动推断返回类型。

auto func = [](){ return 42; };

lambda捕获和返回

当定义一个lambda时，编译器生成一个与lambda对应的新的（未命名的）类类型。当向一个函数传递一个lambda时，同时定义了一个新类型和该类型的一个对象。类似地，当使用auto定义一个用lambda初始化的变量时，定义了一个从lambda生成的类型的对象。

默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员。类似任何普通类的数据成员，lambda的数据成员也在lambda对象创建时被初始化。

变量捕获的方式可以是值或引用。值捕获是变量的拷贝，引用捕获是变量的引用。

Warning

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

建议：尽量保持lambda的变量捕获简单化。如果可能的话，应该避免捕获指针或引用。见p351。

隐式捕获

可以让编译器根据lambda体中的代码来推断要使用哪些变量。为了指示编译器推断捕获列表，应在捕获列表中写一个&或=。&告诉编译器采用捕获引用方式，=则表示采用值捕获方式。

如：

// sz为隐式捕获，值捕获方式
wc = find_if(words.begin(), words.end(),
             [=](const string &s) { return s.size() >= sz; } );

详见lambda捕获列表，p352。

可变lambda

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

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

参数绑定

对于那种只在一两个地方使用的简单操作，lambda表达式是最有用的。如果需要在很多地方使用相同的操作，或者一个操作需要很多语句完成，通常应该定义一个函数。

如果lambda的捕获列表为空，通常可以用函数来代替它。但如果捕获列表不为空就不能直接代替了。

标准库bind函数

为了解决这个问题，可以使用一个新的名为bind的标准库函数，它定义在头文件functional中。它接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表。

auto newCallable = bind(callable, arg_list);

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

arg_list中的参数可能包含形如_n的名字，这些参数是“占位符”，表示newCallable的参数。比如：_1为newCallable的第一个参数，_2为第二个参数。

使用placeholders名字

名字_n都定义在一个名为placeholders的命名空间中，这个命名空间本身定义在std命名空间中。

一种简单的using语句是：

using namespace namespace_name;

这种形式说明希望所有来自namespace_name的名字都可以在我们的程序中直接使用。如：

using namespace std::placeholders;

这使得placeholders定义的所有名字都可用。

再探迭代器

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

  • 插入迭代器：这些迭代器被绑定到一个容器上，可以用来向容器插入元素。

  • 流迭代器：这些迭代器被绑定到输入或输出流上，可以来遍历所关联的IO流。

  • 反向迭代器：这些迭代器向后而不是向前移动。

  • 移动迭代器：不拷贝其中的元素，而是移动它们。将在13.6.2节（p480页）介绍。

插入迭代器

插入器是一种迭代器适配器，它接受一个容器，生成一个迭代器，能实现向给定容器添加元素。当我们通过一个插入迭代器进行赋值时，该迭代器调用容器操作来向给定容器的指定位置插入一个元素。

it = t; // 在it指定的当前位置插入值t。

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

  • back_inserter，创建一个使用push_back的迭代器。

  • front_inserter，创建一个使用push_front的迭代器。

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

iostream迭代器

istream_iterator读取输入流，ostream_iterator向一个输出流写数据。这些迭代器将它们对应的流当作一个特定类型的元素序列来处理。

通过使用流迭代器，我们可以使用泛型算法从流对象读取数据以及向其写入数据。

详细操作见p359。

反向迭代器

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

可以通过rbegin, rend, crbegin, crend成员函数来获得反向迭代器。这些成员函数返回指向容器尾元素和首元素之前一个位置的迭代器。

泛型算法结构

任何算法的最基本的特性是它要求其迭代器提供哪些操作。算法所要求的迭代器操作可以分为5个迭代器类别。

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

5类迭代器

类似容器，迭代器也定义了一组公共操作。一些操作所有迭代器都支持，另一些只有特定类别的迭代器才支持。

如ostream_iterator只支持递增、解引用和赋值。vector、string、deque的迭代器除了这些操作，还支持递减、关系和算术运算。

除了输出迭代器之外，一个高层类别的迭代器支持低层类别迭代器的所有操作。

算法的形参模式

大多数算法具有如下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);

其中，alg是算法名字，beg和end表述输入范围。几乎所有算法都有一个输入范围。

接受单个目标迭代器的算法

dest参数是一个表示算法可以写入目的位置的迭代器。算法假定（assume）：按其需要写入数据，不管写入多少个元素都是安全的。

一般dest被绑定到一个插入迭代器或是一个ostream_iterator。插入迭代器会将新元素添加到容器中，因为保证空间是足够的。

接受第二个输入序列的算法

接受beg2或beg2和end2的算法用这些迭代器表示第二个输入范围。

接受单独beg2的算法假定从beg2开始的序列与beg和end所表示的范围至少一样大。

算法命名规范

除了参数规范，算法还遵循一套命名和重载规范。

一些算法使用重载形式传递一个谓词

函数的一个版本用元素类型的运算符来比较元素；另一个版本接受一个额外的谓词参数，来代替<或==：

unique(beg, end);
unique(beg, end, comp);

_if版本的算法

接受一个元素值的算法通常有另一个不同名的（不是重载的）版本，该版本接受一个谓词代替元素值。接受谓词参数的算法都有附加的_if前缀：

find(beg, end, val);
find_if(beg, end, pred);

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

默认情况下，重排元素的算法将重排后的元素写回给定的输入序列中。这些算法还提供另一个版本，将元素写到一个指定的输出目的位置。

reverse(beg, end);
reverse_copy(beg, end, dest);

特定容器的算法

链表类型list定义了几个成员函数形式的算法。通用版本的sort要求随机访问迭代器，因此不能用于list。

链表类型定义的其他算法的通用版本可以用于链表，但代价太高。这些算法需要交换输入序列中的元素。一个链表可以通过改变元素间的链接而不是真的交换它们的值来快速“交换”元素。因此，这些链表版本的算法的性能比对应的通用版本好得多。

这些算法见p369。

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

多数链表特有的算法与通用版本的很相似，但不完全相同，其中一个至关重要的区别是链表版本的会修改底层的容器。例如， remove 的链表版本会删除指定的元素， unique 的链表版本会删除第二个和后继的重复元素。

Note

对于通用版本的，如 std::remove ，不会删除容器的元素。它只会迁移元素。之后需要调用 erase 才能执行确切的删除动作。