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

常用遍历算法

for_each遍历

for_each(iterator beg, iterator end, _func);//遍历容器

• beg//起始迭代器
• end//结束迭代器
• _func()//函数或函数对象

for_each是实际开发中最常用的遍历算法，需要熟练掌握

#include#include#includeusing namespace std; //普通函数 void myPrint(int val) {  cout << val << " "; } //仿函数 class myPrint2 { public:  void operator()(int val)  {  cout << val << " ";  } }; int main() {  vectorv;  for (int i = 0; i < 10; i++)  {  v.push_back(i);  }  for_each(v.begin(), v.end(), myPrint);  cout << endl;  for_each(v.begin(), v.end(), myPrint2());  return 0; }

transform搬运

transform(iterator beg1, iterator end1, iterator beg2, _func);//搬运容器

• beg1//源容器开始迭代器
• end1//源容器结束迭代器
• beg2//目标容器开始迭代器
• _func//函数或函数对象

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

#include#include#includeusing namespace std; class Transform { public:  int operator()(int val)  {  return val;  } }; int main() {  vectorv;  for (int i = 0; i < 10; i++)  {  v.push_back(i);  }  vectorv2;  v2.resize(v.size());  transform(v.begin(), v.end(), v2.begin(), Transform());  for (vector::iterator it = v2.begin(); it != v2.end(); it++)  {  cout << *it << " ";  }  return 0; }

常用查找算法

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

find按值查找

find(iterator beg, iterator end, value);//按值查找

• beg//开始迭代器
• end//结束迭代器
• value//查找的元素

返回一个迭代器，如果没有找到，返回end()

查找自定义数据类型需要重载==运算符，否则底层不知道如何对比

#include#include#includeusing namespace std; //查找内置数据类型 void test01() {  vectorv;  for (int i = 0; i < 10; i++)  {  v.push_back(i);  }  //返回一个迭代器，如果没有找到，返回end()  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_age = age;  this->m_name = name;  }  //重载==运算符，让find知道如何对比Person类型数据  bool operator==(const Person& p)  {  if (p.m_age == this->m_age && p.m_name == this->m_name)  return true;  else  return false;  }  string m_name;  int m_age; }; void test02() {  //准备数据  Person p1("A", 1);  Person p2("B", 2);  Person p3("C", 3);  Person p4("D", 4);  Person p5("E", 5);  //放入容器中  vectorp;  p.push_back(p1);  p.push_back(p2);  p.push_back(p3);  p.push_back(p4);  p.push_back(p5);  //查找  Person p6("A", 1);  vector::iterator it = find(p.begin(), p.end(), p6);  //输出，验证结果  if (it == p.end())  cout << "没找到" << endl;  else  cout << "找到了" << it->m_name << it->m_age << endl; } int main() {  test01();  test02();  return 0; }

find_if条件查找

find_if(iterator beg, iterator end, _Pred);

• beg//开始迭代器
• end//结束迭代器
• _Pred//函数或者谓词（返回bool数据类型的仿函数）

#include#include#includeusing namespace std; //查找内置数据类型 class GreaterFive { public:  bool operator()(int v)  {  return v > 5;  } }; void test01() {  vectorv;  for (int i = 0; i < 10; i++)  {  v.push_back(i);  }  vector::iterator it = find_if(v.begin(), v.end(), GreaterFive());  if (it == v.end())  cout << "没找到" << endl;  else  cout << "找到了" << *it << endl; } //查找自定义数据类型 class Person { public:  Person(string name, int age)  {  this->m_age = age;  this->m_name = name;  }  string m_name;  int m_age; }; class GreaterThree { public:  bool operator()(Person& p)  {  return p.m_age > 3;  } }; void test02() {  //准备数据  Person p1("A", 1);  Person p2("B", 2);  Person p3("C", 3);  Person p4("D", 4);  Person p5("E", 5);  //放入容器中  vectorp;  p.push_back(p1);  p.push_back(p2);  p.push_back(p3);  p.push_back(p4);  p.push_back(p5);  //查找  vector::iterator it = find_if(p.begin(), p.end(), GreaterThree());  //输出，验证结果  if (it == p.end())  cout << "没找到" << endl;  else  cout << "找到了" << it->m_name << it->m_age << endl; } int main() {  test01();  test02();  return 0; }

adjacent_find查找相邻重复元素

如果查到，返回相邻重复元素的第一个位置的迭代器

adjacent_find(iterator beg, iterator end)

• beg//开始迭代器
• end//结束迭代器

