泛型算法-1

CPP
CPP
发布日期:   2019-01-03

泛型算法-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个或多个来自所在函数的变量，这些变量采用引用捕获方式，且变量名字前必须使用&。任何隐式捕获的变量都采用值方式捕获
文章作者: ShanSan
文章链接: http://yeshan333.github.io/2019/01/03/%E6%B3%9B%E5%9E%8B%E7%AE%97%E6%B3%95-1/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 ShanSan !
CPP
赏
 上一篇
Jinja2语法小记 Jinja2语法小记
jinja2模板语法小记 Jinja2模板中文文档 三种常见界定符 表达式{{ ... }} 用于装载字符串、变量、函数调用等 语句{% ... %} 用于装载控制语句，比如if判断、for循环等 注释{# ... #}
2019-01-09 Flask
Flask
下一篇 
装饰器--python 装饰器--python
python装饰器回顾返回函数 什么是装饰器 python装饰器就是用于拓展原来函数功能的一种函数，目的是在不改变原函数定义的情况下，给函数增加新的功能。这个函数的特殊之处在于它的返回值也是一个函数，这个函数是内嵌“原”函数的函数 在
2019-01-03 Python
Python
  目录