泛型算法

概述

大多数算法定义在头文件algorithm，标准库还在numeric中定义了一些。且一般情况不直接操作容器而是需要一个迭代器指定的范围。

如find：

string val = "a value"; //我们要查找的值
//此调用在list中查找string元素
auto result = find(lst. cbegin()，lst.cend()， val) ;
//类似的，由于指针就像内置数组上的迭代器一样， 我们可以用find在数组中查找值,这里使用到了begin和end:
int ia[] = {27， 210，12, 47， 109， 83};
int val = 83;
int* result = find (begin(ia), end(ia), val);
//还可以在子序列中查找，如从ia[1]开始，直至(但不包含) ia[4]的范围内查找元素
auto result = find(ia + 1，ia+4，val);

迭代器算法不依赖容器但依赖元素类型

例如find用元素类型==运算符，例如还会使用到<运算符等，所以需要在使用时确保元素类型定义了该操作，或者自定义操作。

算法永远不会改变容器大小（即不会添加或删除元素）

初识泛型算法

只读算法

意思是：只会读取输入范围不会改变元素。如：find、count、accumulate：

1
2
3

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

算法和元素类型

accumulate将给定的元素范围加到第三个参数上。所以必须保证容器元素类型能够转换成和的元素类型，且和的类型定义了+操作：string sum = accumulate (v.cbegin()，v.cend() ，string("")) ;

注意这里必须显示的创建一个string，不可以使用字符串字面值：

1 2	//错误: const char*.上没有定义+运算符 string sum = accumulate (v.cbegin()，v.cend(), "") ;

对于只读算法，最好只采用cbegin和cend

操作两个序列的算法

equal用于确定是否保存相同的值。

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

由于使用的是迭代器，所以不同类型的容器可以比较。而且，元素类型也不必一一样，只要我们能用=来比较两个元素类型即可。例如，在此例中，rosterl 可以是vector，而roster2 是list<const char*>。

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

写容器元素的算法

-些算法将新值赋予序列中的元素。当我们使用这类算法时，必须注意确保序列原大小至少不小于我们要求算法写入的元素数目。记住，算法不会执行容器操作，因此它们自身不可能改变容器的大小。一些算法会自己向输入范围写入元素。这些算法本质上并不危险，它们最多写入与给定序列一样多的元素。

1
2
3

fill(vec.begin(), vec.end ( ),0);//将每个元素重置为0
//将容器的一个子序列设置为10
fill(vec.begin(), vec.begin () + vec.size ()/2，10);

关键概念：迭代器参数
一些算法从两个序列中读取元素。构成这两个序列的元素可以来自于不同类型的容器。例如,第一个序列可能保存于一个vector中,而第二个序列可能保存于一个list.deque、内置数组或其他容器中。而且，两个序列中元素的类型也不要求严格匹配。算法要求的只是能够比较两个序列中的元素。例如，对equal算法，元素类型不要求相同,但是我们必须能使用一来比较来自两个序列中的元素。
操作两个序列的算法之间的区别在于我们如何传递第二个序列。一些算法，例如equal，接受三个迭代器:前两个表示第一个序列的范围，第三个表示第二个序列中的首元素。其他算法接受四个迭代器:前两个表示第一个序列的元素范围，后两个表示第二个序列的范围。
用一个单一迭代器表示第二个序列的算法都假定第二个序列至少与第一个一样长。确保算法不会试图访问第二个序列中不存在的元素是程序员的责任。例如,算法 equal会将其第一个序列中的每个元素与第二个序列中的对应元素进行比较。如果第二个序列是第一个序列的一个子集,则程序会产生一个严重错误———equal会试图访问第二个序列中末尾之后（不存在）的元素。

算法不检查写操作

一些算法接受一个迭代器来指出一个单独的目的位置。这些算法将新值赋予一个序列中的元素，该序列从目的位置迭代器指向的元素开始。例如，函数fill_n：

vector<int> vec; //空vector
//使用vec，赋予它不同值
fill_n(vec.begin (), vec.size ( ),0);//将所有元素重置为0
//函数fill_n假定写入指定个元素是安全的。即，如下形式的调用
fill_n(dest, n, val);
//一定要保证写入后大小不能超过容器大小，因为它不会重新开辟空间
vector<int> vec; //空向量
//灾难:修改vec中的10个（不存在）元素fill_n (vec.begin (),10,0);

back_inserter

头文件为iterator，它接受一个引用，返回一个与容器绑定的插入迭代器，当通过此迭代器赋值会调用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

由于每次赋值都会使用push_back，所以可以添加元素。

重排容器元素

先看一段代码，用于消除重复的元素：

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

