00 概述

算法主要是由头文件< algorithm> < functional> < numeric>组成；

< algorithm>是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历、复制、修改等待；< functional>体积很小，只包括几个在序列上面进行简单数学运算的模板函数；< numeric>定义了一些模板类，用以声明函数对象；

01 遍历算法

for_each //遍历容器transform //搬运容器到另一个容器中

for_each 遍历容器

#include<iostream> #include<vector> #include<algorithm> using namespace std; //普通函数 void print1(int v) { cout << v<<" "; } //仿函数 class print2 { public: void operator()(int v) { cout << v << " "; } }; void test() { vector<int>v; v.push_back(343); v.push_back(566); v.push_back(23); v.push_back(54); //普通函数实现遍历操作 把函数名放进来 for_each(v.begin(), v.end(), print1); cout << endl; //仿函数实现遍历操作 把函数对象放进来 for_each(v.begin(), v.end(), print2()); cout << endl; } int main() { test(); system("pause"); return 0; }

for_each在实际开发中是最常用的遍历算法；

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

transform(iterator beg1,iterator end1,iterator beg2,_func); //beg1 原容器的开始迭代器 //end1 原容器的结束迭代器 //beg2 目标容器的开始迭代器 // _func 函数或函数对象，搬运过程器件可以对数据进行一些运算

#include<iostream> #include<vector> #include<algorithm> using namespace std; class Transform { public: int operator()(int v) { return v+100; } }; class Print { public: void operator()(int v) { cout << v << " "; } }; void test() { vector<int>v; v.push_back(343); v.push_back(566); v.push_back(23); v.push_back(54); vector<int>v2; //目标容器需要提前开启空间 v2.resize(v.size()); //搬运 transform(v.begin(), v.end(), v2.begin(), Transform()); for_each(v2.begin(), v2.end(), Print()); cout << endl; } int main() { test(); system("pause"); return 0; }

搬运的目标容器必须要提前开辟空间，否则无法正常搬运；

02 查找算法

find //查找元素find_if //按条件查找元素adjacent_find //查找相邻重复元素binary_find //二分查找count //统计元素个数count_if //按条件统计元素个数

find 查找指定元素

查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()；

find(iterator beg,iterator end,value); //按值查找，value为要查找的元素； 1）查找内置的数据类型

#include<iostream> #include<vector> #include<algorithm> using namespace std; void test() { vector<int>v; v.push_back(343); v.push_back(566); v.push_back(23); v.push_back(54); //查找内置的数据类型 无论能不能找到 都会返回一个迭代器 vector<int>::iterator it=find (v.begin(), v.end(), 23); if (it == v.end()) { cout << "没有找到" << endl; } else { cout << "找到：" << *it << endl; } } int main() { test(); system("pause"); return 0; }

2）查找自定义的数据类型

#include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; class Person { public: Person(string name, int age) { this->m_Age = age; this->m_Name = name; } //重载==号 让底层知道如何对比Person类型 bool operator==(const Person&p) { if (this->m_Age == p.m_Age&&this->m_Name == p.m_Name) { return true; } else { return false; } } string m_Name; int m_Age; }; void test() { vector<Person>v; Person p1("liu", 20); Person p2("gao", 22); Person p3("wang", 26); Person p4("zheng", 18); Person p5("zhou", 29); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); v.push_back(p5); //需要重载==号 返回值是迭代器 vector<Person>::iterator it=find (v.begin(), v.end(), p2); if (it == v.end()) { cout << "没有找到" << endl; } else { cout << "找到：" << "姓名：" << it->m_Name << " 年龄：" << it->m_Age << endl; } } int main() { test(); system("pause"); return 0; }

find_if 条件查找

find_if(iterator beg,iterator end, _pred); //按条件查找元素 // _pred函数或者谓词（返回bool类型的仿函数） 1）内置数据类型 #include<iostream> #include"vector" using namespace std; //find_if class GreaterFive { public: bool operator()(int val) { return val > 5;//>5返回真 } }; void test() { vector<int>v; for(int i = 0; i < 10; i++) { v.push_back(i); } vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive()); if (it == v.end()) { cout << "没有找到" << endl; } else { cout << "找到大于5的数字为：" << *it << endl; } } int main() { test(); system("pause"); return 0; }

