泛型算法-1

Cloud-Cloudys

发布于 2020-07-07 16:14:28

6610

发布于 2020-07-07 16:14:28

文章被收录于专栏：ShanSan的云原生之路ShanSan的云原生之路

泛型算法-1

泛型算法实现了一些经典算法的公共接口，如排序和搜索；称它们是“泛型的”，是因为它们可以用于不同类型的元素的和多种容器类型（不仅包括标准库类型，还包括内置的数组类型），以及其它类型的序列。

** 大多数算法都定义在头文件algorithm中 **

算法永远不会执行容器的操作

/*算法find*/
/*
- find将范围内中的所有元素与给定值进行比较，返回指向第一个等于给定值的迭代器
- 如果范围内无匹配元素，则find返回第二个参数来表示搜索失败 
*/ 
void find_value()
{
    //find函数的返回值类型是迭代器类型 
	//在vector中查找值 
	int val = 7;
	vector<int> v{1,2,3,4,5,6,7,8};
	
	auto result = find(v.begin(),v.end(),val);
	
	cout<<*result<<endl;
	
	//在数组中查找值 
	int nums[10] = {1,2,3,4,5,6,7,8,9,10};
	auto search = find(begin(nums),end(nums),11);//值不存在，返回尾后迭代器 
	cout<<*search<<endl; 	
} 

/*算法count*/
/*
- 返回给定值在序列中出现的次数 
*/ 
void value_count()
{
	//count函数返回给定值在序列中出现的次数
	int a[]={1,1,1,1,1,2,3,4,5,6};
	auto c = count(a,a+10,1);
	cout<<"1出现的次数:"<<c<<endl; 
}


/*算法accumulate*/ 
/*
- accumulate将第三个参数作为求和起点
- 注意序列中的元素的类型必须与第三个参数匹配 
*/ 
void sum_num()
{
	//accumulate函数用去求给定元素范围内元素的和 
	vector<int> v={1,2,3,4,5,6,7,8,9,10};
	auto sum = accumulate(v.begin(),v.end(),0);
	
	vector<int> v_compare{1,2,3,4,5,6,7,8,9,10,11};
	
	if( equal(v.begin(),v.end(),v_compare.begin()) )
	    cout<<"yeah"<<endl;
	
	cout<<sum<<endl;
}

/*算法fill*/
/*
- 用于确定两个序列中是否保存相同的值
- 第二个序列至少与第一个序列一样长 
*/ 
void init_fill()
{
	vector<int> v{1,2,3,4,5,6,7,8};
	fill(v.begin(),v.end(),1);//不要对空容器使用此操作 
	for(auto a:v)
	    cout<<a<<" ";
}

void elimDups(vector<string> &words)
{
	void print(vector<string> v);
	sort(words.begin(),words.end());
	//使用sort算法按字典序重排序列 
	
	//unique重排了输入范围，使得每个单词只出现一次，
	//unique返回指向不重复区域之后一个位置的迭代器 
	auto end_unique = unique(words.begin(),words.end());
	//删除重复元素 
	words.erase(end_unique,words.end());
	print(words);
}

void print(vector<string> v)
{
	for(auto a:v)
	    cout<<a<<" ";
	cout<<endl;
}

//定制操作，按照长度重新排vector
bool isShorter(const string &s1,const string &s2)
{
    return s1.size() > s2.size();	
} 

//按长度进行排序 
void length_sort(vector<string> &words)
{
    sort(words.begin(),words.end(),isShorter);
	print(words);
	
	//使用算法stable_sort来保持等长元素间的字典序 
    stable_sort(v.begin(),v.end(),isShorter);
	print(v);	
}

向算法传递函数

算法谓词

算法谓词即标准库算法传递的参数, 可以指定算法的操作，它是一个可以调用的表达式，其返回结果是一个能用作条件的值
接受谓词参数的算法对输入序列中的元素调用谓词。因此元素类型必须能转换成谓词的参数类型

标准库算法所使用的谓词分为两类： 1.一元谓词：它们只接受一个参数 2.二元谓词：它们接受两个参数

//定制操作，按照长度重新排vector
bool isShorter(const string &s1,const string &s2)
{
    return s1.size() > s2.size();	
} 

//按长度进行排序 
void length_sort(vector<string> &words)
{
    sort(words.begin(),words.end(),isShorter);
	print(words);
	
	//使用算法stable_sort来保持等长元素间的字典序 
    stable_sort(v.begin(),v.end(),isShorter);
	print(v);	
}

这里向算法stable_sort传递的第三个参数就是一个谓词

lambda表达式（匿名函数）

lambda表达式与其它函数的区别是：lambda表达式可定义在函数内部