#include#include#includeusing namespace std; void test01() {  vectorv;  for (int i = 0; i < 10; i++)  {  v.push_back(i);  }  v.push_back(5);  vector::iterator it=adjacent_find(v.begin(), v.end());  if (it == v.end())  cout << "未找到相邻重复元素" << endl;  else  cout << "找到了相邻重复元素" << *it << endl; } int main() {  test01();  return 0; }

binary_search二分查找

bool binary_search(iterator beg, iterator end, value);

• 查找指定的元素，查到返回true，否则返回false
• 注意：在无序列表中不可用，如果是无序序列，结果未知
• beg//开始迭代器
• end//结束迭代器
• value//查找的元素

#include#include#includeusing namespace std; void test01() {  vectorv;  for (int i = 0; i < 10; i++)  {  v.push_back(i);  }  cout << binary_search(v.begin(), v.end(), 5) << endl; } int main() {  test01();  return 0; }

count统计

对于统计自定义数据类型，需要重载==运算符

#include#include#includeusing namespace std; //统计内置数据类型 void test01() {  vectorv;  v.push_back(10);  v.push_back(20);  v.push_back(10);  cout << count(v.begin(), v.end(), 10) << endl; } //统计自定义数据类型 class Person { public:  Person(string name, int age)  {  this->m_name = name;  this->m_age = age;  }  //需要重载==运算符  //底层要求加const  bool operator==(const Person& p)  {  if (this->m_name == p.m_name)  return true;  }  string m_name;  int m_age; }; void test02() {  Person p1("A", 1);  Person p2("B", 2);  Person p3("A", 3);  Person p4("A", 4);  vectorp;  p.push_back(p1);  p.push_back(p2);  p.push_back(p3);  cout << "与p4同名的元素个数" << count(p.begin(), p.end(), p4) << endl; } int main() {  test01();  test02();  return 0; }

count_if条件统计

按条件统计元素出现次数

count_if(iterator beg, iterator end, _Pred);

• beg//开始迭代器
• end//结束迭代器
• _Pred//函数或者谓词（返回bool数据类型的仿函数）

#include#include#includeusing namespace std; //统计内置数据类型 class GreaterFive { public:  bool operator()(int val)  {  return val > 5;  } }; void test01() {  vectorv;  for (int i = 0; i < 10; i++)  {  v.push_back(i);  }  cout << count_if(v.begin(), v.end(), GreaterFive()) << endl; } //统计自定义数据类型 class Person { public:  Person(string name, int age)  {  this->m_name = name;  this->m_age = age;  }  string m_name;  int m_age; }; class AgeGreaterTwo { public:  bool operator()(const Person& p)  {  return p.m_age > 2;  } }; void test02() {  Person p1("A", 1);  Person p2("B", 2);  Person p3("A", 3);  Person p4("A", 4);  vectorp;  p.push_back(p1);  p.push_back(p2);  p.push_back(p3);  p.push_back(p4);  //统计年龄大于2的人数  cout << count_if(p.begin(), p.end(), AgeGreaterTwo()) << endl; } int main() {  test01();  test02();  return 0; }

常用排序算法

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

sort排序

sort(iterator beg, iterator end, _Pred)//排序

• beg//开始迭代器
• end//结束迭代器
• _Pred//函数或者谓词，可填可不填，不填则默认升序排列

#include#include#includeusing namespace std; void test01() {  vectorv;  for (int i = 0; i < 10; i++)  {  v.push_back(i);  }  //默认升序  sort(v.begin(), v.end());  for (vector::iterator it = v.begin(); it != v.end(); it++)  {  cout << *it << " " ;  }  cout << endl;  //使用内建函数对象实现降序排列  sort(v.begin(), v.end(), greater());  for (vector::iterator it = v.begin(); it != v.end(); it++)  {  cout << *it << " ";  } } int main() {  test01();  return 0; }

random_shuffle随机洗牌

random_shuffle(iterator beg, iterator end);//随机洗牌

• 只需要提供开始迭代器和结束迭代器

srand((unsigned int)time(NULL));可以设置系统时间为随机数种子

#include#include#includeusing namespace std; void test01() {  vectorv;  for (int i = 0; i < 10; i++)  {  v.push_back(i);  }  random_shuffle(v.begin(), v.end());  for (vector::iterator it = v.begin(); it != v.end(); it++)  {  cout << *it << " " ;  }  cout << endl; } int main() {  test01();  return 0; }

merge合并

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, dest);//将两个容器元素合并，并储存到另一个容器中

