devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++ 26 常用算法_c++算法

作者：你好赵伟 | 2024-08-03 00:21:17

赞

踩

c++算法

目录

 

一、概述

1.1 常用遍历算法

1.1.1 算法简介

1.1.2 for_each遍历算法

1.1.3 transform遍历算法

1.2 常用查找算法

1.2.1 算法简介

1.2.2 find 查找算法

1.2.3 find_if 查找算法

1.2.4 adjacent_find 查找算法

1.2.5 binary_search 查找算法

1.2.6 count 查找算法

1.2.7 count_if 查找算法

1.3 常用排序算法

1.3.1 算法简介

1.3.2 sort排序算法

1.3.3 random_shuffle排序算法

1.3.4 merge排序算法

1.3.5 reverse排序算法

1.4 常用的拷贝和替换算法

1.4.1 算法简介

1.4.2 copy算法

1.4.3 replace算法

1.4.4 replace_if算法

1.4.5 swap算法

1.5 常用的算术生成算法

1.5.1 算法简介

1.5.2 accumulate生成算法

1.5.3 fill生成算法

1.6 常用集合算法

1.6.1 算法简介

1.6.2 set_intersection算法

1.6.3 set_union集合算法

1.6.4 set_difference集合算法

一、概述

① 算法主要是由头文件 #include<functional> //内建函数对象头文件, #include<numeric>, 

#include<algorithm>组成。

② <algorithm>是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历操作、复制、修改等等。

③ <numeric>体积很小，只包含几个在序列上面进行简单数学运算的模板函数。

④<functional> 定义了一些模板类，用以声明函数对象。

1.1 常用遍历算法

1.1.1 算法简介

① for_each //遍历容器

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

1.1.2 for_each遍历算法

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

② 函数原型：for_each(iterator beg, iterator end,  _func);

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5.  
  6. //普通函数
  7. void print01(int val)
  8. {
  9.     cout << val << " ";
  10. }
  11.  
  12. //仿函数
  13. class print02
  14. {
  15. public:
  16.     void operator()(int val)
  17.     {
  18.         cout << val << " ";
  19.     }
  20. };
  21.  
  22. void test01()
  23. {
  24.     vector<int>v;
  25.  
  26.     for (int i = 0; i < 10; i++)
  27.     {
  28.         v.push_back(i);
  29.     }
  30.  
  31.     for_each(v.begin(), v.end(), print01()); //利用普通函数实现遍历操作,放入函数名即可
  32.     cout << endl;
  33.  
  34.     for_each(v.begin(), v.end(), print02()); //仿函数，放入匿名函数对象即可
  35.     cout << endl;
  36.     
  37. }
  38.  
  39.  
  40. int main() 
  41. {
  42.     test01();
  43.  
  44.     system("pause");
  45.  
  46.     return 0;
  47. }
  48. 运行结果：
  49.  
  50. 0 1 2 3 4 5 6 7 8 9
  51. 0 1 2 3 4 5 6 7 8 9
  52. 请按任意键继续. . .

1.1.3 transform遍历算法

① 功能描述：搬运容器到另一个容器中。

② 函数原型：transform(iterator beg1, iterator end1, iterator beg2, _func);

  1. beg1 源容器开始迭代器
  2. end1 源容器结束迭代器
  3. beg2 目标容器开始迭代器
  4. _func 函数或者函数对象

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

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5.  
  6. //常用遍历算法 transform
  7.  
  8. class Transform
  9. {
  10. public:
  11.     int operator()(int v)
  12.     {
  13.         return v;
  14.     }
  15. };
  16.  
  17. class MyPrint
  18. {
  19. public:
  20.     void operator()(int val)
  21.     {
  22.         cout << val+100 << " ";
  23.     }
  24. };
  25.  
  26. void test01()
  27. {
  28.     vector<int>v;
  29.     for (int i = 0; i < 10; i++)
  30.     {
  31.         v.push_back(i);
  32.     }
  33.     vector<int>vTarget;  //目标容器
  34.     vTarget.resize(v.size());  //目标容器，需要提前开辟空间
  35.  
  36.     transform(v.begin(), v.end(), vTarget.begin(), Transform());
  37.     
  38.     for_each(vTarget.begin(), vTarget.end(), MyPrint());
  39.     cout << endl;
  40. }
  41.  
  42. int main() 
  43. {
  44.     test01();
  45.  
  46.     system("pause");
  47.  
  48.     return 0;
  49. }
  50. 运行结果：
  51.  
  52. 100 101 102 103 104 105 106 107 108 109
  53. 请按任意键继续. . .

1.2 常用查找算法

1.2.1 算法简介

① find //查找元素

② find_if //按条件查找元素

③ adjacent_find //查找相邻重复元素

④ binary_search //二分查找法

⑤ cout //统计元素个数

⑥ count_if //按条件统计元素个数

1.2.2 find 查找算法

① 功能描述：查找指定元素，找到返回指定元素的迭代器，找不到返回迭代器end()

② 函数原型：find(operator beg,iterator end, value);

  1. 按值查找元素，找到返回指定位置迭代器，找不到返回结束位置迭代器位置。
  2. beg 开始迭代器
  3. end 结束迭代器
  4. value 查找的元素