2）自定义数据类型 查找一个年龄大于20岁的人

#include<iostream> #include"vector" #include<string> using namespace std; //find_if 查找自定义的数据类型 class Person { public: Person(string name, int age) { this->m_Age = age; this->m_Name = name; } string m_Name; int m_Age; }; //仿函数 class Greater20 { public: bool operator()(Person& p)//只要年龄大于20就返回 { return p.m_Age > 20; } }; void test() { vector<Person>v; Person p1("yutong", 26); Person p2("runqi", 19); Person p3("xiaoxiong", 19); Person p4("keke", 19); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20()); if (it == v.end()) { cout << "没有找到" << endl; } else { cout << "找到姓名：" << it->m_Name << " 年龄：" << it->m_Age << endl; } } int main() { test(); system("pause"); return 0; }

adjacent_find 查找相邻重复元素

adjacent_find (iterator beg, iterator end); //查找相邻重复元素，返回相邻元素的第一个位置的迭代器 #include<iostream> #include"vector" #include<algorithm> using namespace std; void test() { vector<int>v; v.push_back(10); v.push_back(5); v.push_back(8); v.push_back(8); v.push_back(10); v.push_back(2); v.push_back(22); vector<int>::iterator it = adjacent_find(v.begin(), v.end());//迭代器接收 if (it == v.end()) { cout << "未找到相邻重复元素" << endl; } else { cout << "找到相邻重复元素" << *it << endl; } } int main() { test(); system("pause"); return 0; }

binary_search 二分查找 查找指定元素是否存在

bool binary_search(iterator beg, iterator end, value); //查找指定元素是否存在，查到返回ture，否则返回false //只能查找有序序列 #include<iostream> #include<vector> #include<algorithm> using namespace std; void test() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } bool m= binary_search(v.begin(), v.end(),6);//返回bool类型 if (m) { cout << "找到" << endl; } else { cout << "未找到"<< endl; } } int main() { test(); system("pause"); return 0; }

count 统计元素个数

count(iterator beg, iterator end, value); //统计元素出现个数 1）统计内置的数据类型 #include<iostream> #include<vector> #include<algorithm> using namespace std; void test() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(6); } int m= count(v.begin(), v.end(),6); cout << "出现次数：" << m << endl; } int main() { test(); system("pause"); return 0; }

2）统计自定义的数据类型 需要在类中 重载等号才能查找，要不然编译器不知道怎么查找

#include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; class Person { public: Person(string name, int age) { this->m_Age = age; this->m_Name = name; } string m_Name; int m_Age; //重载== bool operator==(const Person& p)//底层要求加const { if (this->m_Age == p.m_Age)//年龄相等即可 return true; else return false; } }; void test() { vector<Person>v; Person p1("yutong", 26); Person p2("runqi", 19); Person p3("xiaoxiong", 19); Person p4("keke", 19); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); Person p("qqq", 19); int m = count(v.begin(), v.end(),p ); cout << "和aaa同岁的人有" << m << "个" << endl; } int main() { test(); system("pause"); return 0; }

count_if 按条件统计元素次数

count_if(iterator beg, iterator end,_pred); //按条件统计元素出现次数 //_pred是谓词 1）统计内置的数据类型 2）统计自定义的数据类型 #include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; class Person { public: Person(string name, int age) { this->m_Age = age; this->m_Name = name; } string m_Name; int m_Age; }; //仿函数 class Greater20 { public: bool operator()(const Person& p)//只要年龄大于20就返回 { return p.m_Age > 20; } }; class Ageover20 { public: bool operator()(Person& p) { return p.m_Age > 20; } }; void test() { vector<Person>v; Person p1("yutong", 26); Person p2("runqi", 19); Person p3("xiaoxiong", 19); Person p4("keke", 19); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); int m = count_if(v.begin(), v.end(), Ageover20()); cout << "年龄大于20的人有" <<m<< "个" << endl; } int main() { test(); system("pause"); return 0; }

