bilibiliC++80-84_STL- 常用算法_查找

╰半夏微凉° 2022-10-30 05:13 204阅读 0赞

5.2 常用查找算法

学习目标:

  • 掌握常用的查找算法

算法简介:

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

5.2.1 find

功能描述:

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

函数原型:

  • find(iterator beg, iterator end, value);

    // 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置

    // beg 开始迭代器

    // end 结束迭代器

    // value 查找的元素

示例:

  1. #include<iostream>
  2. using namespace std;
  3. #include <algorithm>
  4. #include <vector>
  5. #include <string>
  6. void test01() {
  7. vector<int> v;
  8. for (int i = 0; i < 10; i++) {
  9. v.push_back(i + 1);
  10. }
  11. //查找容器中是否有 5 这个元素
  12. vector<int>::iterator it = find(v.begin(), v.end(), 5);
  13. if (it == v.end())
  14. {
  15. cout << "没有找到!" << endl;
  16. }
  17. else
  18. {
  19. cout << "找到:" << *it << endl;
  20. }
  21. }
  22. class Person {
  23. public:
  24. Person(string name, int age)
  25. {
  26. this->m_Name = name;
  27. this->m_Age = age;
  28. }
  29. //重载==
  30. bool operator==(const Person& p)
  31. {
  32. if (this->m_Name == p.m_Name && this->m_Age == p.m_Age)
  33. {
  34. return true;
  35. }
  36. return false;
  37. }
  38. public:
  39. string m_Name;
  40. int m_Age;
  41. };
  42. void test02() {
  43. vector<Person> v;
  44. //创建数据
  45. Person p1("aaa", 10);
  46. Person p2("bbb", 20);
  47. Person p3("ccc", 30);
  48. Person p4("ddd", 40);
  49. v.push_back(p1);
  50. v.push_back(p2);
  51. v.push_back(p3);
  52. v.push_back(p4);
  53. vector<Person>::iterator it = find(v.begin(), v.end(), p2);
  54. if (it == v.end())
  55. {
  56. cout << "没有找到!" << endl;
  57. }
  58. else
  59. {
  60. cout << "找到姓名:" << it->m_Name << " 年龄: " << it->m_Age << endl;
  61. }
  62. }
  63. int main()
  64. {
  65. test01();
  66. test02();
  67. system("pause");
  68. return 0;
  69. }
  70. /* 找到:5 找到姓名:bbb 年龄: 20 请按任意键继续. . . */

总结: 利用find可以在容器中找指定的元素,返回值是迭代器

5.2.2 find_if

功能描述:

  • 按条件查找元素

函数原型:

  • find_if(iterator beg, iterator end, _Pred);

    // 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置

    // beg 开始迭代器

    // end 结束迭代器

    // _Pred 函数或者谓词(返回bool类型的仿函数)

示例:

  1. #include<iostream>
  2. using namespace std;
  3. #include <algorithm>
  4. #include <vector>
  5. #include <string>
  6. //内置数据类型
  7. class GreaterFive
  8. {
  9. public:
  10. bool operator()(int val)
  11. {
  12. return val > 5;
  13. }
  14. };
  15. void test01() {
  16. vector<int> v;
  17. for (int i = 0; i < 10; i++) {
  18. v.push_back(i + 1);
  19. }
  20. vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
  21. if (it == v.end()) {
  22. cout << "没有找到!" << endl;
  23. }
  24. else {
  25. cout << "找到大于5的数字:" << *it << endl;
  26. }
  27. }
  28. //自定义数据类型
  29. class Person {
  30. public:
  31. Person(string name, int age)
  32. {
  33. this->m_Name = name;
  34. this->m_Age = age;
  35. }
  36. public:
  37. string m_Name;
  38. int m_Age;
  39. };
  40. class Greater20
  41. {
  42. public:
  43. bool operator()(Person& p)
  44. {
  45. return p.m_Age > 20;
  46. }
  47. };
  48. void test02() {
  49. vector<Person> v;
  50. //创建数据
  51. Person p1("aaa", 10);
  52. Person p2("bbb", 20);
  53. Person p3("ccc", 30);
  54. Person p4("ddd", 40);
  55. v.push_back(p1);
  56. v.push_back(p2);
  57. v.push_back(p3);
  58. v.push_back(p4);
  59. vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20());
  60. if (it == v.end())
  61. {
  62. cout << "没有找到!" << endl;
  63. }
  64. else
  65. {
  66. cout << "找到姓名:" << it->m_Name << " 年龄: " << it->m_Age << endl;
  67. }
  68. }
  69. int main() {
  70. test01();
  71. test02();
  72. system("pause");
  73. return 0;
  74. }
  75. /* 找到大于5的数字:6 找到姓名:ccc 年龄: 30 请按任意键继续. . . */

总结:find_if按条件查找使查找更加灵活,提供的仿函数可以改变不同的策略

5.2.3 adjacent_find

功能描述:

  • 查找相邻重复元素

函数原型:

  • adjacent_find(iterator beg, iterator end);

    // 查找相邻重复元素,返回相邻元素的第一个位置的迭代器

    // beg 开始迭代器

    // end 结束迭代器

示例:

  1. #include<iostream>
  2. using namespace std;
  3. #include <algorithm>
  4. #include <vector>
  5. void test01()
  6. {
  7. vector<int> v;
  8. v.push_back(1);
  9. v.push_back(2);
  10. v.push_back(5);
  11. v.push_back(2);
  12. v.push_back(4);
  13. v.push_back(4);
  14. v.push_back(3);
  15. //查找相邻重复元素
  16. vector<int>::iterator it = adjacent_find(v.begin(), v.end());
  17. if (it == v.end()) {
  18. cout << "找不到!" << endl;
  19. }
  20. else {
  21. cout << "找到相邻重复元素为:" << *it << endl;
  22. }
  23. }
  24. int main() {
  25. test01();
  26. system("pause");
  27. return 0;
  28. }
  29. /* 找到相邻重复元素为:4 请按任意键继续. . . */

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