这里首先使用sort进行排序，这里使用的是string中的<成员，这样相同的元素就会相邻，然后使用unique算法“删除”重复元素，还记得其实我们并不能真的删除容器中的元素，它只是将将重复元素覆盖，然后返回一个“删除”后容器的end位置，所以最后一句代码用erase真正的删除掉它们。

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

定制操作

很多算法允许我们自定义元素的运算符，如sort中的<。

向算法传递函数

如果希望排序是按照单词长度排序，可添加一个参数，称谓词

谓词

谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类: 一元谓词(unary predicate，意味着它们只接受单一参数)和二元谓词( binary predicate，意味着它们有两个参数)。接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型，这里就是用它来代替<来比较参数。

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

如果还希望当长度相等时，按字典排序：

elimDups (words); // 将words按字典序重排，并消除重复单词
//按长度重新排序，长度相同的单词维持字典序
stable_ sort (words .begin()，words.end() ，isShorter) ;
for (const auto &s : words) // 无须拷贝字符串
	cout << s <<”"; //打印每个元素，以空格分隔
cout << endl;

lambda表达式

求大于等于一个给定长度的单词有多少，框架如下：

void biggies (vector<string> &words, vector<string>::size_ type sz)
{
	elimDups (words); // 将words按字典序排序，删除重复单词.
	//按长度排序， 长度相同的单词维持字 典序
	stable_ sort (words .begin(), words.end(), isShorter) ;
	//获取一个迭代器，指向第一个满足size()>= sz的元素
	//计算满足size >= sz的元素的数目
	//打印长度大于等于给定值的单词，每个单词后面接一个空格
}

可以使用find_if算法来查找特定大小的元素，第三个参数为谓词，它将对每个元素使用谓词，返回第一个使谓词返回非0值的元素。不存在返回尾迭代器。

我们的想法是编写一个接受string和长度两个参数返回bool值，表示string长度是否大于给定长度，但find_if值接受一元谓词，所以使用lambda表达式

介绍

与任何函数类似，一个 lambda具有一个返回类型、一个参数列表和一个函数体。但与函数不同，lambda可能定义在函数内部。一个lambda表达式具有如下形式：
[ capture list ] (parameter list) -> return type { function body }
其中，capture list（捕获列表）是一个lambda所在函数中定义的局部变量的列表（通常为空);return type、parameter list和 function body与任何普通函数一样，分别表示返回类型、参数列表和函数体。但是，与普通函数不同，lambda必须使用尾置返回来指定返回类型：

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

如果 lambda的函数体包含任何单一return语句之外的内容，且未指定返回类型,则返回void。

传参

lambda不能有默认参数，所以实参形参数目必须相等且匹配，编写一个isShorter类型的lambda：

1 2	[](const string &a, const string &b) {return a.size()<b.size ();}

//按长度排序，长度相同的单词维持字典序
stable_sort (words.begin ( ), words.end () , 
             	[](const string &a,const string &b)
					{ return a.size () < b.size();});

当比较元素长度，就会使用lambda。

使用捕获列表

在例子中，我们需要捕获用户传进来的边界长度用来查找：

1	[sz] (const string &a) { return a.size() >= SZ; }

捕获了sz，所以我们才可以使用它，没有捕获的不可以使用。

一个lambda只有在其捕获列表中捕获一个它所在函数中的局部变量,才能在函数体中使用该变量。

调用find_if

//获取一个迭代器，指向第一个满足size () >= sz的元素
auto wc = find_if(words.begin(), words.end () ,
					[sz] (const string &a)
						{ return a.size() >=sz; });
auto count = words.end() - wc;  //它表示size >= sz 元素的数目

for_each算法

我们还可以打印出>给定长度的单词：

1
2
3

//打印长度大于等于给定值的单词，每个单词后面接一个空格
for_each(wc, words.end (), [] (const string &s ) { cout << s <<" "; });
cout << endl;

捕获列表只用于局部非static变量，lambda可以直接使用局部static变量和在它所在函数之外声明的名字，所以可以使用cout。

完成程序

void biggies(vector<string> &words, vector<string>::size_type sz)
{
	elimDups (words);// 将words按字典序排序，删除重复单词
	//按长度排序，长度相同的单词维持字典序
	stable_sort (words.begin (), words.end(), [](const string &a, const string &b)
												{return a.size() < b.size();});
	//获取一个迭代器，指向第一个满足size () >= sz的元素
	auto wc = find_if (words.begin(), words.end (), [sz] (const string &a)
													{ return a.size () >=sz; });
	//计算满足size >= sz的元素的数目
	auto count = words.end() - wc;
	cout << count << " " << make_plural(count, "word", "s")
		 <<" of length " <<sz<<" or longer" << endl;
	//打印长度大于等于给定值的单词，每个单词后面接一个空格
	for_each (wc, words.end(), [] (const string &s) {cout << s << " ";});
	cout <<endl;
}