③ 利用find可以坐在容器这种找指定的元素，返回值是迭代器。

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6.  
  7. //查找 内置数据类型
  8. void test01()
  9. {
  10.     vector<int>v;
  11.     for (int i = 0; i < 10; i++)
  12.     {
  13.         v.push_back(i);
  14.     }
  15.  
  16.     //查找 容器中 是否有 5 这个元素
  17.     vector<int>::iterator it = find(v.begin(), v.end(), 5);
  18.     if (it == v.end())
  19.     {
  20.         cout << "没有找到！" << endl;
  21.     }
  22.     else
  23.     {
  24.         cout << "找到：" << *it << endl;
  25.     }
  26. }
  27.  
  28. class Person 
  29. {
  30. public:
  31.     Person(string name, int age)
  32.     {
  33.         this->m_Name = name;
  34.         this->m_Age = age;
  35.     }
  36.  
  37.     //重载 == 让find底层知道如何对比person数据类型
  38.     bool operator==(const Person& p)
  39.     {
  40.         if (this->m_Name == p.m_Name && this->m_Age == p.m_Age)
  41.         {
  42.             return true;
  43.         }
  44.         else
  45.         {
  46.             return false;
  47.         }
  48.     }
  49.  
  50.     string m_Name;
  51.     int m_Age;
  52. };
  53.  
  54. //查找 自定义数据类型
  55. void test02()
  56. {
  57.     vector<Person>v;
  58.     //创建数据
  59.     Person p1("aaa", 10);
  60.     Person p2("bbb", 20);
  61.     Person p3("ccc", 30);
  62.     Person p4("ddd", 40);
  63.  
  64.     //放入到容器中
  65.     v.push_back(p1);
  66.     v.push_back(p2);
  67.     v.push_back(p3);
  68.     v.push_back(p4);
  69.  
  70.     Person pp("bbb",20);
  71.  
  72.     vector<Person>::iterator it = find(v.begin(), v.end(), pp); //find找里面有没有pp这个对象
  73.     if (it == v.end())
  74.     {
  75.         cout << "没有找到" << endl;
  76.     }
  77.     else
  78.     {
  79.         cout << "找到元素姓名：" << it->m_Name << " 年龄：" << it->m_Age <<endl;
  80.     }
  81. }
  82.  
  83. int main() 
  84. {
  85.     test01();
  86.  
  87.     test02();
  88.  
  89.     system("pause");
  90.  
  91.     return 0;
  92. }
  93. 运行结果:
  94.  
  95. 找到：5
  96. 找到元素姓名：bbb 年龄：20
  97. 请按任意键继续. . .

1.2.3 find_if 查找算法

① 功能描述：按条件查找

② 函数原型：find_if(iterator beg, iterator end, _Pred);

  1. 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置。
  2. beg 开始迭代器
  3. end 结束迭代器
  4. _Pred 函数或者谓词 (返回bool类型的仿函数)
  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6.  
  7. //1、查找 内置数据类型
  8.  
  9. class GreaterFive
  10. {
  11. public:
  12.     bool operator()(int val)
  13.     {
  14.         return val > 5;  //当val大于5时，返回真
  15.     }
  16. };
  17.  
  18. void test01()
  19. {
  20.     vector<int>v;
  21.     for (int i = 0; i < 10; i++)
  22.     {
  23.         v.push_back(i);
  24.     }
  25.     vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
  26.  
  27.     if (it == v.end())
  28.     {
  29.         cout << "没有找到";
  30.     }
  31.     else
  32.     {
  33.         cout << "找到大于5的数字为：" << *it << endl;
  34.     }
  35. }
  36.  
  37. //查找 自定义数据类型
  38.  
  39. class Person 
  40. {
  41. public:
  42.     Person(string name, int age)
  43.     {
  44.         this->m_Name = name;
  45.         this->m_Age = age;
  46.     }
  47.     string m_Name;
  48.     int m_Age;
  49. };
  50.  
  51. class Greater20
  52. {
  53. public:
  54.     bool operator()(Person& p)
  55.     {
  56.         return p.m_Age > 20;
  57.     }
  58. };
  59.  
  60. void test02()
  61. {
  62.     vector<Person>v;
  63.  
  64.     //创建数据
  65.     Person p1("aaa", 10);
  66.     Person p2("bbb", 20);
  67.     Person p3("ccc", 30);
  68.     Person p4("ddd", 40);
  69.  
  70.     v.push_back(p1);
  71.     v.push_back(p2);
  72.     v.push_back(p3);
  73.     v.push_back(p4);
  74.  
  75.     //找年龄大于20的人
  76.     vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20());
  77.  
  78.     if (it == v.end())
  79.     {
  80.         cout << "没有找到" << endl;
  81.     }
  82.     else
  83.     {
  84.         cout << "找到姓名：" << it->m_Name << " 年龄：" << it->m_Age << endl;
  85.     }
  86. }
  87.  
  88. int main() {
  89.  
  90.     test01();
  91.  
  92.     test02();
  93.  
  94.     system("pause");
  95.  
  96.     return 0;
  97.  
  98. }
  99. 运行结果：
  100.  
  101. 找到大于5的数字为：6
  102. 找到姓名：ccc 年龄：30
  103. 请按任意键继续. . .

1.2.4 adjacent_find 查找算法

① 功能描述：查找相邻重复元素

② 函数原型：adjacent_find(iterator beg, iterator end);

  1. 查找相邻重复元素，返回相邻元素的第一个位置的迭代器
  2. beg 开始迭代器
  3. end 结束迭代器