功能描述:

  • 查找指定元素是否存在

函数原型:

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

    // 查找指定的元素,查到 返回true 否则false

    // 注意: 在无序序列中不可用

    // beg 开始迭代器

    // end 结束迭代器

    // value 查找的元素

示例:

  1. #include<iostream>
  2. using namespace std;
  3. #include <algorithm>
  4. #include <vector>
  5. void test01()
  6. {
  7. vector<int>v;
  8. for (int i = 0; i < 10; i++)
  9. {
  10. v.push_back(i);
  11. }
  12. //二分查找
  13. bool ret = binary_search(v.begin(), v.end(), 2);
  14. if (ret)
  15. {
  16. cout << "找到了" << endl;
  17. }
  18. else
  19. {
  20. cout << "未找到" << endl;
  21. }
  22. }
  23. int main() {
  24. test01();
  25. system("pause");
  26. return 0;
  27. }
  28. /* 找到了 请按任意键继续. . .*/

**总结:**二分查找法查找效率很高,值得注意的是查找的容器中元素必须的有序序列

5.2.5 count

功能描述:

  • 统计元素个数

函数原型:

  • count(iterator beg, iterator end, value);

    // 统计元素出现次数

    // beg 开始迭代器

    // end 结束迭代器

    // value 统计的元素

示例:

  1. #include<iostream>
  2. using namespace std;
  3. #include <algorithm>
  4. #include <vector>
  5. //内置数据类型
  6. void test01()
  7. {
  8. vector<int> v;
  9. v.push_back(1);
  10. v.push_back(2);
  11. v.push_back(4);
  12. v.push_back(5);
  13. v.push_back(3);
  14. v.push_back(4);
  15. v.push_back(4);
  16. int num = count(v.begin(), v.end(), 4);
  17. cout << "4的个数为: " << num << endl;
  18. }
  19. //自定义数据类型
  20. class Person
  21. {
  22. public:
  23. Person(string name, int age)
  24. {
  25. this->m_Name = name;
  26. this->m_Age = age;
  27. }
  28. bool operator==(const Person& p)
  29. {
  30. if (this->m_Age == p.m_Age)
  31. {
  32. return true;
  33. }
  34. else
  35. {
  36. return false;
  37. }
  38. }
  39. string m_Name;
  40. int m_Age;
  41. };
  42. void test02()
  43. {
  44. vector<Person> v;
  45. Person p1("刘备", 35);
  46. Person p2("关羽", 35);
  47. Person p3("张飞", 35);
  48. Person p4("赵云", 30);
  49. Person p5("曹操", 25);
  50. v.push_back(p1);
  51. v.push_back(p2);
  52. v.push_back(p3);
  53. v.push_back(p4);
  54. v.push_back(p5);
  55. Person p("诸葛亮", 35);
  56. int num = count(v.begin(), v.end(), p);
  57. cout << "num = " << num << endl;
  58. }
  59. int main() {
  60. test01();
  61. test02();
  62. system("pause");
  63. return 0;
  64. }
  65. /* 4的个数为: 3 num = 3 请按任意键继续. . .*/

总结: 统计自定义数据类型时候,需要配合重载 operator==

5.2.6 count_if

功能描述:

  • 按条件统计元素个数

函数原型:

  • count_if(iterator beg, iterator end, _Pred);

    // 按条件统计元素出现次数

    // beg 开始迭代器

    // end 结束迭代器

    // _Pred 谓词

示例:

  1. #include<iostream>
  2. using namespace std;
  3. #include <algorithm>
  4. #include <vector>
  5. class Greater4
  6. {
  7. public:
  8. bool operator()(int val)
  9. {
  10. return val >= 4;
  11. }
  12. };
  13. //内置数据类型
  14. void test01()
  15. {
  16. vector<int> v;
  17. v.push_back(1);
  18. v.push_back(2);
  19. v.push_back(4);
  20. v.push_back(5);
  21. v.push_back(3);
  22. v.push_back(4);
  23. v.push_back(4);
  24. int num = count_if(v.begin(), v.end(), Greater4());
  25. cout << "大于4的个数为: " << num << endl;
  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. string m_Name;
  37. int m_Age;
  38. };
  39. class AgeLess35
  40. {
  41. public:
  42. bool operator()(const Person& p)
  43. {
  44. return p.m_Age < 35;
  45. }
  46. };
  47. void test02()
  48. {
  49. vector<Person> v;
  50. Person p1("刘备", 35);
  51. Person p2("关羽", 35);
  52. Person p3("张飞", 35);
  53. Person p4("赵云", 30);
  54. Person p5("曹操", 25);
  55. v.push_back(p1);
  56. v.push_back(p2);
  57. v.push_back(p3);
  58. v.push_back(p4);
  59. v.push_back(p5);
  60. int num = count_if(v.begin(), v.end(), AgeLess35());
  61. cout << "小于35岁的个数:" << num << endl;
  62. }
  63. int main() {
  64. test01();
  65. test02();
  66. system("pause");
  67. return 0;
  68. }
  69. /* 大于4的个数为: 4 小于35岁的个数:2 请按任意键继续. . .*/

总结: 按值统计用count,按条件统计用count_if

发表评论

表情:
评论列表 (有 0 条评论,204人围观)

还没有评论,来说两句吧...

相关阅读