泛型算法

能够通用于各种容器的算法。

算法的一切都是基于容器通用的迭代器与容器元素类型的自己的函数来进行的。因此能够泛化。因此，不管容器为何，算法都是能用的。但是由于只使用迭代器，算法并不能改变底层容器的大小，虽然有可以插入元素的迭代器存在。

只读算法

最好使用cbegin()与cend()

1. find(begin,end,val)

2. find_if(begin,end,predicate)

   对于元素调用谓词，若谓词返回为非0值则算成功。

3. accumulate(begin,end,初始值)

   虽然允许元素与初值的类型不同，但是必须得能够相加才行。

4. equal(begin1,end1,begin2)

   对于三参数迭代器参数都需要保证第二个容器的大小大于等于第一个，因为其并不会检查当前访问元素是否存在，而是直接访问，因此会访问不存在的元素，产生报错。

写元素算法

需保证原大小大于写入新序列的大小。

1. fill(begin,end,val)

2. fill(begin,num,val)

   需要保证num小于等于begin到容器末尾的距离

3. replace(begin,end,originalnum,replacenum)

插入迭代器?

可以使用back_inserter(容器)来获取容器对应的插入迭代器。

给插入迭代器赋值会将所赋的值作为一个新的元素插入其中。相当于调用push_back()。

可以用于算法中。

fill_n(back_inserter(vector),num,val)

拷贝

copy(begin,end,target’sbegin)

仍要注意不要越界，返回指向copy完后的一位

多数算法提供了拷贝版本，将结果写入一个新的容器而非在原容器上进行更改。

function_copy(begin,end,back_inserter(newvec),…)

重排算法

1. sort(begin,end,cmp)

2. unique(begin,end)

   unique作为算法，并不能改变容器的元素个数，不能进行删除，因此其所做的是将不重复元素放到容器的前部，并返回一个指向不重复元素尾后迭代器，但是这之后的元素并不是重复元素，是未知的。

   最后需要调用erase来真正的消除。

向算法传递函数

谓词是一个返回可用作条件的可调用的表达式，一般使用函数。

有一元谓词与二元谓词。

接受谓词的算法对输入序列的元素调用谓词。元素类型必须能转换为谓词的参数类型。

可以给sort第三个参数一个二元谓词来指定排序顺序。

stable_sort可以保证“相等”元素的顺序按照原本的顺序。

for_each

for_each(begin,end,func)

对每一个元素执行一元谓词func。

可调用对象

1. 函数
2. 函数指针
3. 重载调用运算符的类
4. lambda

lambda

可以看作一种内联函数。

$$[capture\ list](param\_list)->return\_type\{function\ body\}$$

函数体与形参表可以忽略。

捕获列表表示其中定义的局部变量(通常为空)。

→与return_type可以一起省略。

必须使用尾置返回。

当把一个变量设置为lambda类型后，就可以通过调用运算符调用它。

lambda不能设置默认参数，因此实参与形参类型应该数量相同且相符。

lambda与普通函数最大的不同就是它能够不通过形参表而通过捕获列表来将作用域外部的变量传入作为局部变量，并且可以直接使用局部static变量与全局变量（cout也算是全局的）。

通过这种方式能够防止某些算法只允许一元谓词或二元谓词。

定义lambda实际上是定义了一个新的类。并以之创建了一个类对象。auto的类型就是这个新创建类型的名字。

捕获列表

当使用值传递时，其将在创建时进行拷贝。$=name$

而使用引用拷贝，其局部变量就会根据其外部引用的变量的变化而变化。$\&name$

当捕获指针或者引用时，需要保证在调用时还存在并且正确。

可以使用隐式捕获。通过第一位使用&或者=来指定默认传递方式，将表示所有隐式传递的变量都是使用该方式来传递。其后可以增加显式捕获的变量，但是必须是采用不同方式传递的变量。

一般来说值传递的变量不在函数体中进行更改，但可以在参数列表后加上mutable来声明要改变。

而通过引用传递可以改变其引用的值。

当一个lambda包括return以外的语句时，若是不显式指定，return_type就会被判断为void类型，然后就报错了。

建议所有捕获列表为空的lambda都用函数写。

bind

通过bind也能实现lambda解决的问题。

$$auto\ newfunc=bind(func,args\_list)$$

通过调用newfunc来间接给func传入参数并调用。

newfunc所接收到的参数将会有$\_n$的别名，代表newfunc接收到的第n个参数。

通过在args_list使用$\_n$可以指定这些参数该如何传入func，并且在args_list可以直接使用变量指定传入的参数的值。

$\_n$是定义在std命名空间的placeholders空间的，placeholders定义在functional头文件中。

bind不仅可以用来转换一元谓词，也可以更改参数的顺序。

bind所做的是拷贝参数，若是要传递引用参数，则需要用ref(val)或cref(val)来获取其的一个可拷贝的引用。

迭代器

1. 插入迭代器

   1. back_inserter调用push_back
   2. front_inserter调用push_front
   3. inserter(val,iterator)，调用insert，并使迭代器指向其原本指向的

   

2. iostream迭代器

   istream_iterator，需要通过<>指定读入类型。

   初始化时可以绑定到istream对象，而当istream为空或者IO错误时，与未绑定的迭代器相等。

   

   通过++来读入下面一个值。可以将其当做一个一次性的vector容器。以未绑定的对象来作为其结尾。

   其并不是立即从流中读取值，而是可能会延迟，但是保证在解引用之前已经完成了读取。

   ostream_iterator，相当于一个cout，但是通过赋值来输出。

   

   必须绑定ostream，并且可以指定每次输出后输出一个固定的字面值。类似于python中的print的end非常相似。

   当要输出一个容器时，可以通过copy的方式。

   流迭代器对于任何定义了输入与输出运算符的类都可以使用。

3. 反向迭代器

   通过rbegin和rend来获取容器的尾迭代器与首前迭代器。

   其递增与递减是正好相反的。

   若给sort传入反向迭代器，就是逆向排序了。

   可以看作是将整个容器倒序后的正常迭代器，因此其所有的行为都将是逆序的。

   可以点运算符调用base()来将自身转换为普通迭代器。

迭代器类型

算法是对迭代器的操作，会对迭代器的权限有要求，也仅会对迭代器的权限有要求，其他都不重要，因此分为了5个类别。

编译器不会因为给算法传入错误的迭代器而报错。

算法除了传入一个迭代器范围(begin,end)外，可能会传入第二个迭代器范围，其他参数，与一个表示算法可以写入的目的位置的迭代器。

dest

算法假定向这个位置写入无论多少个元素都是安全的。

1. 若为指向容器的迭代器，会直接写入覆盖容器原本的元素。
2. 插入迭代器或ostream_iterator。

算法的命名

1. 有的算法提供重载版本，重载的版本可以传入谓词。
2. 有_if版本的算法，将比较相等改为是谓词为真。
3. 拷贝与非拷贝版本。

对list与forward_list有一些特定的成员函数代替通用算法。

不像其他的通用算法，专用于这二者的成员函数会改变容器中的结构，因此不能使用算法，只能使用成员函数。