10.1 概述

:::info 什么是泛型算法？
标准库并未给每个容器都定义成员函数来实现这些操作，而是定义了一组泛型算法(generic algorithm)：称它们为“算法”，是因为它们实现了一些经典算法的公共接口，如排序和搜索；称它们是“泛型的”，是因为它们可以用于不同类型的元素和多种容器类型(不仅包括标准库类型，如vector或list，还包括内置的数组类型） ::: :::tips

  • 大多数算法都定义在头文件algorithm中。标准库还在头文件numeric中一组数值泛型算法
  • 一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的一个元素范围（参见9.2.1节，第296页）来进行操作。通常情况下，算法遍历范围，对其中每个元素进行一些处理。

  • 泛型算法本身不会执行容器的操作，它们只会运行于迭代器之上，执行迭代器的操作。泛型算法运行于迭代器之上而不会执行容器操作的特性带来了一个令人惊讶但非常必要的编程假定：算法永远不会改变底层容器的大小。 :::

    10.2 初识泛型算法

    :::info 理解算法的最基本的方法就是了解它们足否读取元素、改变元素或是重排元素顺序 :::

    只读算法

    一些算法只会读取其输入范围内的元素，而从不改变元素。find就是这样一种算法,我们在10.1节练习(第337页)中使用的count函数也是如此。

    1. int sum = accumulate(vec.cbegin(),vec.cend(),0);
    2. //accumulate的第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型。

    accumulate第三个参数是求和的起点这蕴含着一个编程假定：将元素类型加到和的类型上的操作必须是可行的。即，序列中元素的类型必须与第三个参数匹配，或者能够转换为第三个参数的类型。

    写容器算法

    如之前所说，算法不会改变容器大小 :::tips

  • 算法不会执行容器操作，因此它们自身不可能改变容器的大小。

  • 向目的位置迭代器写入数据的算法假定目的位置足够大，能容纳要写入的元素 :::

    back_inserter

    一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器(insert iterator)。插入迭代器是一种向容器中添加元素的迭代器。通常情况，当我们通过一个迭代器向容器元素赋值时，值被赋予迭代器指向的元素。而当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素被添加到容器中。 :::info back_inserter接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中 :::

    1. vector<int>vec;/ /空向量
    2. //正确：back_inserter创建一个插入迭代器，可用来向vec添加元素
    3. fill_n(back_inserter(vec),10,0);//添加10个元素到vec

    重排算法

    sort

    某些算法会重排容器中元素的顺序，一个明显的例子是sort。调用sort会重排输入序列中的元素，使之有序，它是利用元素类型的<运算符来实现排序的。

    unique

    unique算法重排输入序列,将相邻的重复项“消除”，并返回一个指向不重复值范围末尾的迭代器。 :::tips 标准库算法对迭代器而不是容器进行操作。因此，算法不能（直接）添加或删除元素。 ::: image.png

    10.3 制定操作

    :::info 很多算法都会比较输入序列中的元素。默认情况下，这类算法使用元素类型的<或=运算符完成比较。标准库还为这些算法定义了额外的版本，允许我们提供自己定义的操作来代替默认运算符。 :::

    谓词

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

    1. bool isShorter(const string&s1,const string&s2){
    2.   return s1.size()<s2.size();
    3. }
    4. //按长度由短至长排序words
    5. sort(words.begin(),words.end(),isShorter);

    lambda表达式

    根据算法接受一元谓词还是二元谓词，我们传递给算法的谓词必须严格接受一个或两个参数。但是，有时我们希望进行的操作需要更多参数，超出了算法对谓词的限制。除了传递谓词，还能传递lambda表达式。 :::info 一个lambda表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。与任何函数类似，一个lambda具有一个返回类型、一个参数列表和一个函数体。但与函数不同，lambda可能定义在函数内部。 :::

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

    :::tips capture list（捕获列表）是一个lambda所在函数中定义的局部变量的列表（通常为空）；
    return type、parameter list和function body与任何普通函数一样，分别表示返回类型、参数列表和函数体。但是，与普通函数不同，**lambda**必须使用尾置返回 :::

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

    向lambda传递参数

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

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

    使用捕获列表

    :::info 一个lambda通过将局部变量包含在其捕获列表中来指出将会使用这些变量。捕获列表指引lambda在其内部包含访问局部变量所需的信息。
    我们只对lambda所在函数中定义的（非static)变量使用捕获列表。一个lambda可以直接使用定义在当前函数之外的名字。 :::

    1. for_each(wc,words.end(),
    2. [](const string&s){cout<<s<<endl;})

    lambda捕获和返回

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

:::tips 默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员。类似任何普通类的数据成员，lambda的数据成员也在lambda对象创建时被初始化。 ::: image.png

值捕获

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

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

引用捕获

:::tips 我们定义lambda时可以采用引用方式捕获变量。
一个以引用方式捕获的变量与其他任何类型的引用的行为类似。当我们在lambda函数体内使用此变量时，实际上使用的是引用所绑定的对象。 :::

  1. void fcnl(){
  2.     size_t v1=42;                //局部变量
  3.     auto f=[&v1]{return v1;};    
  4.     v1=0;
  5.     auto j=f();                    //j为0;f保存了我们创建它时v1的引用
  6. }

:::danger 默认情况下，对于一个值被拷贝的变量，lambda不会改变其值。如果我们希望能改变—个被捕获的变量的值，就必须在参数列表前加上关键字mutable。 :::

