泛型算法-1

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

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

算法永远不会执行容器的操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/*算法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.二元谓词:它们接受两个参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//定制操作,按照长度重新排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表达式可定义在函数内部

基本形式:

1
[capture lsit](parameter list)  ->  return type {function body}
  • capture list(捕获列表): 一个lambda所在函数中的定义的局部变量的列表(通常为空)
  • parameter list(参数列表)
  • return type(返回类型)
  • function body(函数体)

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

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

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

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

捕获列表的使用

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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体中的代码来推断我们要使用哪些变量

  • &告诉编译器采用引用捕获方式
  • =告诉编译器采用值捕获方式
混合使用显式捕获和隐式捕获时,显示捕获必须使用与隐式捕获不同的方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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定义返回类型时,必须使用尾置返回类型
  • 尾置返回类型跟在形参列表后面,并以一个
    1
    2
    3
    4

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

可变lambada

使用关键字

1
2
3
4
5
6

```c++
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个或多个来自所在函数的变量,这些变量采用引用捕获方式,且变量名字前必须使用&。任何隐式捕获的变量都采用值方式捕获

 评论