• 两个容器必须是有序的
• beg1//容器1开始迭代器
• end1//容器1结束迭代器
• beg2//容器2开始迭代器
• end2//容器2结束迭代器
• dest//目标容器开始迭代器

#include#include#includeusing namespace std; void Print(int val) {  cout << val << " "; } void test01() {  vectorv1;  vectorv2;  for (int i = 0; i < 10; i++)  {  v1.push_back(i);  v2.push_back(i + 1);  }  //目标容器  vectorv3;  //目标容器需要提前开辟空间  v3.resize(v1.size() + v2.size());  merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());  //合并后仍然是有序容器  for_each(v3.begin(), v3.end(), Print); } int main() {  test01();  return 0; }

reverse反转

reverse(iterator beg, iterator end);//反转指定范围内的元素

• beg//起始迭代器
• end//结束迭代器

#include#include#includeusing namespace std; void Print(int val) {  cout << val << " "; } void test01() {  vectorv1;  for (int i = 0; i < 10; i++)  {  v1.push_back(i);  }  for_each(v1.begin(), v1.end(), Print);  cout << endl;  //反转  reverse(v1.begin(), v1.end());  for_each(v1.begin(), v1.end(), Print); } int main() {  test01();  return 0; }

常用拷贝和替换算法

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

copy拷贝

copy(iterator beg, iterator end, iterator dest);//容器内指定范围的元素拷贝到另一个容器中

• beg//开始迭代器
• end//结束迭代器
• dest//目标容器的开始迭代器

用到的比较少，直接用赋值操作更简单

#include#include#includeusing namespace std; void Print(int val) {  cout << val << " "; } void test01() {  vectorv1;  for (int i = 0; i < 10; i++)  {  v1.push_back(i);  }  vectorv2;  //v2要提前开辟空间  v2.resize(v1.size());  copy(v1.begin(), v1.end(), v2.begin());  for_each(v2.begin(), v2.end(), Print); } int main() {  test01();  return 0; }

replace替换

replace(iterator beg, iterator end, oldvalue, newvalue);//将区间内的旧元素替换为新元素

• beg//起始迭代器
• end//结束迭代器
• oldvalue//旧元素
• newvalue//新元素

#include#include#includeusing namespace std; class Print { public:  void operator()(int val)  {  cout << val << " ";  } }; void test01() {  vectorv1;  v1.push_back(1);  v1.push_back(2);  v1.push_back(1);  v1.push_back(3);  for_each(v1.begin(), v1.end(), Print());  cout << endl;  //替换  replace(v1.begin(), v1.end(), 1, 2);  for_each(v1.begin(), v1.end(), Print()); } int main() {  test01();  return 0; }

replace_if条件替换

replace_if(iterator beg, iterator end, _Pred, newvalue);//容器内指定范围满足条件的元素替换为新元素

• beg//开始迭代器
• end//结束迭代器
• _Pred//谓词
• newvalue//替换的新元素

#include#include#includeusing namespace std; class Print { public:  void operator()(int val)  {  cout << val << " ";  } }; class GreaterFive { public:  bool operator()(const int& val)  {  return val > 5;  } }; void test01() {  vectorv;  for (int i = 0; i < 10; i++)  {  v.push_back(i);  }  replace_if(v.begin(), v.end(), GreaterFive(), 0);  for_each(v.begin(), v.end(), Print()); } int main() {  test01();  return 0; }

swap互换

swap(container c1, container c2);//互换两个容器的元素

• c1容器1
• c2容器2

注意必须是同种容器

#include#include#includeusing namespace std; class Print { public:  void operator()(int val)  {  cout << val << " ";  } }; class GreaterFive { public:  bool operator()(const int& val)  {  return val > 5;  } }; void test01() {  vectorv1;  vectorv2;  for (int i = 0; i < 10; i++)  {  v1.push_back(i);  v2.push_back(i + 2);  }  //交换前  for_each(v1.begin(), v1.end(), Print());  for_each(v2.begin(), v2.end(), Print());  cout << endl;  //交换后  swap(v1, v2);  for_each(v1.begin(), v1.end(), Print());  for_each(v2.begin(), v2.end(), Print()); } int main() {  test01();  return 0; }

常用算术生成算法

算术生成算法属于小型算法，使用时包含的头文件为

• accumulate//计算容器元素累计总和
• fill//向容器中添加元素

accumulate累积

accumulate(iterator beg, iterator end, value);//计算容器元素累计总和

• beg//起始迭代器
• end//结束迭代器
• value//起始值

