c++提高篇——STL常用算法

一、常用遍历算法

算法主要是由头文件 组成。
是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、追历操作、复制、修改等等。
体积很小,只包括几个在序列上面进行简单数学运算的模板函数。
定义了—些模板类.用以声明函数对象。

一、for_each 遍历容器

样例如下，这也是我们在做项目中常用的一种算法：

//回调函数实现
void print1(int val)
{cout << val << " ";
}//仿函数实现
class print2
{
public:void operator()(int val){cout << val << " ";}
};void test08()
{vector<int> v;v.push_back(10);v.push_back(20);v.push_back(30);v.push_back(40);for_each(v.begin(), v.end(), print1);for_each(v.begin(), v.end(), print2());
}

二、transform 搬运容器到另一个容器中

transform( iterator beg1,iterator end1，iterator beg2，_func) ;
具体的案例如下：

//函数实现
void print1(int val)
{cout << val << " ";
}//仿函数实现
class Transform
{
public:int operator()(int val){return val;}
};void test08()
{vector<int> v;v.push_back(10);v.push_back(20);v.push_back(30);v.push_back(40);vector<int> v2;v2.resize(v.size());//目标容器需要提前开辟空间transform(v.begin(), v.end(), v2.begin(), Transform());for_each(v.begin(), v.end(), print1);

二、常用查找算法

下面为函数实现的接口：
find 查找元素
find_if 按条件查找元素
adjacent_find 查找相邻重复元素
binary _search 二分查找法
count 统计元素个数
count_if 按条件统计元素个数

一、find

查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()
函数原型：
find(iterator beg, iterator end, value);
按值查找元素，找到返回指定位位置迭代器，找不到返回结束迭代器位置
beg 开始迭代器
end结束迭代器
value查找的元素
案例一：

	vector<int> v;v.push_back(10);v.push_back(20);v.push_back(30);v.push_back(40);vector<int>::iterator pos = find(v.begin(), v.end(), 10);cout << *pos << endl; 

案例二：

class Person
{
public:Person(string name, int age){this->M_Age = age;this->M_Name = name;	}bool operator == (const Person & p){if (this->M_Name == p.M_Name && this->M_Age == p.M_Age){return true;}else{return false;}};string M_Name;int M_Age;};void test08()
{Person p1("张三", 10);Person p2("里斯", 20);Person p3("王五", 30);Person p4("找刘", 40);vector<Person> v;v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);vector<Person>::iterator pos = find(v.begin(), v.end(), p2);cout << (*pos).M_Age << endl;
}

二、find_if

find_if(iterator beg, iterator end，_pred);
按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置beg 开始迭代器
end结束迭代器
_Pred函数或者谓词（返回bool类型的仿函数)
具体案例如下：

//创建一个人类
class Person
{
public:Person(string name, int age){this->M_Age = age;this->M_Name = name;	}string M_Name;int M_Age;};//创建一个仿函数
class MyCompare
{
public:bool operator()(Person &p){return p.M_Age > 10;	}
};void test08()
{//实例化人Person p1("张三", 10);Person p2("里斯", 20);Person p3("王五", 30);Person p4("找刘", 40);//放入容器vector<Person> v;v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);//查找符合条件的人vector<Person>::iterator pos = find_if(v.begin(), v.end(), MyCompare());//如果存在则打印if (pos != v.end()){cout << (*pos).M_Age << endl;}	//不存在else{cout << "不存在" << endl;}
}

三、adjacent_find

查找相邻重复元素
adjacent_find(iterator beg, iterator end) ;
查找相邻重复元素,返回相邻元素的第一个位置的迭代器
beg开始迭代器
end结束迭代器
优于语法比较简单，这里就不在进行演示了。

四、binary_search

查找指定元素是否存在
bool binary_search(iterator beg， iterator end, value);
查找指定的元素，查到返回true否则false
beg开始迭代器
end结束迭代器
value查找的元素
**注意在无序序列中不可用！**如果序列是无序的，则结果未知。也许对也许错。

五、count

统计元素个数
count(iterator beg,iterator end, value);统计元素出现次数
beg 开始迭代器
end结束迭代器
value 统计的元素
注意在统计自定义数据类型时，要重载==号才可以进行对比，且在传参数的时候要用const类型的数据类型。

六、count_if

按条件统计元素个数
count_if(iterator beg，iterator end，_Pred);
beg开始迭代器
end结束迭代器
_Pred谓词
具体的语法与find_if相似，请参照上文

三、常用排序算法