lambda捕获和返回

当定义一个lambda时，编译器生成一个与lambda对应的新的（未命名的）类类型。目前，可以这样理解，它就是一个未命名的类类型的对象，捕获列表里是他的数据成员，使用auto定义一个lambda初始值变量时，就定义了一个从lambda生成的类型的对象。

值捕获与引用捕获

类似参数传递，变量的捕获方式也可以是值或引用。到目前为止，我们的 lambda采用值捕获的方式。与传值参数类似，采用值捕获的前提是变量可以拷贝。与参数不同，被捕获的变量的值是在 lambda创建时拷贝，而不是调用时拷贝:

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

采用引用则改变该值会同时改变：

void fcn2(){
size_t v1 = 42; 	//局部变量
//对象2包含v1的引用
auto f2 =[ &v1] { return vl; };
v1 = 0;
autoj = f2();		//j为0;f2保存v1的引用，而非拷贝

但捕获引用返回引用有一个问题是，必须保证使用lambda时该引用对象存在

void biggies(vector<string> &words, vector<string>::size_type sz, 
             ostream &os= cout,char c = ' ')
{
//与之前例子一样的重排words的代码
//打印count的语句改为打印到os
	for_each (words.begin (), words.end ( ), [ &os,c] (const string &s){ os << s<< c; });
}

由于我们不能拷贝ostream对象，所以拷贝os的唯一方式就时捕获引用（或指向os的指针）

我们可以从函数返回lambda，但该lambda不能捕获引用，因为局部变量消失会使lambda数据成员不可用。

我们应尽量减少引用或指针捕获

隐式捕获

使用=（值捕获）&（引用捕获）告诉编译器接下来我要使用的变量都采用该捕获方式：

1
2
3

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

也可以一部分值捕获，一部分引用捕获：

// os隐式捕获，引用捕获方式;c显式捕获，值捕获方式
for_each ( words.begin(), words.end(), [&, c](const string &s){ os<< s<< c; });
// os显式捕获，引用捕获方式;c隐式捕获，值捕获方式
for_each (words.begin(), words.end(), [=, &os](const string &s){ os << s << c; });

混合捕获必须把默认捕获方式写在前面（只能是=或者&），且显示捕获方式必须与默认不同。

可变lambda

默认情况是如果一个lambda包含除return以外的任何语句，则假定此lambda返回void，则不能返回值，这里使用位置返回类型来返回：

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

transform接受一对迭代器范围，和一个目的地，将由第四个参数调用后放入目的地。

参数绑定bind（跳过）

对于只在一两个地方用到的简单操作可以使用lambda，而很多地方，且操作更多，我们应该使用函数。

再探迭代器

插入迭代器（insert iterator):这些迭代器被绑定到一个容器上，可用来向容器插入元素。
流迭代器(stream iterator):这些迭代器被绑定到输入或输出流上，可用来遍历所关联的IO流。
反向迭代器( reverse iterator ):这些迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器。
移动迭代器（move iterator):这些专用的迭代器不是拷贝其中的元素，而是移动它们。

插入迭代器

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

*it,++it,it++ 这些操作虽然存在，但不会对it做任何事情。每个操作都返回it插入器有三种类型。

差异在于元素插入的位置:

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

插入迭代器还是基于容器自身的push操作，所以必须确保有该操作才可以使用对应的插入迭代器。

*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 () ) );

iostream迭代器（跳过）

反向迭代器

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

除了forward_list之外,其他容器都支持反向迭代器。我们可以通过调用rbegin、rend、crbegin 和 crend 成员函数来获得反向迭代器。这些成员函数返回指向容器尾元素和首元素之前一个位置的迭代器。与普通迭代器一样，反向迭代器也有 const和非const版本。

一些应用：

1
2
3

sort (vec.begin(), vec.end()); //按“正常序”排序vec
//按逆序排序:将最小元素放在vec的末尾
sort (vec.rbegin () , vec.rend () );

//在一个逗号分隔的列表中查找第一个元素
auto comma = find (line.cbegin(), line.cend(), ',' );
cout << string (line.cbegin() , comma) << endl;
//在一个逗号分隔的列表中查找最后一个元素
auto rcomma = find(line.crbegin(), line.crend(), ',');
//错误:将逆序输出单词的字符
cout << string(line.crbegin() , rcomma) << endl;
//正确:得到一个正向迭代器，从逗号开始读取字符直到line末尾
cout << string(rcomma.base(), line.cend()) << endl;

base函数将反向迭代器转换为正向迭代器。

泛型算法结构

算法所要求的迭代器可分为五类：

