第10章泛型算法（上）

顺序容器只定义了很少的操作，我们可以想象用户可能还希望做其他很多有用的操作：查找特定元素、替换或删除一个特定值、重排元素顺序等。标准库定义了一组泛型算法（generic algorithm）。

10.1 概述

大多数算法都定义在头文件algorithm中。标准库还在头文件numeric中定义了一组数值泛型算法，一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的一个元素范围来进行操作。

//我们假定有一个int的vector，希望知道vector中是否包含一个特定值
int val = 42;	//我们将查找的值
//如果在vec中找到想要的元素，则返回结果指向它，否则返回结果为vec.cend()
auto result = find (vec.cbegin(), vec.cend(), val);
//报告结果
cout << "The value " << val 
	 << (result == vec.cend() ? "is not present" : "is present") << endl;

//我们假定有一个int的vector，希望知道vector中是否包含一个特定值

int val = 42; //我们将查找的值

//如果在vec中找到想要的元素，则返回结果指向它，否则返回结果为vec.cend()

auto result = find (vec.cbegin(), vec.cend(), val);

//报告结果

cout << "The value " << val

<< (result == vec.cend() ? "is not present" : "is present") << endl;

如果范围中无匹配元素，则find返回第二个参数来表示搜索失败。由于find操作的是迭代器，因此我们可以用同样的find函数(与string类的find成员函数不同)在任何容器中查找值。

类似的，由于指针就像内置数组上的迭代器一样，我们可以用find在数组中查找值：

int ia[] = {27, 210, 12,47, 109, 83};
int val = 83;
int *result = find(begin(ia), end(ia), val);

int ia[] = {27, 210, 12,47, 109, 83};

int val = 83;

int *result = find(begin(ia), end(ia), val);

此例中我们使用了标准库begin和end函数来获得指向ia中首元素和尾元素之后位置的指针，并传递给find。

迭代器令算法不依赖于容器，但算法依赖于元素类型的操作。
算法永远不会执行容器的操作：泛型算法本身不会执行容器的操作，它们只会运行于迭代器之上，执行迭代器的操作。泛型算法运行于迭代器之上而不会执行容器操作的特性带来了一个令人惊讶但非常必要的编程假定：算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但永远不会直接添加或删除元素。

10.2初识泛型算法

除了少数例外，标准库算法都对一个范围内的元素进行操作。我们将此范围称为“输入范围”。虽然大多数算法遍历输入范围的方式相似，但它们使用范围中元素的方式不同。理解算法的最基本的方法就是了解它们是否读取元素、改变元素或是重排元素顺序。

只读算法：一些算法只会读取其输入范围内的元素，而从不改变元素。find就是这样一种算法，10.1节练习中使用的count函数也是如此。另一个只读算法是accumulate，它定义在头文件numeric中。accumulate函数接受三个参数，前两个指出了需要求和的元素的范围，第三个参数是和的初值。

//对vec中的元素求和，和的初值是0
int sum = accumulate(vec.begin(), vec.end(), 0);
//NOTE：accumulate的第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型

//对vec中的元素求和，和的初值是0

int sum = accumulate(vec.begin(), vec.end(), 0);

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

另一个只读算法：equal，用于确定两个序列是否保存相同的值。它将第一个序列中的每个元素与第二个序列中的对应元素进行比较如果对应元素相等，返回true，否则返回false。此算法接受三个迭代器：前两个表示第一个序列中的元素范围，第三个表示第二个序列的首元素：

C++

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

1
2

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

由于equal利用迭代器完成操作，因此我们可以通过调用equal来比较两个不同类型容器中的元素。而且，元素类型也不必一样，只要我们能用==来比较来个元素即可。

WARNING：那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长。

写容器元素的算法：算法不会执行容器操作，因此它们自身不可能改变容器的大小。一些算法会自己向输入范围写入元素。这些算法本质上并不危险它们最多写入与给定序列一样多的元素。

//例如算法fill接受一对迭代器表示一个范围，还接受一个值作为第三个参数
//fill将给定的这个值赋予输入序列中的每个元素
fill (vec.begin(), vec.end(), 0);    //将每个元素重置为0
//将容器的一个序列设置为10
fill (vec.begin(), vec.begin() + vec.size()/2, 10);

//例如算法fill接受一对迭代器表示一个范围，还接受一个值作为第三个参数

//fill将给定的这个值赋予输入序列中的每个元素

fill (vec.begin(), vec.end(), 0); //将每个元素重置为0

//将容器的一个序列设置为10

fill (vec.begin(), vec.begin() + vec.size()/2, 10);

算法不检查写操作：fill_n接受一个单迭代器、一个计数值和一个值。它将给定值赋予迭代器指向的元素开始的指定个元素。

vector<int> vec;	//空vector
//使用vec,赋予它不同值
fill_n(vec.begin(), vec.size(), 0);	//将所有元素重置为0
//函数fill_n假定写入指定个元素是安全的。即如下形式的调用
fill_n (dest, n, val);	//将定dest指向一个元素，而从dest开始的序列至少包含n个元素

vector<int> vec; //空vector

//使用vec,赋予它不同值

fill_n(vec.begin(), vec.size(), 0); //将所有元素重置为0

//函数fill_n假定写入指定个元素是安全的。即如下形式的调用

fill_n (dest, n, val); //将定dest指向一个元素，而从dest开始的序列至少包含n个元素

