• 【C++】常用查找算法

    目录

    find

    find_if

    adjacent_find

    binary_search

    count

    count_if

    查找算法简介：

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

    find

    功能：

    • 查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器

    函数原型：

    find(iterator beg, iterator end, value);

    beg  —— 开始迭代器

    end  —— 结束迭代器

    value—— 查找的元素

    测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4. #include
    5. #include
    6.  
    7. class Person {
    8. public:
    9.     Person(string name, int age) :m_Name(name), m_Age(age) {}
    10.     // 重载 == 让底层 find 知道 == 方式
    11.     bool operator==(const Person& p) {
    12.         if (this->m_Name == p.m_Name && this->m_Age == p.m_Age) return true;
    13.         else return false;
    14.     }
    15.     string m_Name;
    16.     int m_Age;
    17. };
    18.  
    19. // 查找内置数据类型
    20. void test1() {
    21.     vector<int>v;
    22.     for (int i = 0; i < 10; ++i) {
    23.         v.push_back(i);
    24.     }
    25.  
    26.     int find_x = 9;
    27.     
    28.     // 返回迭代器
    29.     vector<int>::iterator it = find(v.begin(), v.end(), find_x);
    30.     if (it != v.end()) {
    31.         cout << "找到了" << *it << endl;
    32.     }
    33.     else {
    34.         cout << "未找到" << endl;
    35.     }
    36. }
    37.  
    38. // 查找自定义数据类型
    39. void test2() {
    40.     vectorv;
    41.     Person p1("李四", 19);
    42.     Person p2("张三", 19);
    43.     Person p3("王五", 19);
    44.  
    45.     v.push_back(p1);
    46.     v.push_back(p2);
    47.     v.push_back(p3);
    48.  
    49.     Person find_p("张三", 19);
    50.  
    51.     vector::iterator it = find(v.begin(), v.end(), find_p);
    52.     if (it != v.end()) {
    53.         cout << "找到" << (*it).m_Name << " " << it->m_Age << endl;
    54.     }
    55.     else {
    56.         cout << "未找到" << endl;
    57.     }
    58. }
    59.  
    60. int main() {
    61.     test1();
    62.     test2();
    63.     system("pause");
    64.     return 0;
    65. }

    运行结果：

    自定义数据类型查找的时候需要重载 == 运算符，让底层代码知道如何进行比较判断

    重载 == 改变解引用First 与 Val 的比较方式

    find_if

    功能：

    • 按条件查找元素，找到返回指定元素的迭代器，找不到返回结束迭代器

    函数原型：

    find_if(iterator beg, iterator end, _Pred);

    beg     —— 开始迭代器

    end     —— 结束迭代器

    _Pred  —— 函数或者谓词（返回 bool 类型的仿函数）

    测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4. #include
    5. #include
    6.  
    7. class Person {
    8. public:
    9.     Person(string name, int age) :m_Name(name), m_Age(age) {}   
    10.     string m_Name;
    11.     int m_Age;
    12. };
    13.  
    14. class Greater5 {
    15. public:
    16.     bool operator()(const int& x) {
    17.         if (x > 5) return true;
    18.         else return false;
    19.     }
    20. };
    21.  
    22. class Greater20 {
    23. public:
    24.     bool operator()(const Person& p) {
    25.         if (p.m_Age > 20) return true;
    26.         else return false;
    27.     }
    28. };
    29.  
    30. bool Greater8(const int& x) {
    31.     if (x > 8) return true;
    32.     else return false;
    33. }
    34.  
    35. bool Greater30(const Person& p) {
    36.     if (p.m_Age > 30) return true;
    37.     else return false;
    38. }
    39.  
    40. // 内置数据类型 find_if
    41. void test01() {
    42.     vector<int>v;
    43.     for (int i = 0; i < 10; ++i)  v.push_back(i + 1);
    44.  
    45.     vector<int>::iterator it1 = find_if(v.begin(), v.end(), Greater5()); // 传入仿函数（谓词）
    46.     vector<int>::iterator it2 = find_if(v.begin(), v.end(), Greater8);   // 传入普通函数
    47.  
    48.     if (it1 != v.end()) {
    49.         cout << "find it " << *it1 << endl;
    50.     }
    51.     else {
    52.         cout << "no find it" << endl;
    53.     }
    54.     if (it2 != v.end()) {
    55.         cout << "find it " << *it2 << endl;
    56.     }
    57.     else {
    58.         cout << "no find it" << endl;
    59.     }
    60. }
    61.  
    62. // 自定义数据类型 find_if
    63. void test02() {
    64.     vectorv;
    65.  
    66.     Person p1("张三", 18);
    67.     Person p2("张三", 30);
    68.     Person p3("李四", 19);
    69.     Person p4("王五", 40);
    70.  
    71.     v.push_back(p1);
    72.     v.push_back(p2);
    73.     v.push_back(p3);
    74.     v.push_back(p4);
    75.  
    76.     vector::iterator it1 = find_if(v.begin(), v.end(), Greater20()); // 传入仿函数（谓词）
    77.     vector::iterator it2 = find_if(v.begin(), v.end(), Greater30);   // 传入普通函数
    78.  
    79.     if (it1 != v.end()) {
    80.         cout << "找到了" << it1->m_Name << " " << (*it1).m_Age << endl;
    81.     }
    82.     else {
    83.         cout << "未找到" << endl;
    84.     }
    85.     if (it2 != v.end()) {
    86.         cout << "找到了" << it2->m_Name << " " << (*it2).m_Age << endl;
    87.     }
    88.     else {
    89.         cout << "未找到" << endl;
    90.     }
    91. }
    92.  
    93. int main() {
    94.     test01();
    95.     test02();
    96.     system("pause");
    97.     return 0;
    98. }

    运行结果：

     find_it 底层代码

    只要是调用传入的函数（条件），所以无需重载操作符，只需要在函数或者仿函数里写清楚条件就可以，返回类型要能进行判断，所以为 bool 类型

    adjacent_find

    功能：

    • 查找相邻重复元素，返回相邻元素的第一个位置的迭代器，没找到返回结束迭代器

    函数原型：

    adjacent_find(iterator beg, iterator end);

    beg —— 开始迭代器

    end —— 结束迭代器

    测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4. #include
    5.  
    6. void test() {
    7.     vector<int>v;
    8.     
    9.     v.push_back(10);
    10.     v.push_back(20);
    11.     v.push_back(10); // 相邻
    12.     v.push_back(10); // 相邻
    13.     v.push_back(40);
    14.     v.push_back(30);
    15.  
    16.     vector<int>::iterator it = adjacent_find(v.begin(), v.end());
    17.     
    18.     if (it != v.end()) {
    19.         cout << "find " << *it << endl;
    20.     }
    21.     else {
    22.         cout << "no find" << endl;
    23.     }
    24. }
    25.  
    26. int main() {
    27.     test();
    28.     system("pause");
    29.     return 0;
    30. }

    运行代码：

    功能：

    • 查找指定元素是否存在，存在返回 true ，不存在返回 false

    函数原型：

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

    beg   ——  开始迭代器

    end   ——  结束迭代器

    value ——  查找的元素

    注意：在 无序 、降序 序列中不可用

    测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4. #include
    5. #include
    6.  
    7. class Person {
    8. public:
    9.     Person(string name, int age) :m_Name(name), m_Age(age) {}
    10.     int m_Age;
    11.     string m_Name;
    12. };
    13.  
    14. // 测试 升序
    15. void test01() {
    16.     vector<int>v;
    17.  
    18.     for (int i = 1; i < 11; ++i) {
    19.         v.push_back(i); 
    20.     }
    21.  
    22.     for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    23.         cout << *it << " "; // 1 - 10
    24.     }
    25.     cout << endl;
    26.  
    27.     int find_x = 9;
    28.     bool ret = binary_search(v.begin(), v.end(), find_x);
    29.  
    30.     if (ret != false)  cout << "find it " << find_x << endl;
    31.     else               cout << "no find " << find_x << endl;
    32. }
    33.  
    34. // 测试 倒序
    35. void test02() {
    36.     vector<int>v;
    37.     for (int i = 10; i > 0; --i) {
    38.         v.push_back(i); 
    39.     }
    40.  
    41.     for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    42.         cout << *it << " "; // 10 - 1
    43.     }
    44.     cout << endl;
    45.  
    46.     int find_x = 9;
    47.     bool ret = binary_search(v.begin(), v.end(), find_x);
    48.  
    49.     if (ret != false) cout << "find it " << find_x << endl;
    50.     else              cout << "no find " << find_x << endl;
    51. }
    52.  
    53. // 测试 无序
    54. void test03() {
    55.     vector<int>v;
    56.     
    57.     v.push_back(1);
    58.     v.push_back(3);
    59.     v.push_back(2);
    60.     v.push_back(0);
    61.  
    62.     for (vector<int>::iterator it = v.begin(); it != v.end(); ++it) {
    63.         cout << *it << " "; // 1 3 2 0
    64.     }
    65.     cout << endl;
    66.  
    67.     int  find_x = 3;
    68.     bool ret    = binary_search(v.begin(), v.end(), find_x);
    69.  
    70.     // 无序序列结果是未知的
    71.     if (ret != false)  cout << "find it " << find_x << endl;
    72.     else               cout << "no find " << find_x << endl;
    73. }
    74.  
    75. int main() {
    76.     test01();
    77.     test02();
    78.     test03();
    79.     system("pause");
    80.     return 0;
    81. }

    运行结果：

    count

    功能：

    • 统计元素个数，返回 __int64 （元素出现的次数）

    函数原型：

    count(iterator beg, iterator end, value);

    beg   —— 开始迭代器

    end   —— 结束迭代器

    value —— 统计的元素

    Val == *_UFirst，自定义数据类型的判断就需要改变 == 的方式，也就是重载

    测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4. #include
    5. #include
    6.  
    7. class Person {
    8. public:
    9.     Person(string name, int age) :m_Name(name), m_Age(age) {}
    10.     bool operator==(const Person& p) {
    11.         if (this->m_Name == p.m_Name && this->m_Age == p.m_Age) {
    12.             return true;
    13.         }
    14.         else {
    15.             return false;
    16.         }
    17.     }
    18.     string m_Name;
    19.     int m_Age;
    20. };
    21.  
    22. // 统计内置数据类型
    23. void test01() {
    24.     vector<int>v;
    25.     v.push_back(10);
    26.     v.push_back(30);
    27.     v.push_back(20);
    28.     v.push_back(10);
    29.  
    30.     int count_x = 10;
    31.     __int64 nums = count(v.begin(), v.end(), count_x);
    32.     cout << count_x << "出现次数：" << nums << endl;
    33. }
    34.  
    35. // 统计自定义数据类型
    36. void test02() {
    37.     vectorv;
    38.     Person p1("张三", 19);
    39.     Person p2("李四", 20);
    40.     Person p3("王五", 17);
    41.     Person p4("王五", 17);
    42.     Person p5("王五", 17);
    43.  
    44.     v.push_back(p1);
    45.     v.push_back(p2);
    46.     v.push_back(p3);
    47.     v.push_back(p4);
    48.     v.push_back(p5);
    49.  
    50.     Person count_Person("王五", 17);
    51.     __int64 nums = count(v.begin(), v.end(), count_Person);
    52.     cout << count_Person.m_Name << " " << count_Person.m_Age << " 出现次数：" << nums << endl;
    53.  
    54. }
    55.  
    56. int main() {
    57.     test01();
    58.     test02();
    59.     system("pause");
    60.     return 0;
    61. }

    运行结果：

    count_if

    功能：

    • 按条件统计元素个数，返回 __int64 （元素出现次数）

    函数原型：

    count_if(iterator beg, iterator end, _Pred);

    beg     —— 开始迭代器

    end     —— 结束迭代器

    _Pred  —— 谓词（仿函数）、函数

     测试代码：

    1. #include
    2. using namespace std;
    3. #include
    4. #include
    5. #include
    6.  
    7. class Person {
    8. public:
    9.     Person(string name, int age) :m_Name(name), m_Age(age) {}
    10.     string m_Name;
    11.     int m_Age;
    12. };
    13.  
    14. // 自定义数据类型 count_if 仿函数
    15. class Person_find {
    16. public:
    17.     bool operator()(const Person& p) {
    18.         if (p.m_Age > 18) return true;
    19.         else              return false;
    20.     }
    21. };
    22.  
    23. // 内置数据类型 count_if 仿函数
    24. class my_find {
    25. public:
    26.     bool operator()(const int& x) {
    27.         if (x > 2 && x < 5)  return true;
    28.         else                 return false;
    29.     }
    30. };
    31.  
    32. // 内置数据类型 count_if
    33. void test01() {
    34.     vector<int>v;
    35.     v.push_back(5);
    36.     v.push_back(1); 
    37.     v.push_back(2); 
    38.     v.push_back(4); // √
    39.     v.push_back(3); // √
    40.  
    41.     __int64 nums = count_if(v.begin(), v.end(), my_find());
    42.     cout << "满足大于 2 小于 5 条件的数： " << nums << endl; // 2
    43. }
    44.  
    45. // 自定义数据类型 count_if
    46. void test02() {
    47.     vectorv;
    48.     Person p1("李四", 19); 
    49.     Person p2("张三", 20); 
    50.     Person p3("王五", 15);
    51.     Person p4("李华", 10);
    52.  
    53.     v.push_back(p1); // √
    54.     v.push_back(p2); // √
    55.     v.push_back(p3);
    56.     v.push_back(p4);
    57.  
    58.     __int64 nums = count_if(v.begin(), v.end(), Person_find());
    59.     cout << "成年人数为：" << nums << endl; // 2
    60. }
    61.  
    62. int main() {
    63.     test01();
    64.     test02();
    65.     system("pause");
    66.     return 0;
    67. }

    运行额结果：

  • 相关阅读:
    C#:实现交换排序算法(附完整源码)
    活动安排问题(贪心算法)
    netcore Polly.Core
    RxJava + Retrofit源码解析
    【机器学习算法】支持向量机（support Vector Machine，SVM）
    32、多租户(multi-tenancy)
    vue.js v-bind的基本使用语法
    华为企业AP开启IPV6包转发
    逻辑漏洞（pikachu）
    安卓WebApp开发-项目MiliSetu
  • 原文地址：https://blog.csdn.net/xuan3215/article/details/126181436