③ 面试题中如果出现查找相邻重复元素，记得用STL中的adjacent_find算法

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6.  
  7. void test01()
  8. {
  9.     vector<int>v;
  10.     v.push_back(0);
  11.     v.push_back(2);
  12.     v.push_back(0);
  13.     v.push_back(3);
  14.     v.push_back(1);
  15.     v.push_back(4);
  16.     v.push_back(3); //相邻，3重复，adjacent_find()返回的是这个，第一个元素的迭代器
  17.     v.push_back(3);  
  18.  
  19.     vector<int>::iterator pos = adjacent_find(v.begin(), v.end());
  20.  
  21.     if (pos == v.end())
  22.     {
  23.         cout << "没有找到相邻重复元素";
  24.     }
  25.     else
  26.     {
  27.         cout << "找到相邻重复元素：" << *pos << endl;
  28.     }
  29. }
  30.  
  31. int main() 
  32. {
  33.     test01();
  34.  
  35.     system("pause");
  36.  
  37.     return 0;
  38. }
  39. 运行结果：
  40.  
  41. 找到相邻重复元素：3
  42. 请按任意键继续. . .

1.2.5 binary_search 查找算法

① 功能描述：查找指定元素是否存在。

② 函数原型：bool binary_search(iterator beg, iterator end, value);

  1. 查找指定的元素，查到返回true，否则false
  2. 注意：在无序序列中不可用
  3. --beg 开始迭代器
  4. --end 结束迭代器
  5. --value 查找迭代器

③ 二分法查找效率很高，值得注意的是查找的容器中元素必须是有序序列。

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6.  
  7. //常用查找算法 binary_search
  8. void test01()
  9. {
  10.     vector<int>v;
  11.     for (int i = 0; i < 10; i++)
  12.     {
  13.         v.push_back(i);
  14.     }
  15.  
  16.     //查找容器中是否有9元素
  17.     //注意：容器必须是有序的序列，上面的vector是一个升序的序列，如果vector是一个无序的序列，那么有可能找到，有可能找不到
  18.     bool ret = binary_search(v.begin(), v.end(),9);
  19.  
  20.     if (ret)
  21.     {
  22.         cout << "找到元素" << endl;
  23.     }
  24.     else
  25.     {
  26.         cout << "没有找到元素：" << endl;
  27.     }
  28.  
  29.     vector<int>v2;
  30.     for (int i = 0; i < 10; i++)
  31.     {
  32.         v2.push_back(i);
  33.     }
  34.     v2.push_back(2);  //又插入了一个元素，vector变成无序序列了，那么结果就是未知的了
  35.     bool ret2 = binary_search(v2.begin(), v2.end(), 9);
  36.  
  37.     if (ret2)
  38.     {
  39.         cout << "找到元素";
  40.     }
  41.     else
  42.     {
  43.         cout << "没有找到元素" << endl;
  44.     }
  45. }
  46.  
  47.  
  48. int main() {
  49.  
  50.     test01();
  51.  
  52.     system("pause");
  53.  
  54.     return 0;
  55.  
  56. }
  57. 运行结果：
  58.  
  59. 找到元素
  60. 没有找到元素
  61. 请按任意键继续. . .

1.2.6 count 查找算法

① 功能描述：统计元素个数。

② 函数原型：count(iterator big, iterator end, value);

  1. 统计元素出现次数
  2. beg 开始迭代器
  3. end 结束迭代器
  4. value 统计的元素

③ 统计自定义数据类型时候，需要配合重载operator==

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6.  
  7. //1、统计内置数据类型
  8.  
  9. void test01()
  10. {
  11.     vector<int>v;
  12.     v.push_back(10);
  13.     v.push_back(40);
  14.     v.push_back(30);
  15.     v.push_back(40);
  16.     v.push_back(20);
  17.     v.push_back(40);
  18.  
  19.     int num = count(v.begin(), v.end(), 40);
  20.  
  21.     cout << "40的元素个数为：" << num << endl;
  22. }
  23.  
  24. //2、统计自定义数据类型
  25.  
  26. class Person
  27. {
  28. public:
  29.     Person(string name, int age)
  30.     {
  31.         this->m_Name = name;
  32.         this->m_Age = age;
  33.     }
  34.  
  35.     // 重载==
  36.     bool operator==(const Person& p)
  37.     {
  38.         if (this->m_Age == p.m_Age)
  39.         {
  40.             return true;
  41.         }
  42.         else
  43.         {
  44.             return false;
  45.         }
  46.     }
  47.     string m_Name;
  48.     int m_Age;
  49. };
  50.  
  51. void test02()
  52. {
  53.     vector<Person>v;
  54.     Person p1("刘备", 35);
  55.     Person p2("关羽", 35);
  56.     Person p3("张飞", 35);
  57.     Person p4("赵云", 30);
  58.     Person p5("曹操", 40);
  59.     
  60.     //将人员插入到容器中
  61.     v.push_back(p1);
  62.     v.push_back(p2);
  63.     v.push_back(p3);
  64.     v.push_back(p4);
  65.     v.push_back(p5);
  66.  
  67.     Person p("诸葛亮", 35);
  68.  
  69.     int num = count(v.begin(), v.end(), p);
  70.  
  71.     cout << "和诸葛亮同岁数的人有多少：" << num << endl;
  72. }
  73.  
  74. int main() 
  75. {
  76.     test01();
  77.  
  78.     test02();
  79.  
  80.     system("pause");
  81.  
  82.     return 0;
  83. }
  84. 运行结果：
  85.  
  86. 40的元素个数为：3
  87. 和诸葛亮同岁数的人有多少：3
  88. 请按任意键继续. . .