5类迭代器

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

输入迭代器

他可以读取序列中的元素，必须支持：

用于比较两个迭代器的相等和不相等运算符（ =一、!=)
用于推进迭代器的前置和后置递增运算(++)
用于读取元素的解引用运算符（*);解引用只会出现在赋值运算符的右侧
箭头运算符(->)，等价于(*it) .member，即，解引用迭代器，并提取对象的成员

输入迭代器只用于顺序访问。对于一个输入迭代器，*it++保证是有效的，但递增它可能导致所有其他指向流的迭代器失效。其结果就是，不能保证输入迭代器的状态可以保存下来并用来访问元素。因此,输入迭代器只能用于单遍扫描算法。算法find和 accumulate要求输入迭代器;而istream_iterator是一种输入迭代器。

输出迭代器

可以看作输入迭代器功能上的补集——只写而不读元素。输出迭代器必须支持

用于推进迭代器的前置和后置递增运算（++)
解引用运算符(*)，只出现在赋值运算符的左侧(向一个已经解引用的输出迭代器赋值，就是将值写入它所指向的元素)

我们只能向一个输出迭代器赋值一次。类似输入迭代器，输出迭代器只能用于单遍扫描算法。用作目的位置的迭代器通常都是输出迭代器。例如，copy函数的第三个参数就是输出迭代器。ostream_iterator类型也是输出迭代器。

前向迭代器

可以读写元素。这类迭代器只能在序列中沿一个方向移动。前向迭代器支持所有输入和输出迭代器的操作，而且可以多次读写同一个元素。因此，我们可以保存前向迭代器的状态，使用前向迭代器的算法可以对序列进行多遍扫描。算法replace要求前向迭代器，forward_list上的迭代器是前向迭代器。

双向迭代器

可以正向/反向读写序列中的元素。除了支持所有前向迭代器的操作之外，双向迭代器还支持前置和后置递减运算符(–)。算法 reverse要求双向迭代器，除了forward_list之外，其他标准库都提供符合双向迭代器要求的迭代器。

随机访问迭代器

提供在常量时间内访问序列中任意元素的能力。此类迭代器支持双向迭代器的所有功能

用于比较两个迭代器相对位置的关系运算符(<、<=、>和>=)
迭代器和一个整数值的加减运算(+、+=、-和-=)，计算结果是迭代器在序列中前进（或后退）给定整数个元素后的位置
用于两个迭代器上的减法运算符(-)，得到两个迭代器的距离
下标运算符(iter[n] )，与* (iter [n])等价

算法sort要求随机访问迭代器。array、deque、string和 vector的迭代器都是随机访问迭代器，用于访问内置数组元素的指针也是。

算法形参模式

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为目的地，arg为算法。此外还有一些算法接受额外非迭代器参数。

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

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

向输出迭代器写入数据的算法都假定目标空间足够容纳写入的数据。

常见情况是dest被绑定到一个插入迭代器或ostream_iterator。插入迭代器会将新元素添加到容器中，因而保证空间足够的，ostream_iterator会将数据写入到一个输出流，同样不管要写入多少个元素都没有问题。

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

接受单独的 beg2或是接受beg2和 end2的算法用这些迭代器表示第二个输入范围。这些算法通常使用第二个范围中的元素与第一个输入范围结合来进行一些运算。

如果一个算法接受beg2和 end2，这两个迭代器表示第二个范围。这类算法接受两个完整指定的范围:[beg,end)表示的范围和[ beg2 end2)表示的第二个范围。

只接受单独的 beg2(不接受end2)的算法将beg2作为第二个输入范围中的首元素。此范围的结束位置未指定，这些算法假定从beg2开始的范围与 beg和 end所表示的范围至少一样大。

算法命名规范

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

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

_if版本算法

接受元素值的算法有一个不同名的版本，使用谓词代替元素值，接受谓词参数版本需要加_if:

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

他们狗接受三个参数，因此不是重载。

拷贝与非拷贝版本

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;v1不变
remove_copy_if(vl.begin(), v1.end(), back_inserter(v2), [](int i){ return i % 2;});

特定容器算法

因为如sort等一些通用算法要求随机访问迭代器，而list和forward_list提供的是前向和双向迭代器，所以只能使用他们自己的成员函数算法

链表还有一些splice算法，这些是链表独有的：

特有的操作会改变容器

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

类似的，merge和splice会销毁其参数。例如，通用版本的merge将合并的序列写到一个给定的目的迭代器;两个输入序列是不变的。而链表版本的merge函数会销毁给定的链表——元素从参数指定的链表中删除，被合并到调用merge的链表对象中。在merge之后，来自两个链表中的元素仍然存在，但它们都已在同一个链表中。