第十章

10.1 概述

泛型算法: 它们可用于 不同类型的容器 和 不同类型的元素

大多数算法都定义在头文件algorithm中。标准库还在头文件numeric中定义了一组数值泛型算法

查找特定值:find(迭代器范围，要查找的数)

eg: int val = 42;
    auto result = find(vec.cbegin(),vec.cend(),val); //找到返回该元素地址，未找到返回尾后迭代器

关键概念:算法永远不会执行容器操作

泛型算法本身不会执行容器的操作，它们只会运行与迭代器之上，执行迭代器的操作
算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但永远不会直接添加或删除元素

10.2 初识泛型算法

10.2.1 只读算法

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

int sum = accumulate(vec.cbegin(),vec.cend(),0); 
//前两个参数指出了需要求和的元素范围，第三个参数是和的初值accumulate的第三个参数的类型决定了函数中使用哪个加法运算符以及返回值类型

操作两个序列的算法

只读算法equal，用来确定两个序列是否保存相同的值。

equal(roster1.cbegin(),roster1.cend(),roster2.cbegin()); 
//前两个参数表示第一个序列的元素范围，第三个参数是第二个序列的首元素    

注:equal基于一个非常重要的假设:它假设第二个序列至少与第一个序列一样长。
注：那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长

10.2.2 写容器算法（修改元素的值，但不会改变容器内元素的个数）

一些算法将新值赋予序列中的元素。当我们使用这类算法时，必须注意确保序列原大小至少不小于我们要求算法写入的元素数目。
切记算法不会执行容器操作，因此不能改变容器大小

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

算法不检查写操作

    fill_n接受一个单迭代器、一个计数值和一个值
    fill_n(dest,n,val);  //从dest开始的序列修改后面n个元素的值为val
    注：非常容易犯的错误就是在空容器中调用fill_n
    vector<int> vec; //空向量
    fill_n(vec.begin(),10,0);   //灾难：修改vec中10个不存在的元素

介绍back_inserter(定义在iterator头文件中)
一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器。
插入迭代器是一种向容器中添加元素的迭代器

当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素被添加到容器中
back_inserter接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，
赋值运算符会调用push_back将一个具有给定值的元素添加到容器中

    eg:vector<int> vec;
    auto it = back_inserter(vec);
    *it = 40;    //vec中现在有一个元素，值为42

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

    eg:vector<int> vec;
    //back_inserter创建一个插入迭代器，可用来向vec添加元素
    fill_n(back_inserter(vec),10,0);   //添加10个元素到vec

拷贝算法
拷贝算法是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法。

此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。此算法将输入范围中的元素拷贝到目的序列中。传递给copy的目的序列至少要包含与输入序列一样多的元素

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

replace(输入序列范围迭代器,输入序列范围迭代器,val1,val2,); //前两个迭代器，表示输入序列，后两个一个是要搜索的值，另一个是新值。它将所有等于第一个值的元素替换为第二个值

    replace(ilist.begin(),ilist.end(),0,42);  //将所有值为0的元素改为42

10.2.3 重排容器元素的算法

某些算***重排容器中元素的顺序，例如sort，调用sort会重排输入序列中的元素，使之有序，它是利用 元素类型的"<" 运算符来实现排序的
为了消除重复单词，首先将vector排序，使得重复单词都相邻出现。一旦vector排序完毕，就可以使用另一个称为unique的标准库算法来重排vector,使得不重复元素出现在vector的开始部分

    void elimDups(vetor<string> &words){
        //按字典排序words，以便查找重复单词
        sort(words.begin(),words.end());
        //unique重排输入范围，使得每个单词只出现一次
        auto end_unique = unique(words.begin(),words.end());
        //使用向量操作earse删除重复单词
        words.earse(end_unique,words.end());
    }  

使用unique

words排序完毕后，我们希望将每个单词都只保存一次。unique算法重新输入序列，将相邻的重复项删除，并返回一个指向不重复范围末尾的迭代器。

10.3 定制操作

    标准库为算法定义了额外的版本，允许我们提供自己定义的操作来代替默认运算符

10.3.1向算法传递函数

谓词：谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。

标准库的谓词分为两类:一元谓词(意味着它们只接受单一参数)和二元谓词(意味着它们有两个参数)接受谓词参数的算法对输入序列中的元素调用谓词，因此，元素类型必须能转换为谓词的参数类型

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

排序算法
    为了保持相同长度的单词按字典排列，可以使用stable_sort算法，这种稳定排序算法维持相等元素的原有顺序
eg: elimDups(words);    //将words按字典序重排，并消除重复单词
    stable_sort(words.begin(),words.end(),isShorter);   //按长度重新排序，长度相同的单词维持字典序

10.3.2 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的元素的数目
        //打印长度大于等于给定值的单词，每个单词后面接一个空格
}            

介绍lambda

我们可以向一个算法传递任何类别的可调用对象。
对于一个对象或一个表达式，如果可以对其使用调用运算符(一对小括号就是调用运算符)，则称它为可调用的。即，如果e是一个可调用的表达式，则我们可以编写代码e(args),其中args是一个逗号分隔的一个或多个参数列表

C++中有四种可调用对象：函数，函数指针，重载了函数调用运算符的类以及lambda表达式

一个lambda表达式表示一个可调用的代码单元。可以将其理解为一个未命名的内联函数。与任何函数相似，一个lambda具有一个返回类型，一个参数列表和一个函数体。