1.2.7 count_if 查找算法

① 功能描述：按条件统计元素个数。

② 函数原型：count_if(iterator beg, iterator end, _Pred)

  1. 按条件统计元素出现次数
  2. beg 开始迭代器
  3. end 结束迭代器
  4. _Pred 谓词
  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6.  
  7. //1、统计内置数据类型
  8.  
  9. class Greater20
  10. {
  11. public:
  12.     bool operator()(int val)
  13.     {
  14.         return val > 20;
  15.     }
  16. };
  17. void test01()
  18. {
  19.     vector<int>v;
  20.     v.push_back(10);
  21.     v.push_back(40);
  22.     v.push_back(30);
  23.     v.push_back(20);
  24.     v.push_back(40);
  25.  
  26.     int num = count_if(v.begin(), v.end(), Greater20());
  27.  
  28.     cout << "在容器中大于20的元素个数为：" << num << endl;
  29. }
  30.  
  31. //2、统计自定义数据类型
  32.  
  33. class Person
  34. {
  35. public:
  36.     Person(string name, int age)
  37.     {
  38.         this->m_Name = name;
  39.         this->m_Age = age;
  40.     }
  41.     string m_Name;
  42.     int m_Age;
  43. };
  44.  
  45. class AgeGreater20
  46. {
  47. public:
  48.     bool operator()(const Person &p)
  49.     {
  50.         return p.m_Age > 20;
  51.     }
  52. };
  53.  
  54. void test02()
  55. {
  56.     vector<Person>v;
  57.     Person p1("刘备", 35);
  58.     Person p2("关羽", 35);
  59.     Person p3("张飞", 35);
  60.     Person p4("赵云", 40);
  61.     Person p5("曹操", 20);
  62.     
  63.     //将人员插入到容器中
  64.     v.push_back(p1);
  65.     v.push_back(p2);
  66.     v.push_back(p3);
  67.     v.push_back(p4);
  68.     v.push_back(p5);
  69.  
  70.     //统计 大于20岁人员个数
  71.  
  72.     int num = count_if(v.begin(), v.end(), AgeGreater20());
  73.  
  74.     cout << "大于20岁的人员个数为：" << num << endl;
  75. }
  76.  
  77. int main() {
  78.  
  79.     test01();
  80.  
  81.     //test02();
  82.  
  83.     system("pause");
  84.  
  85.     return 0;
  86.  
  87. }
  88. 运行结果：
  89.  
  90. 在容器中大于20的元素个数为：3
  91. 请按任意键继续. . .

1.3 常用排序算法

1.3.1 算法简介

① sort //对容器内元素进行排序

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

③ merge //容器元素合并，并存储到另一容器中

④ reverse //反转指定范围的元素

1.3.2 sort排序算法

① 功能描述：对容器内元素进行排序

② 函数原型：sort(iterator beg, iterator end, _Pred);

  1. 按值查找元素，找到返回指定位置迭代器，找不到返回结束位置迭代器位置
  2. beg 开始迭代器
  3. end 结束迭代器
  4. _Pred 谓词

③ sort属于开发中最常用的算法之一，需熟练掌握

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6. #include<functional>
  7.  
  8. //1、统计内置数据类型
  9.  
  10. //普通函数
  11. void myPrint(int val)
  12. {
  13.     cout << val << " ";
  14. }
  15.  
  16. void test01()
  17. {
  18.     vector<int>v;
  19.     v.push_back(10);
  20.     v.push_back(30);
  21.     v.push_back(50);
  22.     v.push_back(20);
  23.     v.push_back(40);
  24.  
  25.     //利用sort升序
  26.     sort(v.begin(), v.end()); //默认是升序排列
  27.     for_each(v.begin(), v.end(), myPrint);
  28.     cout << endl;
  29.  
  30.     //改变为降序
  31.     sort(v.begin(), v.end(), greater<int>());
  32.     for_each(v.begin(), v.end(), myPrint);
  33.     cout << endl;
  34. }
  35.  
  36. //2、统计自定义数据类型
  37.  
  38. class Person
  39. {
  40. public:
  41.     Person(string name, int age)
  42.     {
  43.         this->m_Name = name;
  44.         this->m_Age = age;
  45.     }
  46.     string m_Name;
  47.     int m_Age;
  48. };
  49.  
  50. class AgeGreater20
  51. {
  52. public:
  53.     bool operator()(const Person &p)
  54.     {
  55.         return p.m_Age > 20;
  56.     }
  57. };
  58.  
  59. void test02()
  60. {
  61.     vector<Person>v;
  62.     Person p1("刘备", 35);
  63.     Person p2("关羽", 35);
  64.     Person p3("张飞", 35);
  65.     Person p4("赵云", 40);
  66.     Person p5("曹操", 20);
  67.     
  68.     //将人员插入到容器中
  69.     v.push_back(p1);
  70.     v.push_back(p2);
  71.     v.push_back(p3);
  72.     v.push_back(p4);
  73.     v.push_back(p5);
  74.  
  75.     //统计 大于20岁人员个数
  76.     
  77.     int num = count_if(v.begin(), v.end(), AgeGreater20());
  78.  
  79.     cout << "大于20岁的人员个数为：" << num << endl;
  80. }
  81.  
  82. int main() {
  83.  
  84.     test01();
  85.  
  86.     //test02();
  87.  
  88.     system("pause");
  89.  
  90.     return 0;
  91.  
  92. }
  93. 运行结果：
  94.  
  95. 10 20 30 40 50
  96. 50 40 30 20 10
  97. 请按任意键继续. . .

