-
【44C++STL-常用算法----2、常用查找算法】
14.2 常用查找算法
学习目标： 掌握常用的查找算法
算法简介：
- find //查找元素
- find_if //按条件查找元素
- adacent_find //查找相邻重复元素
- binary_search //二分查找法
- count //统计元素个数
- count_if //按条件统计元素个数
14.2.1 find
功能描述：
- 查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()
函数原型：
- find(iterator beg,iterator end, value);
//按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置end()
//beg 开始迭代器
//end 结束迭代器
//value 查找的元素
示例代码：
#includeusing namespace std; #include #include #include //find //查找 内置数据类型 void test31() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } //查找 容器中是否有5 这个元素 vector<int>::iterator it = find(v.begin(), v.end(), 50); if (it == v.end()) { cout << "没有找到" <<endl; } else { cout << "找到该元素：" << *it << endl; } } //查找 自定义数据类型 class Person { public: Person(string name, int age) { this->m_name = name; this->m_age = age; } //重载 == 底层find知道如何对比person数据类型 bool operator==(const Person& p) { if (this->m_name == p.m_name && this->m_age == p.m_age) { return true; } else { return false; } } string m_name; int m_age; }; void test32() { vector<Person>v; //创建数据 Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); //将对象放到容器中 v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); Person pp("ccc", 30); //创建迭代器遍历容器中数据,查找p3 vector<Person>::iterator it = find(v.begin(), v.end(),pp); if (it == v.end()) { cout << "没有找到" << endl; } else { cout << " 找到元素 姓名：" << it->m_name << " 年龄：" << it->m_age << endl; } } int main() { //test31(); test32(); system("pause"); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
运行结果：
总结：
利用find可以在容器中找到指定的元素，返回值是迭代器
14.2.2 find_if
功能描述：
- 按条件查找元素
函数原型：
- find_if(iterator beg, iterator end, _pred);
//按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
//beg 开始迭代器
//end 结束迭代器
//_Pred 函数或者谓词（返回bool类型的仿函数）
示例代码：
#includeusing namespace std; #include #include #include //常用查找算法 find_if //1、查找内置数据类型 class GreaterFive { public: bool operator()(int val) { return val>5; } }; void test41() { 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; } } //2、查找自定义数据类型 class Person { public: Person(string name, int age) { this->m_name = name; this->m_age = age; } string m_name; int m_age; }; class Greater20 { public: bool operator()(Person& p) { return p.m_age > 20; } }; void test42() { vector<Person>v; //创建数据 Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd",40); //向容器中添加数据 v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); //找到年龄大于20的人 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() { //test41(); test42(); system("pause"); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
运行结果：
14.2.3 adjacent_find
功能描述：
- 操作相邻重复元素
函数原型：
- adjacent_find(iterator beg, iterator end);
//查找相邻重复元素，返回相邻元素的第一个位置的迭代器
//beg 开始迭代器
//end 结束迭代器
示例代码：
#includeusing namespace std; #include #include //常用查找算法 adjacent_find void test51() { vector<int>v; v.push_back(0); v.push_back(2); v.push_back(3); v.push_back(2); v.push_back(1); v.push_back(2); v.push_back(2); vector<int>::iterator pos = adjacent_find(v.begin(), v.end()); if (pos == v.end()) { cout << "未找到相邻重复元素" << endl; } else { cout << "找到相邻重复元素" << *pos << endl; } } int main() { test51(); system("pause"); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
运行结果：
总结： 该算法在实际应用开发中用到不多，但会在面试题中出现，面试官会考察你对STL的掌握程度。
14.2.4 binary_search
功能描述：
- 查找指定元素是否存在
函数原型：
- bool binary_search(iterator beg, iterator end, value);
//查找指定的元素，查到 返回true，否则false
//注意：在无序序列中不可用
//beg 开始迭代器
//end 结束迭代器
//value 查找的元素
示例代码：
#includeusing namespace std; #include #include //常用查找算法 binary_search void test61() { vector<int>v; for (int i = 0; i < 10; i++) { v.push_back(i); } //v.push_back(5); //二分查找容器中是否有8 //注意：容器必须是有序的序列，否则结果的正确性未知 bool ret = binary_search(v.begin(), v.end(), 8); if (ret) { cout << "查找到该元素" << endl; } else { cout << "没有找到" << endl; } } int main() { test61(); system("pause"); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
运行结果：
总结： 二分查找法查找效率很高，值得注意的是查找的容器中元素必须是有序序列的，否则结果正确性难以保证。
14.5.5 count
功能描述：
- 统计元素个数
函数原型：
- int count(iterator beg, iterator end, value);
//统计元素出现次数
//beg 开始迭代器
//end 结束迭代器
//value 统计的元素
**示例代码： **
#includeusing namespace std; #include #include //常用查找算法 count //1、统计内置数据类型 void test71() { vector<int>v; v.push_back(20); v.push_back(10); v.push_back(20); v.push_back(30); v.push_back(50); v.push_back(20); int num = count(v.begin(), v.end(), 20); cout << "20的个数为：" << num<<endl; } //2、统计自定义数据类型 class Person { public: Person(string name, int age) { this->m_name = name; this->m_age = age; } bool operator==(const Person& p) { if (this->m_age == p.m_age) { return true; } else { return false; } } string m_name; int m_age; }; void test72() { vector<Person>v; Person p1("刘备", 25); Person p2("张飞", 35); Person p3("赵云", 25); Person p4("曹操", 22); Person p5("关羽", 25); Person pp("诸葛亮", 35); //将数据添加到容器中 v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); v.push_back(p5); int num = count(v.begin(), v.end(), pp); } int main() { test71(); system("pause"); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
运行结果：
14.2.6 count_if
功能描述：
- 按条件统计元素个数
函数原型：
- count_if(iterator beg,iterator end, _pred);
//按条件统计元素出现次数
//beg 开始迭代器
//end 结束迭代器
//_pred 谓词
示例代码：
#includeusing namespace std; #include #include //常用查找算法 count_if //1、统计内置数据类型 class Greater20 { public: bool operator()(int val) { return val > 20; } }; void test81() { vector<int>v; v.push_back(10); v.push_back(40); v.push_back(10); v.push_back(30); v.push_back(20); v.push_back(10); int num = count_if(v.begin(), v.end(), Greater20()); cout << "大于20元素个数为：" << num << endl; } //2、统计自定义数据类型个数 class Person { public: Person(string name, int age) { m_name = name; m_age = age; } string m_name; int m_age; }; class AgeGreater20 { public: bool operator()(const Person& p) { return p.m_age > 20; } }; void test82() { vector<Person>v; Person p1("张飞", 35); Person p2("刘备", 20); Person p3("曹操", 35); Person p4("关羽", 40); Person p5("诸葛亮", 35); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); v.push_back(p5); int num = count_if(v.begin(), v.end(), AgeGreater20()); cout << "大于20岁的人员个数为：" << num << endl; } int main() { //test81(); test82(); system("pause"); return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
运行结果：
总结： 按值统计用count，按条件统计用count_if
如果对你有帮助的话，请不要忘了给我一点点点…支持 ( ^ o ^)/~
-
相关阅读:
【分布式任务调度】（四）XXL-JOB的任务调度及执行流程
猿创征文｜基于libevet的C++高并发、易扩展HTTP服务迭代之路
组件之前的传值——中央事件总线bus
RecyclerView滑动时添加缩放效果
海报在线制作系统
spring-aop源码分析(2)_AnnotationAwareAspectJAutoProxyCreator后置处理器
操作系统复习整理
【Linux】一些工具的简单使用，vim/gcc/gdb/make
CSS详细基础（三）复合选择器
论算法是如何优化的：四数之和
- 原文地址：https://blog.csdn.net/qq_45986997/article/details/126747372