参数绑定 bind

:::info 可以将bind函数看作一个通用的函数适配器，它接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表. ::: 调用bind的一般形式：

  1. auto newCallable=bind(callable,arg_list)
  • newCallable是一个可调用对象

  • arg_list是逗号隔开的参数列表，是给callable的参数 :::tips 当我们调用newCallable时，newCallable会调用callable，并且将参数列表传递给callable； :::

  • arg_list中会有形如_n的占位符，该参数在生成的newCallable中的第几位。

    1. auto check6=bind(check_sz,_1,6);
    2. string s="hello!";
    3. check6(s);//会调用check_sz(s,6);
    4. //=======================================
    5. auto g=bind(f,a,b,_2,c,_1);
    6. g(X,Y);//会调用f(a,b,Y,c,X);

    :::tips

  • _n占位符出现在std namespace中，因此应该带有using指令

  • 标准库定义了两个分别名为bind1st和bind2nd的函数。类似bind,这两个函数接受一个函数作为参数，生成一个新的可调用对象，该对象调用给定函数，并将綁定的参数传递给它。但是，这些函数分别只能綁定第一个或第二个参数。由于这些函数局限太强，在新标准中已被弃用（deprecated)。所谓被弃用的特性就是在新版本中不再支持的特性。新的C++程序应该使用bind。 :::

    10.4 再探迭代器

    还有几种额外的迭代器：

    插入迭代器

    插入器是一种迭代器适配器，它接受一个容器，生成一个迭代器，能实现向给定容器添加元素。当我们通过一个插入迭代器进行赋值时，该迭代器调用容器操作来向给定容器的指定位置插入一个元素
    插入器有三种类型，差异在于元素插入的位置: :::info

  • back_inserter

  • front_inserter
  • inserter:创建一个使用insert的迭代器。此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。 ::: :::tips 只有在容器支持push_back的情况下，才能用back_inserter；同理，需要有push_front才能front_inserter； :::

    iostream迭代器

    :::info 虽然iostream不是容器，但是标准库定义了迭代器，istream_iterator读 取 输 入 流，ostream_iterator向一个输出流写数据。迭代器将它们对应的流当作一个特定类型的元素序列来处理 :::
    1. istream_iterator<int> in_iter(cin);
    2. istream_iterator<int> eof;
    3. while(in_iter!=eof)
    4. //后置递增运算读取流，返回迭代器的旧值
    5. //解引用迭代器，获得从流读取的前一个值
    6. vec.push_back(*in_iter++);
    7. //--------------------------------------------------
    8. istream_iterator<int> in_iter(cin),eof;
    9. vector<int> vec(in_itr,eof);

10.5 泛型算法结构

:::info 任何泛型算法的基本要求就是看其要求迭代器提供哪些操作；按照需求不同，可以分成5类迭代器； ::: c67b4d6f6c8113f082b167a3974eadbc.png

迭代器的层次

:::info 迭代器也定义了一组公共操作。一些操作所有迭代器都支持，另外一些只有特定类别的迭代器才支持。例如，ostream_iterator只支持递增、解引用和赋值。vector、string和deque的迭代器除了这些操作外，还支持递减、关系和算术运算。迭代器是按它们所提供的操作来分类的，而这种分类形成了一种次。 :::

输入迭代器(input iterator)

可以读取序列中的元素。
一个输入迭代器必须支持

  • 用于比较两个迭代器的相等和不相等运算符（=、！=)
  • 用于推进迭代器的前置和后置递增运算（++)
  • 用于读取元素的解引用运算符（*);解引用只会出现在赋值运算符的右侧

  • 箭头运算符（->),等价于（*it).member,即，解引用迭代器，并提取对象的成员

    输出迭代器（output iterator)

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

  • 用于推进迭代器的前置和后置递增运算（++)

  • 解引用运算符（*)，只出现在赋值运算符的左侧（向一个已经解引用的输出迭代器赋值，就是将值写入它所指向的元素）

前向迭代器（forwarditerator)

可以读写元素。这类迭代器只能在序列中沿一个方向移动。前向迭代器支持所有输入和输出迭代器的操作，而且可以多次读写同一个元素

双向迭代器（bidirectionaliterator)

可以正向/反向读写序列中的元素。除了支持所有前向迭代器的操作之外，双向迭代器还支持前置和后置递减运算符(—)。

随机访问迭代器(random-accessiterator)

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

算法的形参模式

大多数算法都具有如下形式之一的参数列表：
b5f710c424a4644260491c00c9a52a6d.png

算法命名规范

重载来传递谓词

接受谓词参数来代替<或=运算符的算法，以及那些不接受额外参数的算法，通常都是重载的函数。、

  1. unique(beg,end);
  2. unique(beg,end,com);

_if来区别谓词

接受一个元素值的算法通常有另一个不同名的（不是重载的）版本，该版本接受一个谓词代替元素值。接受谓词参数的算法都有附加的_if前缀

  1. find(beg,end,val);
  2. find_if(beg,end,pred);

区分拷贝和不拷贝的版本

默认情况下，重排元素的算法将重排后的元素写冋给定的输入序列中。这些算法还提供另一个版本，将元素写到一个指定的输出目的位置。

  1. reverse(beg,end);
  2. reverse_copy(beg,end,dest);