1.3.3 random_shuffle排序算法

① 功能描述：洗牌算法指定范围内的元素随机调整次序。

② 函数原型：random_shuffle(iterator beg, iterator end);

  1. 指定范围内的元素随机调整次序
  2. beg 开始迭代器
  3. end 结束迭代器

③ random_shuffle洗牌算法比较实用，使用时记得加随机数种子。

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6. #include<functional>
  7. #include<ctime>
  8.  
  9. class myPrint
  10. {
  11. public:
  12.     void operator()(int val)
  13.     {
  14.         cout << val << " ";
  15.     }
  16. };
  17.  
  18. void test01()
  19. {
  20.     srand((unsigned int)time(NULL));  //生成一个随机数种子，利用时间生成，确保每次生成的随机数种子不同
  21.  
  22.     vector<int>v;
  23.     for (int i = 0; i < 10; i++)
  24.     {
  25.         v.push_back(i);
  26.     }
  27.     //利用洗牌 算法 打乱顺序
  28.     random_shuffle(v.begin(), v.end());
  29.  
  30.     for_each(v.begin(), v.end(),myPrint());
  31.     cout << endl;
  32. }
  33.  
  34. int main() 
  35. {
  36.     test01();
  37.  
  38.     system("pause");
  39.  
  40.     return 0;
  41. }
  42. 运行结果：
  43.  
  44. 1 5 7 9 4 2 6 8 3 0
  45. 请按任意键继续. . .

1.3.4 merge排序算法

① 功能描述：两个容器元素合并，并存储到另一容器中。

② 函数原型：merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

  1. 容器元素合并，并存储到另一容器中
  2. 注意：两个容器必须是有序的
  3. beg1 容器1开始迭代器
  4. end2 容器1结束迭代器
  5. beg2 容器2开始迭代器
  6. end2 容器2结束迭代器
  7. dest 目标容器开始迭代器

③ merge合并后的容器也是有序的

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6. #include<functional>
  7. #include<ctime>
  8.  
  9. void myPrint(int val)
  10. {
  11.     cout << val << " ";
  12. }
  13.  
  14. void test01()
  15. {
  16.     vector<int>v1;
  17.     vector<int>v2;
  18.  
  19.     for (int i = 0; i < 10; i++)
  20.     {
  21.         v1.push_back(i);
  22.         v2.push_back(i + 1);
  23.     }
  24.  
  25.     //目标容器
  26.     vector<int>vTarget;
  27.     vTarget.resize(v1.size() + v2.size());  //提前给目标容器分配空间
  28.     
  29.     merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
  30.     for_each(vTarget.begin(), vTarget.end(), myPrint);
  31.     cout << endl;
  32. }
  33.  
  34. int main() 
  35. {
  36.     test01();
  37.  
  38.     system("pause");
  39.  
  40.     return 0;
  41. }
  42. 运行结果：
  43.  
  44. 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
  45. 请按任意键继续. . .

1.3.5 reverse排序算法

① 功能描述：将容器内元素进行反转

② 函数原型：reverse(iterator beg, iterator end);

  1. 反转指定范围的元素
  2. beg 开始迭代器
  3. end 结束迭代器

③ reverse反转区间内的元素，面试题可能涉及到

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6. #include<functional>
  7. #include<ctime>
  8.  
  9.  
  10. void myPrint(int val)
  11. {
  12.     cout << val << " ";
  13. }
  14.  
  15. void test01()
  16. {
  17.     vector<int>v1;
  18.     v1.push_back(10);
  19.     v1.push_back(30);
  20.     v1.push_back(50);
  21.     v1.push_back(20);
  22.     v1.push_back(40);
  23.  
  24.     cout << "反转前：" << endl;
  25.     for_each(v1.begin(), v1.end(), myPrint);
  26.     cout << endl;
  27.  
  28.     cout << "反转后：" << endl;
  29.     reverse(v1.begin(), v1.end());
  30.     for_each(v1.begin(), v1.end(), myPrint);
  31.     cout << endl;
  32. }
  33.  
  34. int main() 
  35. {
  36.     test01();
  37.  
  38.     system("pause");
  39.  
  40.     return 0;
  41. }
  42. 运行结果：
  43.  
  44. 反转前：
  45. 10 30 50 20 40
  46. 反转后：
  47. 40 20 50 30 10
  48. 请按任意键继续. . .

1.4 常用的拷贝和替换算法

1.4.1 算法简介

① 算法简介：

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

1.4.2 copy算法

① 功能描述：容器内指定范围的元素拷贝到另一容器中。

② 函数原型：copy(iterator beg, iterator end, iterator dest);

  1. 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
  2. beg 开始迭代器
  3. end 结束迭代器
  4. dest 目标起始迭代器