但于函数不同，lambda可能定义在函数内部。一个lambda表达式具有如下形式:

[capture list](parameter list)->returu type{ function body}
其中，capture list(捕获列表)是一个lambda所在函数中定义的局部变量的列表(通常为空);returun type,parameter list和  
function body与任何普通函数一样，分别表示返回类型，参数列表和函数体，但是与普通函数不同，lambda必须使用尾置返回来
指定返回类型

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

auto f = [] {return 42};  //定义了一个可调用对象f,它不接受参数，返回42

lambda的调用方式与普通函数的调用方式相同，都是使用调用运算符"()":

eg: cout << f() <<endl;

注：如果lambda表达式的函数体包含任何单一return语句之外的内容，并且未指定返回类型，则返回void

向lambda传递参数

与一个普通函数调用类似，调用一个lambda时给定的实参被用来初始化lambda的形参。通常，实参和形参的类型必须匹配，但与普通函数不同，lambda不能有默认参数。因此，一个lambda调用的实参数目永远与形参数目相等，一旦形参初始化完毕，就可以执行函数体了。

编写一个与isShorter函数完成相同功能的lambda

    [](const string &a,const string &b){return a.size() < b.size();} 
    //空捕获列表表明此lambda不适用它所在函数中的任何局部变量
    eg:可是使用lambda来调用stable_sort
    stable_sort(words.begin(),words.end(),[](const string &a,const string &b){return a.size() < b.size()});

使用捕获列表

虽然一个lambda可以出现在一个函数中，使用其局部变量，但它只能使用那些明确指明的变量。一个lambda通过局部变量包含在
其捕获列表中来指出将会使用这些变量

    [sz](const string &a)
        {return a.size() >= sz};
    由于此lambda捕获sz,因此lambda的函数体可以使用sz
    [](const string &a)
      {return a.size() >= sz}  //错误，sz未捕获

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

调用find_if

auto wc = find_if(words.begin(),words.end(),[sz](const string &a){return a.size() >= sz;});

for_each算法

for_each(wc,words.end(),[](const string &a){cout << s << " ";});

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

lambda捕获和返回

当定义一个lambda时，编译器生成一个与lambda对应的新的(未命名的)类类型

值捕获

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

void fcn1(){
    size_t v1 = 42;
    auto f = [v1]{return v1};
    v1 = 0;
    auto j = f();    //j为42；f保存了我们创建它时v1的拷贝
}

引用捕获

void fcn2(){
    size_t v1 = 42;
    auto f2 = [&v1]{return v1;};
    v1 = 0;
    auto j = f2();  //j为0；f2保存v1的引用，而非拷贝

}

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

当以引用捕获一个变量时，必须保证在lambda执行时变量时存在的

隐式捕获

为了指示编译器推断捕获列表，应在捕获列表中写一个&或=。&告诉编译器采用捕获引用方式，=则表示采用值捕获方式。

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

如果希望对一部分变量采用值捕获，对其他变量采用引用捕获，可以混合使用隐式捕获和显式捕获

void biggies(vector<string> &words,vector<string>::size_type sz,ostream &os = cout,char 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;});
//os是显示引用捕获，c是隐式值捕获
}

当我们混合使用隐式捕获和显式捕获时，捕获列表中的第一个元素必须是&或=。此符号指定了默认捕获方式为引用或值
|表10.1 | lambda捕获列表
--|:--
[ ]| 空捕获列表。lambda不能使用所在函数中的变量。一个lambda只有捕获变量后才能使用它们
[names]|names是一个逗号分隔的名字列表，这些名字都是lambda所在函数的局部变量。
[&]|隐式捕获列表，采用引用捕获方式。lambda体中所使用的的来自所在函数的实体都采用引用方式使用
[=]|隐式捕获列表，采用值捕获方式。lambda体将拷贝所使用的来自所在函数的实体的值
[&,identifire_list]|identifire_list是一个逗号分隔的列表，包含0个或多个来自所在函数的变量。这些变量采用支捕获方式，而任何隐式捕获的变量都采用引用的方式捕获。identifier_list中的名字前面不能使用&
[=,identifier_list]|identifier_list中的变量都采用引用方式捕获，而任何隐式捕获的变量都采用值方式捕获。identifier_list中的名字不能包括this，且这些名字之前必须使用&

可变lambda

默认情况下，对一个值被拷贝的变量，lambda不会改变其值。如果希望改变一个被捕获的变量的值，就必须在参数列表加上关键字mutable。因此,可变lambda能省略参数列表

void test(){
    int a = 42;
    auto f = [a](){return ++a; }; //错误，不能改变其值，应该是一个顶层const
    auto f = [a]()mutable{return ++a; };
    std::cout << a << std::endl;         //a ==42
    //a = 0;
    auto j = f();                     // j == 43
    std::cout << a << std::endl;     // a == 42
    std::cout << j << std::endl;   // j == 43

}

一个引用捕获的变量是否可以修改依赖于此引用指向的是一个const类型还是一个非const类型

void test(){
    const int a = 42;
    auto f = [&a](){return ++a; };    //错误因为a是const所以不能改变其值
    std::cout << a << std::endl;
    a = 0;
    auto j = f();
    std::cout << a << std::endl;
    std::cout << j << std::endl;
}

指定lambda返回类型

如果一个lambda体包含return之外的任何语句，并且没有指定返回类型，则编译指定lambda返回void
当我们需要为一个lambda定义返回类型时，必须使用尾置返回类型

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