概述：
- 算法主要是由头文件
组成 - 是所有STL头文件中最大的一个，范围涉及到比较，交换，查找，遍历操作，复制，修改等等
体积很小，只包括几个在序列上面进行简单数学运算的模板函数 定义了一些模板类，用以声明函数对象
学习目标：掌握常用的遍历算法
算法简介：
for_each //遍历容器 transform //搬运容器到另一个容器中1.1 for_each
功能描述：实现遍历容器
函数原型：
for_each(iterator beg,iterator end,_func); //遍历算法 遍历容器元素 //beg开始迭代器 //end结束迭代器 //_func函数或者函数对象
#include#include #include #include #include using namespace std; //普通函数 void print01(int val) { cout << val << " "; } //函数对象 class print02 { public: void operator()(int val) { cout << val << " "; } }; void test01() { vector v; v.push_back(10); v.push_back(20); v.push_back(30); v.push_back(40); //遍历算法 for_each(v.begin(), v.end(),print01); cout << endl; for_each(v.begin(), v.end(), print02()); cout << endl; } int main() { test01(); system("pause"); return 0; }
总结：for_each是在实际开发中最常用的遍历算法，需要熟练掌握
1.2 transform功能描述：搬运容器到另一个容器中
函数原型：
transform(iterator beg1,iterator end1,iterator beg2,_func); //beg1 源容器开始迭代器 //endl 源容器结束迭代器 //beg2 目标容器开始迭代器 //_func 函数或者函数对象（取出的对象进行处理后再放进目标容器中）
#include#include #include #include #include using namespace std; class Transform { public: int operator()(int val) { //将值搬运到目标容器中，当然也可以进行运算后进行搬运，例如return val+100； return val; } }; class MyPrint { public: void operator()(int val) { cout << val << " "; } }; void test01() { vector v; v.push_back(10); v.push_back(20); v.push_back(30); v.push_back(40); vector v2; //还需要对目标空间进行开辟，因为塞不进去，这样会会报错 v2.resize(v.size()); //搬运 transform(v.begin(), v.end(), v2.begin(), Transform()); //遍历 for_each(v2.begin(),v2.end(),MyPrint()); cout << endl; //仿函数是可以直接使用的，但是需要创建一个对象 Transform tr; cout << tr(2) << endl; } int main() { test01(); system("pause"); return 0; }
总结：搬运的目标容器必须要提前开辟空间，否则无法正常搬运
2 常用查找算法学习目标：掌握常用的查找算法
算法简介：
find //查找元素 find_if //按条件查找元素 adjacent_find //查找相邻重复元素 binary_search //二分查找法 count //统计元素个数 count_if //按条件统计元素个数2.1 find
功能描述：查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()
函数原型：
find(iterator beg,iterator end,value) //按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 //beg开始迭代器 //end结束迭代器 //value查找的元素
#include#include #include #include #include using namespace std; //查找内置的数据类型 void test01() { vector v; for (int i = 0; i < 10; i++) { v.push_back(i); } vector ::iterator it = find(v.begin(), v.end(), 5); if (it == v.end()) { cout << "未找到元素" << endl; } else { cout << "找到元素：" << (*it) << endl; } } class Person { public: Person(string name, int age) { this->m_Name = name; this->m_Age = age; } //不重载==运算符，就无法判断Person类对象是否相等 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 test02() { vector v; Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); Person pp("aaa",10); vector ::iterator it = find(v.begin(), v.end(), pp); if (it == v.end()) //我们可以想像一下，两个Peroson对象怎么才能判断两个相同或者不相同呢，所以需要重载==运算符 { cout << "未找到元素" << endl; } else { cout << "找到元素 姓名：" << (*it).m_Name << "年龄：" << (*it).m_Age << endl; } } int main() { test01(); test02(); system("pause"); return 0; }
总结：find可以再容器中找到指定的元素，返回值是迭代器
2.2 find_if功能描述：按条件查找元素
函数原型：
find_if(iterator beg,iterator end,_Pred) //按仿函数查找元素，找到返回指定位置迭代器，找不到返回结束迭代器 //beg开始迭代器 //end结束迭代器 //_Pred函数或者谓词（返回bool类型的仿函数）
#include#include #include #include using namespace std; class GreaterFive { public: bool operator()(int val) { return val > 5; } }; //查找内置的数据类型 void test01() { vector v; for (int i = 0; i < 10; i++) { v.push_back(i); } vector ::iterator pos = v.begin(); //找到大于5的数 for (vector ::iterator it = v.begin(); it != v.end(); it++) { if (pos != v.end()) { //find_if为条件查找，find为值查找 pos = find_if(pos, v.end(), GreaterFive()); cout << *pos << endl; pos++; } else { return; } } } class Person { public: Person(string name, int age) { this->m_Name = name; this->m_Age = age; } //不重载==运算符，就无法判断Person类对象是否相等 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; }; class Greater20 { public: bool operator()(Person& p) { return p.m_Age > 20; } }; //查找自定义的数据类型 void test02() { vector v; Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); vector ::iterator it = find_if(v.begin(), v.end(), Greater20()); if (it == v.end()) //我们可以想像一下，两个Peroson对象怎么才能判断两个相同或者不相同呢，所以需要重载==运算符 { cout << "未找到元素" << endl; } else { cout << "找到元素 姓名：" << (*it).m_Name << "年龄：" << (*it).m_Age << endl; } } int main() { test01(); test02(); system("pause"); return 0; }
总结：find_if的返回的是迭代器
2.3 adjacent_find功能描述：查找相邻重复元素
函数原型：
adjacent_find(iterator beg,iterator end) //查找相邻重复元素，返回相邻元素的第一个位置的迭代器 //beg开始迭代器 //end结束迭代器
#include2.4 binary_search#include #include #include using namespace std; void test01() { vector v; v.push_back(0); v.push_back(1); v.push_back(1); v.push_back(2); v.push_back(3); //查找相邻元素算法，找到返回相邻第一个的迭代器，否则返回结束迭代器 vector ::iterator pos = adjacent_find(v.begin(), v.end()); if (pos == v.end()) { cout << "未找到相邻元素" << endl; } else { cout << "找到相邻元素" << *pos << endl; } } int main() { test01(); system("pause"); return 0; }
功能描述：查找指定元素是否存在
函数原型：
bool binary_search(iterator beg,iterator end,value); //查找指定的元素，查到返回true，否则false //注意：在无序序列中不适用 //beg开始迭代器 //end迭代器 //value查找的元素
#include2.5 count#include #include #include using namespace std; void test01() { vector v; for (int i = 0; i < 10; i++) { v.push_back(i); } //二分查找法，只能是有序序列 bool ret = binary_search(v.begin(), v.end(),7); if (ret) { cout << "找到元素" << endl; } else { cout << "未找到元素" << endl; } } int main() { test01(); system("pause"); return 0; }
功能描述：统计元素个数
函数原理：
int count(iterator beg,iterator end,value) //统计元素出现次数 //beg开始迭代器 //end结束迭代器 //value统计的元素
#include#include #include #include using namespace std; //查找内置的数据类型 void test01() { vector v; for (int i = 0; i < 10; i++) { v.push_back(i); } int num = count(v.begin(), v.end(), 2); cout << "元素的个数为：" << num << endl; } class Person { public: Person(string name, int age) { this->m_Name = name; this->m_Age = age; } //不重载==运算符，就无法判断Person类对象年龄是否相等 bool operator==(const Person& p) { if (this->m_Age == p.m_Age) { return true; } else { return false; } } string m_Name; int m_Age; }; //查找自定义的数据类型 void test02() { vector v; Person p1("张飞", 30); Person p2("关羽", 30); Person p3("刘备", 30); Person p4("曹操", 40); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); Person p("诸葛亮", 30); int num = count(v.begin(), v.end(), p); cout << "和诸葛亮同岁的人数为：" << num << endl; } int main() { test01(); test02(); system("pause"); return 0; }
总结：统计自定义的数据类型个数，需要重载==号
2.6 count_if功能描述：按条件统计元素个数
函数原型：
int count_if(iterator beg,iterator end,_Pred) //统计元素出现次数 //beg开始迭代器 //end结束迭代器 //_Pred谓词
#include3 常用排序算法#include #include #include using namespace std; class GreaterFive { public: bool operator()(int val) { return val > 5; } }; //查找内置的数据类型 void test01() { vector v; for (int i = 0; i < 10; i++) { v.push_back(i); } //找到大于5的数 int num = count_if(v.begin(),v.end(), GreaterFive()); cout << "大于5的个数为：" << num << endl; } class Person { public: Person(string name, int age) { this->m_Name = name; this->m_Age = age; } string m_Name; int m_Age; }; class Greater20 { public: bool operator()(Person& p) { return p.m_Age > 20; } }; //查找自定义的数据类型 void test02() { vector v; Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); //找年龄大于20的人的个数 int num = count_if(v.begin(), v.end(), Greater20()); cout << "年龄大于20的个数为：" << num << endl; } int main() { test01(); test02(); system("pause"); return 0; }
学习目标：掌握常用的排序算法
算法简介：
sort //对容器内的元素进行排序 random_shuffle //洗牌 指定范围内的元素随机调整次序 merge //容器元素合并，并存储到另一个容器中 reverse //反转指定范围的元素3.1 sort
功能描述：对容器内元素进行排序
函数原理：
sort(iterator beg,iterator end,_Pred); //按值查找元素，找到返回指定位置的迭代器，找不到返回迭代器结束位置 //beg开始迭代器 //end结束迭代器 //_Pred谓词，不写从小到大排序
#include3.2 random_shuffle#include #include #include #include using namespace std; void MyPrint(int val) { cout << val << " "; } //查找内置的数据类型 void test01() { vector v; v.push_back(10); v.push_back(30); v.push_back(20); v.push_back(40); //默认排序从小到大 sort(v.begin(), v.end()); for_each(v.begin(), v.end(), MyPrint); cout << endl; //改变排序规则，从大到小 sort(v.begin(), v.end(), greater ()); for_each(v.begin(), v.end(), MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
功能描述：洗牌 指定范围内的元素随机调整次序
函数原型：
random_shuffle(iterator beg,iterator end); //指定范围内的元素随机调整次序 //beg开始迭代器 //end结束迭代器
#include#include #include #include #include using namespace std; void MyPrint(int val) { cout << val << " "; } //查找内置的数据类型 void test01() { vector v; for (int i = 0; i < 10; i++) { v.push_back(i); } //洗牌算法，打乱次序 random_shuffle(v.begin(), v.end()); for_each(v.begin(),v.end(),MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
总结：random_shuffle洗牌算法比较实用，实用时记得加随机数种子
3.3 merge功能描述：两个容器元素合并，并存储到另一个容器中
函数原型：
merge(iterator beg1,iterator end1,iterator beg2,iterator end1,iterator dest) //容器元素合并，并存储到另一个容器中 //注意:两个容器必须是有序的 //beg1 容器1开始迭代器 //end1 容器1结束迭代器 //beg2 容器2开始迭代器 //end2 容器2结束迭代器 //dest 目标容器开始迭代器
#include3.4 reverse#include #include #include #include using namespace std; void MyPrint(int val) { cout << val << " "; } //查找内置的数据类型 void test01() { vector v1; vector v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i+1); } //目标容器 vector vTarger; //目标容器必须开辟空间才能放进去数据 vTarger.resize(v1.size()+v2.size()); //合并算法，两个容器必须是有序序列才可以合并 merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarger.begin()); for_each(vTarger.begin(), vTarger.end(),MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
功能描述：将容器内的元素进行反转
函数原型：
reverse(iterator beg,iterator end) //反转指定范围的元素 //beg开始迭代器 //end结束迭代器
#include#include #include #include #include using namespace std; void MyPrint(int val) { cout << val << " "; } //查找内置的数据类型 void test01() { vector v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } //反转算法 reverse(v1.begin(),v1.end()); for_each(v1.begin(), v1.end(),MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
总结：reverse反转区间内元素，面试题可能涉及到
4 常用的拷贝和替换算法学习目标：掌握常用的拷贝和替换算法
算法简介：
copy //容器内指定范围的元素拷贝到另一个容器中 replace //将容器内指定范围的旧元素修改为新元素 replace_if //容器内指定范围满足条件的元素替换为新元素 swap //互换两个容器的元素4.1 copy
功能描述：容器内指定范围的元素拷贝到另一个容器中
函数原型：
copy(iterator beg,iterator end,iterator dest) //将一个容器里面的元素拷贝到另一个容器中 //beg开始迭代器 //end结束迭代器 //dest目标起始迭代器
#include#include #include #include #include using namespace std; void MyPrint(int val) { cout << val << " "; } //查找内置的数据类型 void test01() { vector v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } //copy算法 vector v2; v2.resize(v1.size()); copy(v1.begin(), v1.end(), v2.begin()); for_each(v2.begin(),v2.end(),MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
总结:copy算法的目标容器需要提前开辟空间
4.2 replace功能描述：将容器内指定范围的旧元素改为新元素
函数原型：
replace(iterator beg,iterator end,oldvalue,newvalue) //将区间内旧元素替换为新元素 //beg开始迭代器 //end结束迭代器 //oldvalue旧元素 //newvalue新元素
#include4.3 replace_if#include #include #include #include using namespace std; void MyPrint(int val) { cout << val << " "; } //查找内置的数据类型 void test01() { vector v1; v1.push_back(100); v1.push_back(10); v1.push_back(100); v1.push_back(10); v1.push_back(100); //replace算法 //将容器里面的100替换为10 replace(v1.begin(), v1.end(), 100, 10); for_each(v1.begin(),v1.end(),MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
功能描述：将区间内满足条件的元素，替换成指定元素
函数原型：
replace_if(iterator beg,iterator end,_Pred,newvalue) //按条件替换元素，满足条件的替换成指定元素 //beg开始迭代器 //end结束迭代器 //_Pred谓词 //newvalue替换的新元素
#include#include #include #include #include using namespace std; //仿函数 class Greater10 { public: bool operator()(int val) { return val > 10; } }; void MyPrint(int val) { cout << val << " "; } //查找内置的数据类型 void test01() { vector v1; v1.push_back(100); v1.push_back(10); v1.push_back(100); v1.push_back(10); v1.push_back(100); //replace_if算法 //将容器里面的大于10的数替换为10 replace_if(v1.begin(), v1.end(), Greater10(), 10); for_each(v1.begin(),v1.end(),MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
总结：replace_if按条件查找，可以利用仿函数灵活筛选满足的条件
4.4 swap功能描述：互换两个容器的元素
函数原型;
swap(container c1,container c2); //互换两个容器的元素 //c1容器1 //c2容器2
#include5 常用算术生成算法#include #include #include #include using namespace std; void MyPrint(int val) { cout << val << " "; } //查找内置的数据类型 void test01() { vector v1; v1.push_back(10); v1.push_back(10); v1.push_back(10); v1.push_back(10); v1.push_back(10); vector v2; v2.push_back(20); v2.push_back(20); v2.push_back(20); v2.push_back(20); v2.push_back(20); //swap算法 swap(v1,v2); for_each(v1.begin(),v1.end(),MyPrint); cout << endl; for_each(v2.begin(), v2.end(), MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
学习目标：掌握常用的算术生成算法
注意：算术生成算法属于小型算法，使用时包含的头文件为#include
算法简介：
accumluate //计算容器元素累计总和 fill //向容器中添加元素5.1 accumulate
功能描述：计算区间内容器元素累计总和
函数原型：
accumulate(iterator beg,iterator end,value) //计算容器元素的累计和 //beg开始迭代器 //end结束迭代器 //value起始值
#include5.2 fill#include #include #include using namespace std; void test01() { vector v1; v1.push_back(10); v1.push_back(10); v1.push_back(10); v1.push_back(10); v1.push_back(10); //accumulate算法 //第三个参数时元素总和再加上的值 int total = accumulate(v1.begin(), v1.end(), 0); cout << total << endl; } int main() { test01(); system("pause"); return 0; }
功能描述：想容器中填充指定的元素
函数原型：
fill(iterator beg,iterator end,value) //向容器中填充元素 //beg开始迭代器 //end结束迭代器 //value填充的值
#include6 常用集合算法#include #include #include #include using namespace std; void MyPrint(int val) { cout << val << " "; } void test01() { vector v1; //现在容器里面的数据都是0 v1.resize(10); //fill算法 //后期重新填充数据 fill(v1.begin(), v1.end(), 100); for_each(v1.begin(), v1.end(), MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
学习目标：掌握常用的集合算法
算法简介：
set_intersection //求两个容器的交集 set_union //求两个容器的并集 set_difference //求两个容器的差集6.1 set_intersection
功能描述：求两人容器的交集
函数原型：
set_intersection//求两个容器的交集 //注意：两个集合必须是有序序列 //beg1 容器1开始迭代器 //end1 容器1结束迭代器 //beg2 容器2开始迭代器 //end2 容器2结束迭代器 //dest 目标容器开始迭代器
#include#include #include #include #include using namespace std; void MyPrint(int val) { cout << val << " "; } void test01() { vector v1; vector v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i+5); } //set_intersection算法 //获取交集，这个算法会返回最后一个交集的迭代器 vector vTarget; //开辟空间，开辟v1和v2之间小的空间大小，虽然可能还是太多了（被0填充），但是我们有最后一个交集的迭代器 vTarget.resize(min(v1.size(),v2.size())); vector ::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin()); for_each(vTarget.begin(), itEnd, MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
总结：
- 求交集的两个集合必须是有序序列
- 目标容器开辟空间需要从两个容器中取小值
- set_intersection返回值即是交集中最后一个元素的位置
功能描述：求两个集合和并集
函数原理：
set_union//求两个容器的并集 //注意：两个集合必须是有序序列 //beg1 容器1开始迭代器 //end1 容器1结束迭代器 //beg2 容器2开始迭代器 //end2 容器2结束迭代器 //dest 目标容器开始迭代器
#include6.3 set_difference#include #include #include #include using namespace std; void MyPrint(int val) { cout << val << " "; } void test01() { vector v1; vector v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i+5); } //set_union算法 //获取并集，这个算法会返回最后一个并集的迭代器 vector vTarget; //开辟空间，开辟v1加上v2的大小空间 vTarget.resize(v1.size()+v2.size()); vector ::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin()); for_each(vTarget.begin(), itEnd, MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
功能描述：求两个集合的差集
函数原型：
set_difference//求两个容器的差集 //注意：两个集合必须是有序序列 //beg1 容器1开始迭代器 //end1 容器1结束迭代器 //beg2 容器2开始迭代器 //end2 容器2结束迭代器 //dest 目标容器开始迭代器
#include#include #include #include #include using namespace std; void MyPrint(int val) { cout << val << " "; } void test01() { vector v1; vector v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i+5); } //set_difference算法 //获取差集，这个算法会返回最后一个差集的迭代器 vector vTarget; //开辟空间，开辟最大的一个空间即可 vTarget.resize(max(v1.size(),v2.size())); vector ::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin()); cout << "v1和v2的差集为：" << endl; for_each(vTarget.begin(), itEnd, MyPrint); cout << endl; itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin()); cout << "v2和v1的差集为：" << endl; for_each(vTarget.begin(), itEnd, MyPrint); cout << endl; } int main() { test01(); system("pause"); return 0; }
总结:
- 求差集的两个集合必须为有序序列
- 目标容器开辟空间需要从两个容器取较大值
- set_difference返回值既是差集最后一个元素的位置