③ 利用copy算法在拷贝时，目标容器记得提前开辟空间。

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6. #include<functional>
  7.  
  8. void myPrint(int val)
  9. {
  10.     cout << val << " ";
  11. }
  12.  
  13. void test01()
  14. {
  15.     vector<int>v1;
  16.     for (int i = 0; i < 10; i++)
  17.     {
  18.         v1.push_back(i);
  19.     }
  20.     vector<int>v2;
  21.     v2.resize(v1.size());
  22.     copy(v1.begin(),v1.end(),v2.begin());
  23.  
  24.     for_each(v2.begin(), v2.end(), myPrint);
  25.     cout << endl;
  26. }
  27.  
  28. int main() {
  29.  
  30.     test01();
  31.  
  32.     system("pause");
  33.  
  34.     return 0;
  35.  
  36. }
  37. 运行结果：
  38.  
  39. 0 1 2 3 4 5 6 7 8 9
  40. 请按任意键继续. . .

1.4.3 replace算法

① 功能描述：将容器内指定范围的旧元素修改为新元素。

② 函数原型：repalece(iterator beg, iterator end, oldvalue, newvalue);

  1. 将区间内旧元素替换成新元素
  2. beg 开始迭代器
  3. end 结束迭代器
  4. oldvalue 旧元素
  5. newvalue 新元素

③ replace会替换区间内满足条件的元素。

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6. #include<functional>
  7.  
  8. class MyPrint
  9. {
  10. public:
  11.     void operator()(int val)
  12.     {
  13.         cout << val << " ";
  14.     }
  15. };
  16.  
  17. void test01()
  18. {
  19.     vector<int>v1;
  20.     for (int i = 0; i < 10; i++)
  21.     {
  22.         v1.push_back(i);
  23.     }
  24.     v1.push_back(20);
  25.     v1.push_back(30);
  26.     v1.push_back(50);
  27.     v1.push_back(30);
  28.     v1.push_back(40);
  29.     v1.push_back(20);
  30.     v1.push_back(10);
  31.     v1.push_back(20);
  32.  
  33.     cout << "替换前：" << endl;
  34.     for_each(v1.begin(), v1.end(), MyPrint());
  35.     cout << endl;
  36.  
  37.     //将容器里面所有的20替换成2000
  38.     replace(v1.begin(), v1.end(), 20, 20000);
  39.     cout << "替换后：" << endl;
  40.     for_each(v1.begin(), v1.end(), MyPrint());
  41.     cout << endl;
  42. }
  43.  
  44. int main() 
  45. {
  46.     test01();
  47.  
  48.     system("pause");
  49.  
  50.     return 0;
  51. }
  52. 运行结果：
  53.  
  54. 替换前：
  55. 0 1 2 3 4 5 6 7 8 9 20 30 50 30 40 20 10 20
  56. 替换后：
  57. 0 1 2 3 4 5 6 7 8 9 20000 30 50 30 40 20000 10 20000
  58. 请按任意键继续. . .

1.4.4 replace_if算法

① 功能描述：将区间内满足条件的元素，替换成指定元素。

② 函数原型：replace_if(iterator beg, iterator end, _pred, newvalue);

  1. 按条件替换元素，满足条件的替换成指定元素
  2. beg 开始迭代器
  3. end 结束迭代器
  4. _pred 谓词
  5. newvalue 替换的新元素

③ replace_if 按条件查找，可以利用仿函数灵活筛选满足的条件

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6. #include<functional>
  7.  
  8. class MyPrint
  9. {
  10. public:
  11.     void operator()(int val)
  12.     {
  13.         cout << val << " ";
  14.     }
  15. };
  16.  
  17. class Greater30
  18. {
  19. public:
  20.     bool operator()(int val)
  21.     {
  22.         return val >= 30;
  23.     }
  24. };
  25.  
  26. void test01()
  27. {
  28.     vector<int>v1;
  29.     v1.push_back(20);
  30.     v1.push_back(30);
  31.     v1.push_back(50);
  32.     v1.push_back(30);
  33.     v1.push_back(40);
  34.     v1.push_back(20);
  35.     v1.push_back(10);
  36.     v1.push_back(20);
  37.  
  38.     cout << "替换前：" << endl;
  39.     for_each(v1.begin(), v1.end(), MyPrint());
  40.     cout << endl;
  41.  
  42.     //将容器里面大于等于30的 替换成30000
  43.     replace_if(v1.begin(), v1.end(), Greater30(),30000);
  44.     cout << "替换后：" << endl;
  45.     for_each(v1.begin(), v1.end(), MyPrint());
  46.     cout << endl;
  47. }
  48.  
  49. int main() 
  50. {
  51.     test01();
  52.  
  53.     system("pause");
  54.  
  55.     return 0;
  56. }
  57. 运行结果：
  58.  
  59. 替换前：
  60. 20 30 50 30 40 20 10 20
  61. 替换后：
  62. 20 30000 30000 30000 30000 20 10 20
  63. 请按任意键继续. . .

1.4.5 swap算法

① 功能描述：互换两个容器的元素。

② 函数原型：swap(container c1, container c2);

  1. 互换两个容器的元素
  2. c1容器1
  3. c2容器2

