程序设计实习: 9.4 算法

STL算法分类 STL中的算法大致可以分为以下七类:

不变序列算法

变值算法

删除算法

变序算法

排序算法

有序区间算法

数值算法

算法：

大多重载的算法都是有两个版本的 用 “==” 判断元素是否相等, 或用 “<” 来比较大小 多出一个类型参数 “Pred” 和函数形参 “Pred op” : 通过表达式 “op(x,y)” 的返回值: ture/false 判断x是否 “等于” y，或者x是否 “小于” y 如下面的有两个版本的min_element: iterator min_element(iterator first, iterator last); iterator min_element(iterator first, iterator last, Pred op);

1. 不变序列算法 该类算法不会修改算法所作用的容器或对象 适用于顺序容器和关联容器 时间复杂度都是O(n)

1. 不变序列算法：

find: templateInIt find(InIt first, InIt last, const T& val); 返回区间 [first,last) 中的迭代器 i ,使得 * i == val find_if: templateInIt find_if(InIt first, InIt last, Pred pr); 返回区间 [first,last) 中的迭代器 i, 使得 pr(*i) == true

for_each: templateFun for_each(InIt first, InIt last, Fun f); 对[first, last)中的每个元素e, 执行f(e), 要求 f(e)不能改变e

count: templatesize_t count(InIt first, InIt last, const T& val); 计算[first, last) 中等于val的元素个数(x==y为true算等于) count_if: templatesize_t count_if(InIt first, InIt last, Pred pr); 计算[first, last) 中符合pr(e) == true 的元素e的个数

min_element: templateFwdIt min_element(FwdIt first, FwdIt last); 返回[first,last) 中最小元素的迭代器, 以 “<” 作比较器 最小指没有元素比它小, 而不是它比别的不同元素都小 因为即便a!= b, a<b 和b<a有可能都不成立="" max_element:="" templateFwdIt max_element(FwdIt first, FwdIt last); 返回[first,last) 中最大元素(不小于任何其他元素)的迭代器 以 “<” 作比较器

2. 变值算法 此类算法会修改源区间或目标区间元素的值 值被修改的那个区间, 不可以是属于关联容器的

transform templateOutIt transform(InIt first, InIt last, OutIt x, Unop uop); 对[first,last)中的每个迭代器I,

执行 uop( * I ); 并将结果依次放入从 x 开始的地方

要求 uop( * I ) 不得改变 * I 的值 本模板返回值是个迭代器, 即 x + (last-first) x可以和 first相等

copy 函数模板(算法)：

In-Video Quiz