一个初学者容易犯的错误是在一个空容器上调用fill_n（或类似的写元素的算法）：

vector<int> vec;	//空向量
//灾难：修改vec中的10个（不存在）元素
fill_n(vec.begin(), 10, 0);	//这个调用是一场灾难，我们指定要写入10个元素，但vec中没有元素——它是空的

vector<int> vec; //空向量

//灾难：修改vec中的10个（不存在）元素

fill_n(vec.begin(), 10, 0); //这个调用是一场灾难，我们指定要写入10个元素，但vec中没有元素——它是空的

WARNING：向目的位置迭代器写入数据的算法假定目的的位置足够大，能容纳要写入的元素。

介绍back_insert:

一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器（insert iterator），back_inserter接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中：

vector<int> vec;	//空向量
auto it = back_inserter(vec);	//通过它赋值会将元素添加到vec中
*it = 42;	//vec中现在又一个元素，值为42；

//我们常常使用back_inserter来创建一个迭代器，作为算法的目的位置来使用。例如：
vector<int> vec;	//空向量
//正确：back_inserter创建一个插入迭代器，可用来向vec添加元素
fill_n(back_inserter(vec),10,0);	//添加10个元素到vec

vector<int> vec; //空向量

auto it = back_inserter(vec); //通过它赋值会将元素添加到vec中

*it = 42; //vec中现在又一个元素，值为42；

//我们常常使用back_inserter来创建一个迭代器，作为算法的目的位置来使用。例如：

vector<int> vec; //空向量

//正确：back_inserter创建一个插入迭代器，可用来向vec添加元素

fill_n(back_inserter(vec),10,0); //添加10个元素到vec

在每步迭代中，fill_n向给定序列的一个元素赋值。由于我们传递的参数是back_inserter返回的迭代器，因此每次赋值都会在vec上调用push_back。最终，这条fill_n调用语句向vec的末尾添加了10个元素，每个元素的值都是0。

拷贝算法：

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

//我们可以用copy实现内置数组的拷贝
int a1[] = {0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1)/siof(*a1)];	//a2与a1大小一样
//ret指向拷贝到a2的尾元素之后的位置
auto ret = copy(begin(a1),end(a1),a2);	//	把a1的内容拷贝给a2

//我们可以用copy实现内置数组的拷贝

int a1[] = {0,1,2,3,4,5,6,7,8,9};

int a2[sizeof(a1)/siof(*a1)]; //a2与a1大小一样

//ret指向拷贝到a2的尾元素之后的位置

auto ret = copy(begin(a1),end(a1),a2); // 把a1的内容拷贝给a2

copy返回的是其目的位置迭代器（递增后）的值。即，ret恰好指向拷贝到a2的尾元素之后的位置。

replace算法读入一个序列，并将其中所有等于给定值的元素都改为另一个值。此算法接受4个参数：前两个是迭代器，表示输入序列，后两个一个是要搜索的值，另一个是新值。

//将所有的值为0的元素改为42
replace(ilist.begin(),ilist.end(),0,42);
//此调用将序列中所有0替换为42.如果我们希望保留原序列不变，可以调用replace_copy，
//此算法接受额外的第三个迭代器参数，指出调整后序列的保存位置：
replace_copy(ilist.begin(),ilist.end(),back_inserter(ivec),0,42);
//此调用后，ilist并未改变，ivec包含ilist的一份拷贝，
//不过原来在ilist中的值为0的元素在ivec中都变为42

//将所有的值为0的元素改为42

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

//此调用将序列中所有0替换为42.如果我们希望保留原序列不变，可以调用replace_copy，

//此算法接受额外的第三个迭代器参数，指出调整后序列的保存位置：

replace_copy(ilist.begin(),ilist.end(),back_inserter(ivec),0,42);

//此调用后，ilist并未改变，ivec包含ilist的一份拷贝，

//不过原来在ilist中的值为0的元素在ivec中都变为42

重排容器元素的算法

某些算法会重排容器中元素的顺序，一个明显的例子是sort。调用sort会重排输入序列中的元素，使之有序，它是利用元素类型的<运算符来实现排序的。

消除重复单词（P343）：为了消除重复单词，首先将vector排序，使得重复的单词都相邻出现。一旦vector排序完毕，我们就可以使用另一个称为unique的标准库算法来重排vector，使得不重复出现的元素出现在vector的开始部分(重复的元素移到了尾端)。由于算法不能执行容器的操作，我们将使用vector的erase成员来完成真正的删除操作：

void elimDups(vector<string> &words)
{
	//按字典序排序words，以便查找重复单词
	sort(words.begin(),words.end());
	//unique重排输入范围，使得每个单词只出现一次
	//排列在范围的前部，返回指向不重复区域之后一个位置的迭代器
	auto end_unique = uniqe(words.begin(),words.end());
	//使用向量操作erase删除重复单词
	words.erase(end_unique, words.end());
}

void elimDups(vector<string> &words)

{

//按字典序排序words，以便查找重复单词

sort(words.begin(),words.end());

//unique重排输入范围，使得每个单词只出现一次

//排列在范围的前部，返回指向不重复区域之后一个位置的迭代器

auto end_unique = uniqe(words.begin(),words.end());

//使用向量操作erase删除重复单词

words.erase(end_unique, words.end());

}

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

10.1 概述

10.2初识泛型算法

发表评论 取消回复

发表评论取消回复