③ swap交换容器时，注意交换的容器要同种类型。

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<algorithm>
  5. #include<string>
  6. #include<functional>
  7.  
  8. class MyPrint
  9. {
  10. public:
  11.     void operator()(int val)
  12.     {
  13.         cout << val << " ";
  14.     }
  15. };
  16.  
  17. class Greater30
  18. {
  19. public:
  20.     bool operator()(int val)
  21.     {
  22.         return val >= 30;
  23.     }
  24. };
  25.  
  26. void test01()
  27. {
  28.     vector<int>v1;
  29.     vector<int>v2;
  30.     for (int i = 0; i < 10; i++)
  31.     {
  32.         v1.push_back(i);
  33.         v2.push_back(i + 100);
  34.     }
  35.  
  36.     cout << "交换前：" << endl;
  37.     for_each(v1.begin(), v1.end(), MyPrint());
  38.     cout << endl;
  39.     for_each(v2.begin(), v2.end(), MyPrint());
  40.     cout << endl;
  41.  
  42.     swap(v1,v2);
  43.     cout << "交换后：" << endl;
  44.     for_each(v1.begin(), v1.end(), MyPrint());
  45.     cout << endl;
  46.     for_each(v2.begin(), v2.end(), MyPrint());
  47.     cout << endl;
  48. }
  49.  
  50. int main() 
  51. {
  52.     test01();
  53.  
  54.     system("pause");
  55.  
  56.     return 0;
  57. }
  58. 运行结果：
  59.  
  60. 交换前：
  61. 0 1 2 3 4 5 6 7 8 9
  62. 100 101 102 103 104 105 106 107 108 109
  63. 交换后：
  64. 100 101 102 103 104 105 106 107 108 109
  65. 0 1 2 3 4 5 6 7 8 9
  66. 请按任意键继续. . .

1.5 常用的算术生成算法

1.5.1 算法简介

① 算术生成算法属于小型算法，使用时包含的头文件为 #include <numeric>

② 算法简介：

  1. accumulate //计算容器元素累积总和
  2. fill //向容器中添加元素

1.5.2 accumulate生成算法

① 计算区间内 容器元素累加总和。

② 函数原型：accumulate(iterator beg, iterator end, value);

  1. 计算容器元素累加总和
  2. beg 开始迭代器
  3. end 结束迭代器
  4. value 起始值

③ accumulate使用时，头文件注意是numeric，这个算法很实用。

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<numeric>
  5.  
  6. void test01()
  7. {
  8.     vector<int>v1;
  9.     for (int i = 0; i <= 100; i++)
  10.     {
  11.         v1.push_back(i);
  12.     }
  13.  
  14.     int total1 = accumulate(v1.begin(), v1.end(), 0);  //起始累加值为0
  15.     int total2 = accumulate(v1.begin(), v1.end(), 10000); //5050加上10000
  16.     cout << "total1 = " << total1 << endl;
  17.     cout << "total2 = " << total2 << endl;
  18. }
  19.  
  20. int main() 
  21. {
  22.     test01();
  23.  
  24.     system("pause");
  25.  
  26.     return 0;
  27. }
  28. 运行结果：
  29.  
  30. total1 = 5050
  31. total2 = 15050
  32. 请按任意键继续. . .

1.5.3 fill生成算法

① 功能描述：向容器中填充指定的元素。

② 函数原型：fill(iterator beg, iterator end, value);

  1. 向容器中填充元素
  2. beg 开始迭代器
  3. end 结束迭代器
  4. value 填充的值

③ 利用fill可以将容器区间内元素填充为指定值。

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<numeric>
  5. #include<algorithm>
  6.  
  7. void myPrint(int val)
  8. {
  9.     cout << val << " ";
  10. }
  11.  
  12. void test01()
  13. {
  14.     vector<int>v1;
  15.     v1.resize(10);
  16.     for_each(v1.begin(), v1.end(), myPrint);
  17.     cout << endl;
  18.     
  19.     //后期重新填充
  20.     fill(v1.begin(), v1.end(), 100);
  21.     for_each(v1.begin(), v1.end(), myPrint);
  22.     cout << endl;
  23. }
  24.  
  25. int main() 
  26. {
  27.     test01();
  28.  
  29.     system("pause");
  30.  
  31.     return 0;
  32. }
  33. 运行结果：
  34.  
  35. 0 0 0 0 0 0 0 0 0 0
  36. 100 100 100 100 100 100 100 100 100 100
  37. 请按任意键继续. . .

1.6 常用集合算法

1.6.1 算法简介

① set_itersection //求两个容器的交集

② set_union //求两个容器的并集

③ set_difference // 求两个容器的差集

1.6.2 set_intersection算法

① 功能描述：求两个容器的交集。

② 函数原型：set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

  1. 求两个集合的交集
  2. 注意：两个集合必须是有序序列
  3. beg1 容器1 开始迭代器
  4. end1 容器1 结束迭代器
  5. beg2 容器2 开始迭代器
  6. end2 容器2 结束迭代器
  7. dest 目标容器开始迭代器

③ 求交集的两个集合必须都是有序序列。

④ 目标容器开辟空间需要从两个容器中取小值。

