泛型算法 | 彩潭有鲤的札记

type

status

date

slug

summary

算法如何工作

find可以在未排序的一系列元素中查找特定的元素，采取的步骤：

访问序列的首元素

将其与给定值进行比较

如果这个元素匹配给定的值，find将返回迭代器或者指针来标识这个元素

否则find继续查找下一个元素，重复步骤 2 和 3

find必须在到达序列的末尾时结束

如果find到了序列的末尾，需要返回一个值来表示元素没有找到。返回的值需要与第 3 步中的类型相兼容

以上所有操作都没有依赖于容器的类型，只要能够使用迭代器来访问元素，find根本不需要依赖于容器的类型。

迭代器使得算法与容器互相独立

除了第二步之外的所有步骤都可以通过迭代器进行操作：

迭代器解引用可以访问元素

如果找到了匹配的元素，find返回那个元素的迭代器

迭代器的自增操作将移动到下一个元素

“尾后”迭代器表示find已经到达了给定序列的尾部，返回尾后迭代器表示没有找到指定的值

但是算法依赖于元素类型的操作

尽管迭代器使得算法和容器类型相互独立，大部分的算法使用一个或多个元素类型的操作，如：用元素类型的==操作符比较每个元素和给定值。其它的算法需要元素类型由<操作符。然而，绝大部分的算法还提供了一种方式允许我们提供自己的操作用于替换默认的行为。

算法永不执行容器的操作

通用算法自己不会执行容器的操作，它们只会操作迭代器。算法不直接调用容器的成员函数有一个重要的隐喻：算法永远不会改变底层容器的长度。算法可能会改变元素的值，可能会在容器中移动元素，但是它们不会直接添加或移除元素。

标准库定义了一种特殊类别的迭代器——插入器，除了遍历序列之外。当给这个迭代器赋值时，它将在底层容器中执行插入操作。当算法操作在这种迭代器上时，迭代器具有加元素到容器中的效果。但是算法本身不会插入元素，甚至它都不知道插入元素这回事。

只读算法

有很多算法对输入范围只读不写，只会读取输入范围内的元素而不改变元素。find和count算法就是一个例子。

另外一个只读算法是accumulate，它定义在numeric 头文件中。accumulate 函数有三个参数，前两个指定输入范围，第三个参数是综合的初始值。

算法和元素类型

accumulate 使用第三个参数作为求和的起点，也就是说元素的类型必须与第三个参数的类型相匹配或者可以相互转换。在上面例子的 vec中，元素类型可以是 int，double，long long 或其它可以与int 相加的类型。

string 定义了+操作符，所以可以通过调用 accumulate 将 vector 中的元素拼接起来：

这里需要显示创建string作为第三个参数，如果传递的是空字符串字面量将会是编译时错误：

通常在只读算法上最好使用cbegin() 和cend()，如果打算使用返回的迭代器来改变元素的值就需要begin() 和end()

操作两个序列的算法

另外一个只读算法是 equal，用于判断是否两个序列中的值完全一样。它将第一个序列中的每个元素与第二个序列中对应位置的元素进行比较，如果所有的对应位置的元素都相等，返回 true，否则返回 false。这个算法接受三个迭代器：前两个表示第一个序列的范围，第三个是第二个序列的首元素：

由于 equal 在是迭代器上定义的，可以用于比较不同类型的容器中的元素。甚至，元素类型也不需要完全一致，只要可以使用 == 进行元素值比较就行。如：roster1 可以是 vector<string> ，roster2 可以是 list<const char*> 。

然而，equal做出了一个严格的假设：它假设第二个序列至少跟第一个序列一样长。这个算法潜在地会遍历第一个序列中的所有元素。它假设第二个序列中一定会有对应的元素。

注：那些只接受一个单一迭代器来表示第二个序列的算法，会假设第二个序列至少跟第一个序列一样长。

写容器元素的算法

一些算法会给序列中的元素赋予新值。使用这些算法时需要注意，必须保证算法写入的序列其大小，大于等于需要写入的数目。算法不会直接调用任何容器的操作，所以它们本身没有任何办法改变容器的大小。

其中一部分算法只会对输入范围内的元素进行写入，没有上面谈到的危险，原因是它们只会对输入范围内的元素进行写入。

比如，fill接受一对迭代器表示范围，以及第三个参数表示要写入的值。fill将给定值赋值给范围内的所有元素：

由于 fill 只会往给定的输入序列中写入数据，只要传入的是合法的输入序列，那么写入将是安全的。

算法不会检查输出操作

有些算法只有一个单独的迭代器表示写入目标。这些算法将新值赋值到以目标迭代器表示的元素开始的序列的元素中。 fill_n 以一个迭代器，计数器和值作为参数。它将这个给定值赋值到从迭代器所表示的元素开始的指定数目的元素中去：

fill_n 假设写入指定数目的元素是安全的：

在空容器上调用 fill_n （以及其它写入的算法）是一个常见的错误：

注：写入到目标迭代器的算法假设目标序列足以容纳将要写入的元素

`back_inserter`

有一种保证算法有足够的元素空间来容纳输出数据，那就是使用插入迭代器（insert iterator）。插入迭代器是往容器中添加元素的迭代器。平常，给迭代器赋值时，是给迭代器所表示的元素赋值。当给插入迭代器赋值时，一个等于右边值的新元素被添加到容器中。

back_inserter是定义在iterator头文件中的函数。back_inserter以指向容器的引用为参数，返回一个绑定到容器上的插入迭代器。当通过这个迭代器给元素赋值时，将调用容器的 push_back 函数给容器添加元素：

常常用 back_inserter 来创建一个迭代器，作为算法的目的位置来使用：

每步迭代中，fill_n向给序列中的一个元素赋值，由于传入的参数是back_inserter返回的迭代器，每次赋值都将调用vec 的 push_back ，因而每次赋值 fill_n 都会添加一个元素到容器的尾部。

拷贝算法

copy 算法是另一个将值写入到由目的迭代器表示的输出序列中的例子。这个算法只有三个参数。前两个表示输入序列；第三个表示输出序列的首元素。这个算法将输入范围内的元素拷贝输出序列中。有一点很重要的是传递给 copy 的输出序列至少要和输入序列一样长。如将值拷贝内置数组中去：

copy 的返回值是自增后的目的迭代器，意味着 ret 将指向 a2 的尾后位置。

有多个算法提供了“拷贝”版本，相比于将计算后的值重新存入输入序列中，这个算法创建一个新的序列以容纳结果。比如replace算法接收四个参数：两个迭代器表示输入序列，以及两个值。它将序列中的每个等于第一个值的元素替换为第二个值：

如果想要保持原始的容器不变的话，需要调用 replace_copy ，这个算法有第三个迭代器参数表示输出目的地：

在此调用之后ilist将保持不变，而ivec的元素将是ilist拷贝，并将其中所有的0替换为42

重排容器元素的算法

有些算法对容器中的元素进行重排序，一个显著的例子就是sort算法。调用sort将使用元素的 < 操作符将输入范围内的元素排序。

一个例子是消除容器中的相同的字符串。首先对这些字符串进行排序，然后调用 unique将所有唯一的字符串放到容器的首部，并返回最后一个唯一字符串的下一个位置的迭代器。unique 本身是不改变容器的大小的，所以需要用容器的 erase 成员移除元素：

调用完 unique 之后，返回值迭代器后面的值到底是什么无法知道，它可能已经被算法给改写了。

由于标准库算法是在迭代器而不是容器上进行操作，算法不能直接添加或移除元素。

使用容器操作来移除元素

为了移除无用的元素，必须使用容器的操作。