C++ primer摘要(8)---泛型算法

泛型算法

概述

使用标准库算法find查找vector中的特定元素

int val = 42;
auto result = find(vec.cbegin(),vec.cend(),val);
cout << (result == vec.cend() ? "not present" : "presend") << endl;

传递给find的前两个参数是表示元素范围的迭代器，第三个参数是要寻找比对的值，如果范围中无匹配元素，则find返回第二个参数表示失败

find操作的是迭代器，所以可以用find在任何容器中查找值

可以用find在数组中擦护照值

int ia[] = {1,1,5,9,56,847,56};
int val = 83;
int * result = find(begin(ia),end(ia),val)

迭代器令算法不依赖于容器，但算法依赖于元素类型的操作

算法用于不会执行容器的操作

- [x] 泛型算法本身不会执行容器的操作，它们只会运行在迭代器之上，执行迭代器的操作
- [x] 算法永远不会改变底层容器的大小，算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但他永远不会直接添加或删除元素
- [x] 标准库定义了一类特殊的迭代器，成为`插入器`，当给这类迭代器赋值时，它们会在底层的容器上执行插入操作，因此，当一个算法操作这样的迭代器时，迭代器可以完成向容器添加元素的效果，但算法自身永远不会做这样的操作

泛型算法

除了少数例外，标准库算法都对一个范围内的元素进行操作

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

只读算法

find、accumulate以及equal函数接受三个参数

accumulate定义在头文件'numeric'中，它的前两个参数指出了需要求和的元素的范围，第三个参数是和的初始值

int sum = accumulate(vec.cbegin(),vec.cend(),0);       //对vec中的元素求和，和的初始值是0
string sum = accumulate(v.cbegin(),v.cend(),"");

accumulate的第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型

对于只读取而不改变元素的算法，最好使用cbegin()和cend()

equal是操作两个序列的算法

- [x] equal用于确定两个序列是否保存相同的值，它将第一个序列中的每个元素与第二序列中的对应元素进行比较，如果所有对应元素都相等，则返回true，否则返回false
- [x] 此算法接受三个迭代器，前两个表示第一个序列中的元素范围，第三个表示第二个序列的首元素

equal(roster1.cbegin(),roster1.cend(),roster2.cbegin());       //roster2中的元素数目至少应该与roster1一样多

equal基于一个非常重要的假设，它假定第二个序列至少与第一个序列一样长

那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长

写容器元素的算法

算法fill接受一对迭代器表示一个范围，还接受一个值作为第三个参数，fill将给定的这个值赋予输入序列中的每个元素

fill(vec.begin(),vec.end(),0);  //将每个元素重置为0

算法不检查写操作

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

copy算法

- [x] 此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置

int a1[] = {0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1)/sizeof(*a1)];         //a1和a2大小一样
auto ret = copy(begin(a1),end(a1),a2);     //把a1的内容拷贝给a2

replace算法

- [x] 读入一个序列，并将其中所有等于给定值的元素都改为另一个值
- [x] 此算法接受四个参数:前两个是迭代器，表示输入序列，后两个一个是要搜索的值，另一个是新值
- [x] 它将所有等于第一个值的元素替代为第二个值

replace(list.begin(),list.end(),0,42);

如果需要真正的删除无用元素，必须使用容器操作，例如erase

定制操作

lambda表达式

一个lambda表达式表示一个可调用的代码单元，我们可以将其裂解为一个未命名的内联函数

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

lambda表达式必须使用尾置返回

lambda表达式可以忽略参数列表(parameter list)和返回类型(return type)，但必须永远包含捕获列表(capture)和函数体(function body)

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

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

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

尽量保持lambda的变量捕获简单化

迭代器

除了为每个容器定义的迭代器之外，标准库在头文件iterator中还定义了额外几种迭代器

- [x] **插入迭代器**：这些迭代器被绑定到一个容器上，可以用来向容器插入元素
    - **back_inserter**
    - **front_inserter**
    - inserter
    - 只有在容器支持push_front的情况下，我们才可以使用front_inserter,类似，只有在容器支持push_back的情况下，才能使用back_inserter
- [x] **流迭代器**：这些迭代器被绑定到输入或输出流上，可用来遍历所关联的IO流
    - **istream_iterator**读取输入流
    - **ostream_iterator**向一个输出流写数据
- [x] **反向迭代器**：这些迭代器向后而不是向前移动(在容器中从尾元素向首元素反向移动)，除了forward_list之外的标准库容器都有反向迭代器
    - 对于反向迭代器，递增或递减操作的含义会反过来
    - **rbegin\rend\crbegin\crend**
- [x] **移动迭代器**：这些专用的迭代器不是拷贝其中的元素，而是移动它们

泛型算法结构

算法形参模式

大多数算法具有如下四种形式之一:

alg(beg,end,other args);
alg(beg,end,dest,other args);
alg(beg,end,beg2,other args);
alg(beg,end,beg2,end2,other args);

接受单个目标迭代器的算法家栋目标空间足够容纳写入的数据

接受第二个输入序列的算法假定从beg2开始的序列与beg和end所表示的范围至少一样大

特定容器算法(链表类型算法)

对于list和forward_list，应该优先使用成员函数版本的算法而不是通用算法

多数链表特有的算法都与其通用版本相似，但不完全相同，链表特有版本与通用版本间的一个至关重要的区别是链表版本会改变底层的容器