#include#include#includeusing namespace std; void test01() {  vectorv1;  for (int i = 0; i < 10; i++)  {  v1.push_back(i);  }  int total = accumulate(v1.begin(), v1.end(), 0);  cout << total << endl; } int main() {  test01();  return 0; }

fill填充

fill(iterator beg, iterator end, value);//向容器中添加元素

• beg//起始迭代器
• end//结束迭代器
• value//填充的值

#include#include#includeusing namespace std; void test01() {  vectorv1;  for (int i = 0; i < 10; i++)  {  v1.push_back(i);  }  for (vector::iterator it = v1.begin(); it != v1.end(); it++)  {  cout << *it << " ";  }  cout << endl;  fill(v1.begin(), v1.end(), 0);  for (vector::iterator it = v1.begin(); it != v1.end(); it++)  {  cout << *it << " ";  } } int main() {  test01();  return 0; }

常用集合容器

• 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//目标容器开始迭代器

注意事项：

• 返回值为迭代器，指向交集最后一个元素的下一个位置
• 求交集的两个集合必须为有序数列
• 目标容器开辟空间需要从两个容器中取小值

交集就是两个容器重复的元素

#include#include#include#includeusing namespace std; void myPrint(int val) {  cout << val << " "; } void test01() {  vectorv1;  vectorv2;  for (int i = 0; i < 10; i++)  {  v1.push_back(i);  v2.push_back(i + 2);  }  for_each(v1.begin(), v1.end(), myPrint);  cout << endl;  for_each(v2.begin(), v2.end(), myPrint);  cout << endl;  //目标容器需要提前开辟空间，最特殊的情况，大容器包含小容器  vectorv3;  v3.resize(min(v1.size(), v2.size()));  //取交集  vector::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());  for_each(v3.begin(), itEnd, myPrint);  cout << endl;  //如果不用返回的itEnd，会把0也给打印出来  for_each(v3.begin(), v3.end(), myPrint); } int main() {  test01();  return 0; }

set_union求并集

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//求两个容器的并集

• beg1//容器1开始迭代器
• end1//容器1结束迭代器
• beg2//容器2开始迭代器
• end2//容器2结束迭代器
• dest//目标容器开始迭代器

注意事项：

• 返回值为迭代器，指向并集最后一个元素的下一个位置
• 求并集的两个集合必须为有序数列
• 目标容器开辟空间需要两个容器相加

#include#include#include#includeusing namespace std; void myPrint(int val) {  cout << val << " "; } void test01() {  vectorv1;  vectorv2;  for (int i = 0; i < 10; i++)  {  v1.push_back(i);  v2.push_back(i + 2);  }  for_each(v1.begin(), v1.end(), myPrint);  cout << endl;  for_each(v2.begin(), v2.end(), myPrint);  cout << endl;  //目标容器需要提前开辟空间，最特殊的情况，两个容器没有交集  vectorv3;  v3.resize(v1.size() + v2.size());  //取并集  vector::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());  for_each(v3.begin(), itEnd, myPrint);  cout << endl;  //如果不用返回的itEnd，会把0也给打印出来  for_each(v3.begin(), v3.end(), myPrint); } int main() {  test01();  return 0; }

set_difference求差集

set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);//求两个容器的差集

• beg1//容器1开始迭代器
• end1//容器1结束迭代器
• beg2//容器2开始迭代器
• end2//容器2结束迭代器
• dest//目标容器开始迭代器

注意事项：

• 返回值为迭代器，指向并集最后一个元素的下一个位置
• 求并集的两个集合必须为有序数列
• 目标容器开辟空间需要从两个容器中取大值

#include#include#include#includeusing namespace std; void myPrint(int val) {  cout << val << " "; } void test01() {  vectorv1;  vectorv2;  for (int i = 0; i < 10; i++)  {  v1.push_back(i);  v2.push_back(i + 2);  }  for_each(v1.begin(), v1.end(), myPrint);  cout << endl;  for_each(v2.begin(), v2.end(), myPrint);  cout << endl;  //目标容器需要提前开辟空间，最特殊的情况，大容器和小容器没有交集  //取两个容器中大的size作为目标容器开辟空间  vectorv3;  v3.resize(max(v1.size(),v2.size()));  //取并集  vector::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());  for_each(v3.begin(), itEnd, myPrint);  cout << endl;  //如果不用返回的itEnd，会把0也给打印出来  for_each(v3.begin(), v3.end(), myPrint); } int main() {  test01();  return 0; }