03 排序算法

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

sort 对容器内元素进行排序

sort(iterator beg, iterator end,_pred); （非常常用的算法，一定要熟练掌握） //按值查找元素，找到返回指定位置的迭代器，找不到则返回结束迭代器的位置 //_pred默认是升序排序 1)默认用法 #include<iostream> #include<vector> #include<algorithm> using namespace std; //默认升序排序 void myPrint(int val) { cout << val << " "; } void test() { vector<int>v; v.push_back(9); v.push_back(4); v.push_back(88); v.push_back(23); v.push_back(40); v.push_back(18); v.push_back(62); v.push_back(8); v.push_back(27); sort(v.begin(), v.end()); for_each(v.begin(), v.end(), myPrint);//普通函数，把函数名放进来 cout << endl; } int main() { test(); system("pause"); return 0; }

2）改为降序排列 使用内建的函数对象greater，当然也可以自己写一个仿函数

sort(v.begin(), v.end(), greater<int>()); for_each(v.begin(), v.end(), myPrint); cout << endl;

random_shuffle 洗牌 指定范围内的元素随机调整次序

random_shuffle(iterator beg, iterator end); #include<iostream> #include<vector> #include<algorithm> #include<ctime> using namespace std; void myPrint(int val) { cout << val << " "; } void test() { srand((unsigned int)time(NULL));//加随机数种子 vector<int>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() { test(); system("pause"); return 0; }

merge 两个容器元素合并，并存储到另一容器中

merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest); //目标容器开始迭代器（目标容器要提前开辟内存空间） //注意：两个容器必须是有序的，要么都是升序，要么都是降序才行 #include<iostream> #include<vector> #include<algorithm> using namespace std; void myPrint(int val) { cout << val << " "; } void test() { vector<int>v1; vector<int>v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 5); } vector<int>v3; //提前给目标容器分配内存空间 v3.resize(v1.size() + v2.size()); merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); for_each(v3.begin(), v3.end(), myPrint); cout << endl; } int main() { test(); system("pause"); return 0; }

reverse 将容器内元素进行反转

reverse(iterator beg, iterator end); #include<iostream> #include<vector> #include<algorithm> using namespace std; void myPrint(int val) { cout << val << " "; } void test() { vector<int>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() { test(); system("pause"); return 0; }

04 拷贝和替换算法

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

copy 拷贝

copy(iterator beg, iterator end, iterator dest); //相当于赋值操作，实际应用中不常用 #include<iostream> #include<vector> #include<algorithm> using namespace std; void myPrint(int val) { cout << val << " "; } void test() { vector<int>v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } vector<int>v2; //提前开辟空间 v2.resize(v1.size()); copy(v1.begin(), v1.end(), v2.begin()); //打印 for_each(v2.begin(), v2.end(), myPrint); cout << endl; } int main() { test(); system("pause"); return 0; }

replace 旧元素修改为新元素

replace(iterator beg, iterator end, old value, new value); #include<iostream> #include<vector> #include<algorithm> using namespace std; void myPrint(int val) { cout << val << " "; } void test() { vector<int>v1; for (int i = 0; i < 10; i++) { v1.push_back(77); } cout << "替换前：" << endl; for_each(v1.begin(), v1.end(), myPrint); cout << endl; //替换 replace(v1.begin(), v1.end(), 77,22); cout << "替换后：" << endl; for_each(v1.begin(), v1.end(), myPrint); cout << endl; } int main() { test(); system("pause"); return 0; }

replace_if 按条件替换元素

replace(iterator beg, iterator end, _pred, new value); #include<iostream> #include<vector> #include<algorithm> using namespace std; void myPrint(int val) { cout << val << " "; } //仿函数 class greater5 { public: bool operator()(const int val) { return val > 5; } }; void test() { vector<int>v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } cout << "替换前：" << endl; for_each(v1.begin(), v1.end(), myPrint); cout << endl; //替换 replace_if(v1.begin(), v1.end(), greater5(),80); cout << "替换后：" << endl; for_each(v1.begin(), v1.end(), myPrint); cout << endl; } int main() { test(); system("pause"); return 0; }

