算法

头文件<algorithm>

（STL算法部分主要由头文件,,组成。要使用STL中的算法函数必须包含头文件，对于数值算法须包含，中则定义了一些模板类，用来声明函数对象）

非变易算法

是一系列模板函数，是不改变对象内容

for_each

在区间[_First, _Last)上对每一个元素应用_Func函数。

find

区间[_First, _Last)中出找第一个与_Val的值相同的元素，返回这个元素的迭代器。否则返回_Last。

find_if

在区间[_First, _Last)内，找出能让_Pred(*it)返回true的值，返回这个迭代器。否则返回_Last。

（“#includestd::greater()(_1st, _2nd)”它是仿函数，相当用“_1st> _2nd”。）

adjacent_find

它有两个重载

（1）adjacent_find (1)

找出第一对相邻而且相同的元素，返回它们第一元素的迭代器。否则返回_Last。

（关系：“*it == *(it+1)”）（第一个重载称为默认的）

（1）adjacent_find (2)

找出第一对相邻的元素，并能使_Pred( *it, *(it+1) )为true的，返回它们第一个元素的代器。否则返回_Last。

find_first_of

(1)find_first_of (1)

在区间1中找出第一个在区间2也存在的元素it，返回it的迭代器。否则返回_Last1。

(1)find_frist_of (2)

在区间1中找出第一个与区间2中的任何一个匹配后，能让_Pred()返回true的元素，返回它的迭代器。否则返回_Last1。

cout

计算在区间[_First1, _Last1]和_Val的值相等的元素的个数，并返回个数。

cout_if

计算在区间中能让_Pred返回true的元素的个数，并返回个数。

mismatch

（1）mismatch (1)

将区间1和区间2头对齐后，找出第一个位置相同，但值不同的两个元素的对迭代器，以类pair<_InIt1, _InIt2>形式返回。否则返回_Last。

（注意！ 返回_Last时，两个区间元素个数不同的话，因为_Last所指向的是最后一个值之后，那么返回的将是最短的区间的_Last和别一个对应位置的迭代器）

（1）mismatch (2)

同样的可以用其它函数指针或者仿函数，找出第一对同位置的能让_Pred返回true的元素it，并返回it的迭代器。否则返回_Last。

equal

(1)equal (1)

如果区间1和区间2中相等，那么返回true，否则返回false。

(1)equal (2)

如果区间1和区间2中同位置的每一对元素，都能让_Pred返回true，那么返回true，否则返回false。

search

(1)查找区间1中有子集与区间人相同（是否包含区间2），如果有返回该子集的开始迭代器，否则返回_Last。

(1)查找区间1中是否有子区间与区间2大小相同，并满足_Pred的判断条件，返回该子集的开始迭代器，否则返回_Last。

变易算法（改变容器中对象元素的操作）

copy

(1)copy

将区间[_First, _Last)中的元，素从_First开始一个一个地拷贝至目的迭代器_Dest。

拷贝对象前注意要预留空间：

copy可以实现，将容器中的对象左移：

(1)copy_backward

与copy算法相反，它是从后面（_Last – 1）开始拷贝到目的迭代器_Dest。

所以它可以实现将容器中的元素右移。

(1)copy_n

指定拷贝个数_Count。

(1)copy_if

将区间内能让_Pred返回true的元素，拷贝到目的迭代器_Dest。

swap

（1）swap

swap(a, b)交换a和b的元素。

（1）swap