sort 对容器内元素进行排序
random_shuffle 洗牌 指定范围内的元素随机调整次序
merge 容器元素合并，并存储到另一容器中
reverse 反转指定范围的元素

一、sort

对元素进行排序
sort(iterator beg, iterator end，_Pred ) ;
按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
beg开始迭代器
end 结束迭代器
_Pred 谓词

sort(v.begin(), v.end(), greaner<int>())

这里语法例子就不在列举，有兴趣的伙伴可以参考之前的内容： 第四部分

二、random_shuffle

洗牌: 指定范围内的元素随机调整次序
randomn_shuffle( iterator beg, iterator end);
beg开始迭代器
end 结束迭代器
样例过于简单就不再写样例，有兴趣的小伙伴可以自行练习。
注意在使用前要加一个随机数种子，才能实现每次运行都是随机的状态：

srand((unsigned int)time(NULL));

三、 merage

两个容器元素合并，并存储到另一个容器中
merge(iterator beg1，iterator end1，iterator beg2，iterator end2，iterator dest);
beg1容器1开始迭代器
end1容器1结束迭代器
beg2容器2开始迭代器
end2客器2结束迭代器
dest目标容器开始迭代器
合并时两个容器必须是有序的，合并之后的序列仍然是有序的！
注意在合并之前要给目标容器提前开辟空间，否则会抛出异常！

vTarget.resize(v1.size() + v2.size());

四、reverse

将容器内元素进行反转
reverse(iterator beg,iterator end);
beg 开始迭代器
end结束迭代器
此函数过于简单就不在描述了

四、常用拷贝和替换算法

copy 容器内指定范围的元素拷贝到另一容器中
replace 将容器内指定范围的旧元素修改为新元素
replace_if 容器内指定范围满足条件的元素替换为新元素
swap 互换两个容器的元素

一、copy

copy (iterator beg,iterator end, iterator dest );
按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位詈
beg开始迭代器
end 结束迭代器
dest目标起始迭代器
注意在copy之前要给目标容器提前开辟空间，否则会抛出异常！

二、replace

replace(iterator beg,iterator end， old value,new value);
beg 开始迭代器
end结束迭代器
old value 旧元素
new value新元素

三、replace_if

将区间内满足条件的元素,替换成指定元察
replace_if(iterator beg，iterator end，_pred，new value);
beg 开始迭代器
end结束迭代器
_pred 谓词
new value替换的新元素

四、swap

互换两个容器的元素
Swap(container c1，container c2); 互换两个容器的元素
c1 容器1
c2 容器2
注意一定是同一个类型的容器进行交换，否则会抛出异常！

五、常用算术生成算法

算术生成算法属于小型算法，使用时包含的头文件为#include 算法简介:
accumulate 计算容器元素累计总和
fill 向容器中添加元素

一、accumulate

计算区间内容器元素累计总和
accumulate(iterator beg, iterator end , value);
beg开始迭代器
end结束迭代器
value 起始值：一般为零

二、fill

向容器中添加元素
fill(iterator beg, iterator end, value) ;
beg 开始迭代器
end结束迭代器
value填充的值

六、常用集合算法

set_intersection 求两个容器的交集
set_union 求两个容器的并集
set_difference 求两个容器的差集

一、set_intersection

set_intersection(iterator beg1，iterator end1，iterator beg2，iterator end2，iterator dest);
beg1容器1开始迭代器
end1容器1结束迭代器
beg2容器2开始迭代器
end2容眙2结束迭代器
dest目标容器开始迭代器
注意:两个集合必须是有序序列！
特殊情况下，两个集合最大的交集是其中最小集合的全部。

v.reszie(min(v1.size(), v2.size()))

二、set_union

set_union(iterator beg1，iterator end1，iterator beg2，iterator end2，iterator dest);
beg1容器1开始迭代器
end1容器1结束迭代器
beg2容器2开始迭代器
end2容器2结束迭代器
dest目标容器开始迭代器
注意:两个集合必须是有序序列!
特殊情况下，两个集合最大的并集是两个集合之和。
set_union返回值既是并集中最后一个元素的位置

三、set_difference

set_difference( iterator beg1，iterator end1，iterator beg2，iterator end2，iterator dest);
beg1容器1开始迭代器
end1容器1结束迭代器
beg2容器2开始迭代器
end2容器2结束迭代器
dest目标容器开始迭代器
注意:两个集合必须是有序序列！
特殊情况下，两个集合最大的差集是两个集合最大的一个。