利用仿函数可以灵活的筛选满足的条件；

swap 互换两个容器的元素

swap(container c1,container c2); //交换的容器要是同一种类型的 #include<iostream> #include<vector> #include<algorithm> using namespace std; void myPrint(int val) { cout << val << " "; } void test() { vector<int>v1; for (int i = 0; i < 10; i++) { v1.push_back(i); } vector<int>v2; for (int i = 0; i < 15; i++) { v2.push_back(i+100); } //容器大小不一样 也是可以互换的 v2.swap(v1); //打印 for_each(v1.begin(), v1.end(), myPrint); cout << endl; for_each(v2.begin(), v2.end(), myPrint); cout << endl; } int main() { test(); system("pause"); return 0; }

05 算术生成算法

算术生成算法属于小型算法，使用时包含的头文件为#include< numeric>accumulate //容器元素累计求和fill //重新填充

accumulate 累计求和

accumulate(iterator beg, iterator end, value); //value为起始的累加值（是额外的），相当于初值； #include<iostream> #include<vector> #include<numeric> using namespace std; void test() { vector<int>v1; for (int i = 0; i <= 100; i++) { v1.push_back(i); } int total = accumulate(v1.begin(), v1.end(), 1); cout << total << endl; } int main() { test(); system("pause"); return 0; }

fill 重新填充

fill(iterator beg, iterator end, value); //将容器区间内的元素值填充为指定的值 #include<iostream> #include<vector> #include<algorithm> #include<numeric> using namespace std; void myPrint(int val) { cout << val << " "; } void test() { vector<int>v1; for (int i = 0; i < 10; i++) { v1.push_back(22); } //重新填充为100 fill(v1.begin(), v1.end(), 100); for_each(v1.begin(), v1.end(), myPrint); cout << endl; } int main() { test(); system("pause"); return 0; }

06 集合算法

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

set_intersction 求两个容器的交集

set_intersction(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest); //两个集合必须是有序序列 #include<iostream> #include<vector> #include<algorithm> using namespace std; void myPrint(int val) { cout << val << " "; } void test() { vector<int>v1; vector<int>v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 5); } vector<int>v3; v3.resize(min(v1.size(), v2.size())); //获取交集 返回一个迭代器 位置是交集的结束迭代器地址 vector<int>::iterator itEnd=set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); for_each(v3.begin(), itEnd,myPrint);//不要使用v3的结束迭代器，使用真正的交集结束的地址 cout << endl; } int main() { test(); system("pause"); return 0; }

set_union 求两个容器的并集

set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest); #include<iostream> #include<vector> #include<algorithm> using namespace std; void myPrint(int val) { cout << val << " "; } void test() { vector<int>v1; vector<int>v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 5); } vector<int>v3; //最坏的情况是两个容器元素没有交集 v3.resize(v1.size()+v2.size()); //获取并集 返回一个迭代器 位置是并集的结束迭代器地址 vector<int>::iterator itEnd=set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); for_each(v3.begin(), itEnd,myPrint);//不要使用v3的结束迭代器 cout << endl; } int main() { test(); system("pause"); return 0; }

set_difference 求两个容器的差集

set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest); #include<iostream> #include<vector> #include<algorithm> using namespace std; void myPrint(int val) { cout << val << " "; } void test() { vector<int>v1; vector<int>v2; for (int i = 0; i < 10; i++) { v1.push_back(i); v2.push_back(i + 5); } vector<int>v3; //最坏的情况 没有一点交集 取最大的那个容器 v3.resize(max(v1.size(),v2.size())); cout << "v1和v2的差集为：" << endl; vector<int>::iterator itEnd=set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());//返回差集结束的位置 for_each(v3.begin(), itEnd,myPrint); cout << endl; cout << "v2和v1的差集为：" << endl; vector<int>::iterator itEnd2 = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v3.begin()); for_each(v3.begin(), itEnd2, myPrint); cout << endl; } int main() { test(); system("pause"); return 0; }