⑤ set_intersection返回值是交集中最后一个元素的位置。

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<numeric>
  5. #include<algorithm>
  6.  
  7. void myPrint(int val)
  8. {
  9.     cout << val << " ";
  10. }
  11.  
  12. void test01()
  13. {
  14.     vector<int>v1;
  15.     vector<int>v2;
  16.     for (int i = 0; i < 10; i++)
  17.     {
  18.         v1.push_back(i); //0~9
  19.         v2.push_back(i + 5); //5~14
  20.     }
  21.     vector<int>vTarget;
  22.     //目标容器需要提前开辟空间
  23.     //最特殊情况 大容器包含小容器  开辟空间 取小容器的size即可
  24.     vTarget.resize(min(v1.size(), v2.size()));
  25.  
  26.     //获取交集
  27.     vector<int>::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
  28.     for_each(vTarget.begin(), vTarget.end(), myPrint); //取交集的元素少于开辟的容量，空的部分用0补充了
  29.     cout << endl;
  30.     for_each(vTarget.begin(), itEnd, myPrint); //itEnd为取交集的最后一个元素的迭代器进行返回
  31.     cout << endl;
  32. }
  33.  
  34. int main() {
  35.  
  36.     test01();
  37.  
  38.     system("pause");
  39.  
  40.     return 0;
  41.  
  42. }
  43. 运行结果：
  44.  
  45. 5 6 7 8 9 0 0 0 0 0
  46. 5 6 7 8 9
  47. 请按任意键继续. . .

1.6.3 set_union集合算法

① 功能描述：求两个集合的并集。

② 函数原型：set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

  1. 求两个集合的并集。
  2. 注意：两个集合必须是有序序列。
  3. beg1 容器1 开始迭代器
  4. end1 容器1 结束迭代器
  5. beg2 容器2 开始迭代器
  6. end2 容器2 结束迭代器
  7. dest 目标容器开始迭代器

③ 求并集的两个集合必须得是有序序列。

④ 目标容器开辟空间需要两个容器相加。

⑤ set_union返回值是并集中最后一个元素的位置。

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<numeric>
  5. #include<algorithm>
  6.  
  7. void myPrint(int val)
  8. {
  9.     cout << val << " ";
  10. }
  11.  
  12. void test01()
  13. {
  14.     vector<int>v1;
  15.     vector<int>v2;
  16.     for (int i = 0; i < 10; i++)
  17.     {
  18.         v1.push_back(i); //0~9
  19.         v2.push_back(i + 5); //5~14
  20.     }
  21.     vector<int>vTarget;
  22.     //目标容器需要提前开辟空间
  23.     //最特殊情况 两个容器没有交集，并集就是两个容器size相加
  24.     vTarget.resize(v1.size()+v2.size());
  25.  
  26.     //获取交集
  27.     vector<int>::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
  28.     for_each(vTarget.begin(), vTarget.end(), myPrint); //用最特殊的情况开辟的内存，由于一共有20个数，开辟了20个内存，并集后多余的位置为0
  29.     cout << endl;
  30.     for_each(vTarget.begin(), itEnd, myPrint); //itEnd为取并集后返回的最后一个元素的迭代器进行返回
  31.     cout << endl;
  32. }
  33.  
  34. int main() 
  35. {
  36.     test01();
  37.  
  38.     system("pause");
  39.  
  40.     return 0;
  41. }
  42. 运行结果：
  43.  
  44. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0 0 0 0
  45. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
  46. 请按任意键继续. . .

1.6.4 set_difference集合算法

① 功能描述：求两个集合的差集

② 函数原型：set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);

  1. 求两个集合的差集
  2. 注意：两个集合必须是有序序列
  3. beg1 容器1 开始迭代器
  4. end1 容器1 结束迭代器
  5. beg2 容器2 开始迭代器
  6. end2 容器2 结束迭代器
  7. dest 目标容器开始迭代器

③ 当集合前后顺序不同时，集合的差集不一样，如下图所示，V1与V2的差集、V2与V1的差集，是不一样的。

 

④ 求差集的两个集合必须是有序序列。

⑤ 目标容器的开辟空间需要从两个容器取较大值。

⑥ set_difference返回值是差集中最后一个元素的位置。

  1. #include<iostream>
  2. using namespace std;
  3. #include<vector>
  4. #include<numeric>
  5. #include<algorithm>
  6.  
  7. void myPrint(int val)
  8. {
  9.     cout << val << " ";
  10. }
  11.  
  12. void test01()
  13. {
  14.     vector<int>v1;
  15.     vector<int>v2;
  16.     for (int i = 0; i < 10; i++)
  17.     {
  18.         v1.push_back(i); //0~9
  19.         v2.push_back(i + 5); //5~14
  20.     }
  21.     vector<int>vTarget;
  22.     //目标容器需要提前开辟空间
  23.     //最特殊情况 两个容器没有交集，取两个容器中大的size作为目标容器开辟空间
  24.     vTarget.resize(max(v1.size(),v2.size()));
  25.  
  26.     cout << "v1和v2的差集为：" << endl;
  27.     vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
  28.     for_each(vTarget.begin(), vTarget.end(), myPrint); 
  29.     cout << endl;
  30.     for_each(vTarget.begin(), itEnd, myPrint); 
  31.     cout << endl;
  32.  
  33.     cout << "v2和v1的差集为：" << endl;
  34.     itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());
  35.     for_each(vTarget.begin(), vTarget.end(), myPrint);
  36.     cout << endl;
  37.     for_each(vTarget.begin(), itEnd, myPrint);
  38.     cout << endl;
  39. }
  40.  
  41. int main() 
  42. {
  43.     test01();
  44.  
  45.     system("pause");
  46.  
  47.     return 0;
  48. }
  49. 运行结果：
  50.  
  51. v1和v2的差集为：
  52. 0 1 2 3 4 0 0 0 0 0
  53. 0 1 2 3 4
  54. v2和v1的差集为：
  55. 10 11 12 13 14 0 0 0 0 0
  56. 10 11 12 13 14
  57. 请按任意键继续. . .

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/920656
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号