基本形式：

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

capture list(捕获列表): 一个lambda所在函数中的定义的局部变量的列表（通常为空）
parameter list(参数列表)
return type(返回类型)
function body(函数体)

** 我们可以忽略形参列表和返回类型，但是必须永远包含捕获列表和函数体 **

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

上面的向算法stable_sort传递的实参可以改写为,效果还是一样的

stable_sort(v.begin(), v.end(), [](const string &a,const string s&b){return a.size()<b.size()});

捕获列表的使用

一个lambda可以出现在一个函数内部，使用其局部变量，但它只能使用那些指明的变量。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

void biggies(vector<string> &words,vector<string>::size_type sz){
	
	//使用sort算法按字典序重排序列 s
	sort(words.begin(),words.end());

	//unique重排了输入范围，使得每个单词只出现一次，
	//unique返回指向不重复区域之后一个位置的迭代器 
	auto end_unique = unique(words.begin(),words.end());
	//删除重复元素 
	words.erase(end_unique,words.end());
	
	//按长度排序,长度相同的按字典序排 
	stable_sort(words.begin(),words.end(), 
	[](const string &a,const string &b){return a.size() < b.size();});
	
	//算法find_if返回一个迭代器，这个迭代器指向第一个满足size()>=sz的元素
	//这里用到了捕获列表，使用局部变量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<<"the numbers of word longer than "<<sz<<": "<<count<<endl; 
	
	//打印长度大于等于给定值sz的单词
	//算法for_earch接受一个可调用对象，并对输入序列中的每个元素调用此对象 
	for_each(wc,words.end(),[](const string &s){ cout<<s<<" "; });	
}

int main()
{
	vector<string> words;
	string str;
	while(cin>>str)
	    words.push_back(str);
	
	for(auto a:words)
	    cout<<a<<" ";
	cout<<endl;
	
	biggies(words,6);//打印长度大于或等于给定值的单词 
 	
	return 0;
}

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

lambada捕获和返回

变量的捕获方式有两种:值捕获、引用捕获
使用引用捕获变量时，必须确保被引用的对象在lambda执行的时候是存在的
lambda捕获的是局部变量，这些变量在函数结束后就不复存在了

我们可以从一个函数返回lambda，函数可以直接返回一个可调用对象，或者返回一个类对象，该类含有可调用对象的数据成员。如果函数返回一个lambda，则与函数不能返回一个局部变量类似，此lambda也不能包含引用捕获

使用&、=进行隐式捕获

我们可以让编译器根据lambda体中的代码来推断我们要使用哪些变量

&告诉编译器采用引用捕获方式
=告诉编译器采用值捕获方式

混合使用显式捕获和隐式捕获时,显示捕获必须使用与隐式捕获不同的方式

#include<iostream>
#include<vector>
#include<algorithm> 
using namespace std;

void biggies(vector<string> &words, ostream &os=cout, char c=' ')
{
	//os隐式捕获，c显式捕获 
    for_each(words.begin(), words.end(), [&, c](const string &s){ os<<s<<c;} );
    
	printf("\n");
	
	//c隐式捕获，os显示捕获 
	for_each(words.begin(), words.end(), [=, &os](const string &s){ os<<s<<c;} );   
}


int main()
{
    vector<string> str;
	string temp;
	
	while(cin>>temp)
	    str.push_back(temp);
		
	biggies(str);
	
	return 0;	
}

指定lambda的返回类型

要为一个lambda定义返回类型时，必须使用尾置返回类型
尾置返回类型跟在形参列表后面，并以一个->符号开头

auto f = [](int i)->int{ return i+1;};
cout<<f(3)<<endl;//输出结果为：4

可变lambada

使用关键字mutable改变一个被捕获变量的值

int i=1;
auto f = [i]()mutable{ return ++i;};
i=0;
cout<<f();//输出结果为2

lambda捕获列表

	说明
[]	空捕获列表。lambda不能使用所在函数中的变量。一个lambda只有捕获变量后才能使用它们
[names]	names是一个逗号分隔的名字列表，这些名字都是lambda所在函数的局部变量。默认情况下，捕获列表中的变量都被拷贝
[&]	隐式捕获列表，采用隐式捕获方式
[=]	隐式捕获列表，采用值捕获方式
[&, identifier_list]	identifier_list是一个逗号分隔的列表，包含0个或多个来自所在函数的变量，这些变量采用值捕获方式。任何隐式捕获的变量都采用引用方式捕获
[=, identifier_list]	identifier_list是一个逗号分隔的列表，包含0个或多个来自所在函数的变量，这些变量采用引用捕获方式，且变量名字前必须使用&。任何隐式捕获的变量都采用值方式捕获