C++学习笔记--泛型算法

标准库给容器定义了一些基本的操作，还定义了一组泛型算法，称它们为算法，是因为它们实现了一些经典算法的公共接口，如排序和搜索，称它们是泛型的，是因为它们可以用于不同类型的元素和多种容器类型，甚至包括内置数组类型。 泛型算法通过迭代器来进行相应的操作，根据操作的不同，可以将泛型算法分为只读算法（如查找、比较）、写容器元素算法（如拷贝）、重排容器元素的算法（如排序、剔重）、以及随机数生成算法等。       迭代器使得泛型算法不依赖于容器，但算法依赖于元素类型的操作。如查找算法需要比较当前元素是否等于要查找的元素，这时需要==操作符，如果该元素类型定义了==操作符，则直接使用元素类型定义的版本，否则需要用户自行定义类似操作符功能的函数，然后将该函数作为参数传递给泛型算法的接口。排序算法需要<操作符，如果元素类型没有定义<操作符，那么也是需要定义相应的函数。在某些使用自定义函数不能满足要求的场合，可以使用C++11新增的lambda表达式，参考《C++ Primer》第5版 p345。

      如果使用容器定义的操作或者增加少量的代码就能满足某些要求，那么尽量不要使用泛型算法，所有的泛型算法见《C++ Primer》第5版 p770。下面仅列出比较实用，但自己实现有些麻烦的泛型算法。

（1）二分搜索算法 binary_search(beg,end,val) binary_search(beg,end,val,comp)    comp是自定义的用于比较两个元素类型是否相等的函数 （2）排序算法 sort(beg,end) stable_sort(beg,end) sort(beg,end,comp) stable_sort(beg,end,comp)        comp是自定义的用于比较两个元素类型大小的函数 （3）重排算法 unique(beg,end)                    要先进行sort使得重复元素相邻，然后才可以使用此算法对相邻的重复元素，                                 通过覆盖它们来进行“删除”，参考《C++ Primer》第5版 p343 unique(beg,end,binaryPred)        binaryPred是自定义的用于比较相邻两个元素类型是否相等的函数 random_shuffle(beg,end)            混洗输入序列中的元素 random_shuffle(beg,end,rand)    生成(0,rand)区间内的服从均匀分布的随机整数 shuffle(beg,end,Uniform_rand)    Uniform_rand必须满足均匀分布随机生成器的要求（这好像是一个可调用的函数名？） （4）有序序列的集合算法 注意，使用下面这些算法要求序列已经是有序的。这些算法提供了类似集合操作的行为，适用于普通顺序容器，但是标准容器set反而没有提供这些行为。参考《C++ Primer》第5版 p779。 includes(beg,end,beg2,end2) includes(beg,end,beg2,end2,comp) set_union(beg,end,beg2,end2,dest) set_union(beg,end,beg2,end2,dest,comp) set_intersection(beg,end,beg2,end2,dest) set_intersection(beg,end,beg2,end2,dest,comp) set_difference(beg,end,beg2,end2,dest) set_difference(beg,end,beg2,end2,dest,comp) set_symmetric_difference(beg,end,beg2,end2,dest) set_symmetric_difference(beg,end,beg2,end2,dest,comp) （5）最小值和最大值 有18个算法，此处不一一列出，参考《C++ Primer》第5版 p779。 （6）数值算法 上面提到的算法都定义在<algorithm>中，数值算法定义在<numeric>中 accumulate(beg,end,init)            对序列中所有值进行累加求和，初始值为init，使用元素类型的+运算符 accumulate(beg,end,init,binaryPred)    使用指定的二元操作binaryPred inner_product(beg1,end1,beg2,init)    对两个序列求内积，即对应元素的积的和，和的初始值为init inner_product(beg1,end1,beg2,init,binop1,binop2)    使用binop1代替加法,binop2代替乘法 （7）随机数 很少用到，不一一列出，参考《C++ Primer》第5版 p781。