将区间[_First, _Last）中的元素与目的迭代器_Dest，一一对应交换。

（当然，区间[_First, _Last）一定不能比_Dest指向的容器区间大）

transform（变换）

（1）transform

将区间[_First, _Last）中的每一个元素放入_Func，然后将_Func的执行结果放入_Dest指定的区间。

（1）transform

将区间[_First, _Last）中的每个元素it1，和与_Dest指定区间中一一对应的元素it2，放入_Func（(*it1), (*it2)），然后将_Func的执行结果放入_Dest指定的区间。

replace（替换）

(1)replace

在区间[_First, _Last）中的找出_Oldal（旧值），并且将其替换为_Newval（新值）。

(1)repace_if

在区间[_First, _Last）中的找出符合判断条件_Pred的元素，替换为_Newval。

(1)replace_copy

与replace相似，不同的是replace_copy在所有替换完成之后，会把区间[_First, _Last）copy到_Dest。

(1)relace_if_copy

将区间[_First, _Last）中所有符合条件_Pred的元素替换为_Val并拷贝至_Dest。

fill（填充）

将区间[_First, _Last）填充为_Val。

（当新建一个容器时，可以用fill快速高效填充）

generate（生成）

调用_Func的结果赋值给区间[_First,

_Last）中的每个元素，但_Func不只是调用一次，而是为每个元素都调用一次。

例子：

std::vectorv(5);

std::fill(

v.begin(), v.end(), rand ); //产生5个随机娄依次赋值给v中的元素

remove（移除）

(1)remove

将区间[_First, _Last）中所有等于_Val的元素移除，移除后它会返回一个新的结束迭代器_Last2

例子：

(2)remove_if

remove_if是在remove的基础上改用_Pred为判断条件。

(3)remove_copy

从区间[_First, _Last）中移除等于_Val的值后，再copy到_Dest

unique(唯一的)

把区间[_First, _Last）中重复且相邻的元素去掉（仅保留一份），返回一个新的迭代器_Last2

测试：它只会删除相邻且相同的多余的元素，所谓的删除只是把数据左移，将要删除的数据覆盖。所以它会返回_Last2，表示新的结尾。

reverse（颠倒）

将顺序颠倒

rotate(旋转)

将[_First, _Mid)与[_Mid, _Last]交换

图示：

random_shuffle（任意放置）

若区间有元素N个，那么算法会N!种排列，而从中选择一个

默认是调用rand函数作为随机函数，也可使用自定义的函数

partition(分割)

将区间[_First, _Last）的每个元素调用_Pred，能让_Pred返回true的元素放在前面[_First, _Mid)，否则放在后面[_Mide, _Last)，并且会返回后面部分的第一个迭代器_Mid

测试：partition算法，在发现一个让_Pred返回false的元素时，它会从后面查找让_Pred返回true的元素交换。

三、排序（sorting）

sort

用less函数对区间中的元素排序，就是从小到大排序

注意需要重载operator<

partial_sort

把区间[_First, _Last)用less排序，再把[_Mid, _Last)变成乱序，结果是只有[_First,

_Mid)按less排序的

binary_search

在已经排好序的区间[_First, _Last)中查找等于_Val的元素

merge

将都排好序的两个区间合并到_Dest，返回合并后的_Last

关于集合算法

includes

判断区间1是否完全包含区间2，前提是两个区间都已经排好序的

第1个例子，区间1中只有一个13，所以不是能完全包含其中。返回true或false。

set相关算法：

set_union：

用于合并，语法：std::set_union(_First1，_Last1，_First2，_Last2，_Dest，排序行为)

set_intersection：

将两部分相同的内容放到目标位置，语法跟上个算法一样

set_difference：

在第一部分中找出跟第二部分内容重复的去除，将第一部分剩下的放到目标位置里。语法一样。

基于堆的算法（Heap operations）

make_heap

将区间变成一个堆，堆的结构采用大根堆max_heap，维持平衡二叉树

（大根堆，根都比子叶要大。相对的是小根堆，根比子叶要小）

push_heap

向堆中添加一个元素，使用方法是在已经用采用max_heap结构的区间[_First, _Last-1)之后添加一个元素*(_Last-1)，

pop_heap

把区间[_First, _Last)中的元素从大到小排序，原理：不断将区间[_First, _Last)中max_heap的根顶元素弹出来，放到区间最后面

四、泛型数值算法

accumulate（积累）

inner_product

partial_sum（局部和）

aduacent_difference（相邻元素差）

accumulate（积累）

（1）

对区间[_First, _Last)中的元素进行累加，_Val为初始值

（2）

用_Func代替加法动作，例如用内置的乘算法实现阶乘：

inner_product

（1）

对区间[_First, _Last)中的元素，在_First2指向的位置和对应的元素相乘，然后各项乘积相加。

（2）

_Func2代替第一个运算动作，_Func1代替第二个运算动作

partial_sum（局部和）

（1）

_Dest是目标位置：

红色箭头是加法运算方向，灰色是运算结果，

算法的结果是，得出一个新序列，其中每个元素值代表指定范围内该位置前所有元素之和

（2）

重载版本使用自定义操作代替加法

adjacent_difference(邻元素差)

（1）

创建一个新序列，新序列中每个新值代表当前元素与上一个元素的差

（2）

重载版本用指定二元操作计算_Func代替相邻元素的差运算