1. find //查找元素
2. find_if //按条件查找元素
3. adjacent_find //查找相邻重复元素
4. binary_search //二分查找法
5. count //统计元素个数
6. count_if //按条件统计元素个数
1. find //查找元素
// 常用查找算法：find /* 功能描述： 查找指定元素，找到'返回'指定元素的'迭代器'，找不到返回结束迭代器end() 函数原型： find(iterator beg, iterator end, value); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // value 查找的'元素' */ #include <bits/stdc++.h> using namespace std; // 查找内置数据类型 void test01() { vector<int> v; for (int i = 0; i < 10; i++) { v.push_back(i); } // 查找容器中是否有元素5 vector<int>::iterator it = find(v.begin(), v.end(), 5); if (it == v.end()) { cout << "no" << endl; } else { cout << "yes," << (*it) << endl; // √ yes,5 } } // 查找自定义数据类型 class person { public: person(string name, int age) { this->name = name; this->age = age; } string name; int age; // 重载=，让底层find知道如何对比person数据类型 bool operator==(const person &p) { if (this->name == p.name && this->age == p.age) return true; else { return false; } } }; void test02() { 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); vector<person>::iterator it = find(v.begin(), v.end(), p2); if (it == v.end()) { cout << "no" << endl; } else { cout << "yes," << (*it).name << " " << (*it).age << endl; // √ yes,bbb 20 } } int main() { test01(); test02(); } /* 总结： 利用find可以在容器中找指定的元素，返回值是迭代器 */
2. find_if //按条件查找元素
// 常用查找算法：find_if /* 功能描述： 按条件查找元素 函数原型： find_if(iterator beg, iterator end, _Pred); // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // _Pred 函数或者谓词（返回bool类型的仿函数） */ #include <bits/stdc++.h> using namespace std; // 查找内置数据类型 class greaterfive { public: bool operator()(int val) { return val > 5; } }; void test01() { vector<int> v; for (int i = 0; i < 10; i++) { v.push_back(i); } // 查找容器中>5元素的位置 vector<int>::iterator it = find_if(v.begin(), v.end(), greaterfive()); if (it == v.end()) { cout << "no" << endl; } else { cout << "yes,大于5的数字为" << (*it) << endl; // √ yes,大于5的数字为6 } } // 查找自定义数据类型 class person { public: person(string name, int age) { this->name = name; this->age = age; } string name; int age; }; class greater20 { public: bool operator()(person &p) { return p.age > 20; } }; void test02() { 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 << "no" << endl; } else { cout << "yes," << (*it).name << " " << (*it).age << endl; // √ yes,ccc 30 } } int main() { test01(); test02(); } /* 总结： find_if按条件查找使查找更加灵活，提供的仿函数可以改变不同的策略 */
3. adjacent_find //查找相邻重复元素
// 常用查找算法：adjacent_find /* 功能描述： 查找相邻重复元素 函数原型： adjacent_find(iterator beg, iterator end); // 查找'相邻重复'元素,返回相邻元素的第一个位置的迭代器 // beg 开始迭代器 // end 结束迭代器 */ #include <bits/stdc++.h> using namespace std; void test01() { vector<int> v; v.push_back(0); v.push_back(2); v.push_back(0); v.push_back(3); v.push_back(1); v.push_back(4); v.push_back(3); v.push_back(3); // 查找容器中'相邻重复'元素,返回相邻元素的第一个位置的迭代器 vector<int>::iterator it = adjacent_find(v.begin(), v.end()); if (it == v.end()) { cout << "no" << endl; } else { cout << "yes,第一个相邻重复元素为" << (*it) << endl; // √ yes,第一个相邻重复元素为3 } } int main() { test01(); } /* 总结： 面试题中如果出现查找相邻重复元素，记得用STL中的adjacent_find算法 */
4. binary_search //二分查找法
// 常用查找算法：binary_search // 二分查找法(返回bool，在有序序列中使用) /* 功能描述： 查找指定元素是否'存在' 函数原型： bool binary_search(iterator beg, iterator end, value); // 查找指定的元素，查到 返回true 否则false // 注意: '在无序序列中不可用' // beg 开始迭代器 // end 结束迭代器 // value 查找的元素 */ #include <bits/stdc++.h> using namespace std; void test01() { vector<int> v; for (int i = 0; i < 10; i++) { v.push_back(i); } // 查找元素，返回bool 容器必须为有序序列，若无序，则可能不会找到 bool it = binary_search(v.begin(), v.end(), 9); if (!it) { cout << "no" << endl; } else { cout << "yes" << endl; // √ yes } } int main() { test01(); } /* 总结： 二分查找法查找效率很高，值得注意的是查找的容器中元素必须的有序序列 */
5. count //统计元素个数
// 常用查找算法：count /* 功能描述： 统计元素个数（返回int） 函数原型： count(iterator beg, iterator end, value); // 统计元素出现次数 // beg 开始迭代器 // end 结束迭代器 // value 统计的元素 */ #include <bits/stdc++.h> using namespace std; // 统计内置数据类型 void test01() { vector<int> v; v.push_back(10); v.push_back(40); v.push_back(30); v.push_back(40); v.push_back(20); v.push_back(40); int num = count(v.begin(), v.end(), 40); cout << num << endl; // 3 } // 统计自定义数据类型 class person { public: person(string name, int age) { this->name = name; this->age = age; } string name; int age; bool operator==(const person &p) // 一定要加const!!!! { if (this->age == p.age) return true; else return false; } }; void test02() { vector<person> v; person p1("aaa", 10); person p2("bbb", 10); person p3("ccc", 20); person p4("ddd", 40); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); person p("eee", 10); int num = count(v.begin(), v.end(), p); // 统计与eee年龄相同的个数 cout << num << endl; // 2 } int main() { test02(); } /* 总结： 统计自定义数据类型时候，需要配合重载 operator== 并且加const */
6. count_if //按条件统计元素个数
// 常用查找算法：count_if /* 功能描述： 按条件统计元素个数,返回int 函数原型： count_if(iterator beg, iterator end, _Pred); // 按条件统计元素出现次数 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词 */ #include <bits/stdc++.h> using namespace std; // 统计内置数据类型 class greater20 { public: bool operator()(int val) { return val > 20; } }; void test01() { vector<int> v; v.push_back(10); v.push_back(40); v.push_back(30); v.push_back(20); v.push_back(40); v.push_back(20); // 查>20的数 int num = count_if(v.begin(), v.end(), greater20()); cout << num << endl; // 3 } // 统计自定义数据类型 class person { public: person(string name, int age) { this->name = name; this->age = age; } string name; int age; }; class greater30 { public: bool operator()(const person &p) // 加const!!! { if (p.age > 30) return true; else return false; } }; void test02() { vector<person> v; person p1("aaa", 10); person p2("bbb", 10); person p3("ccc", 20); person p4("ddd", 40); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); int num = count_if(v.begin(), v.end(), greater30()); // 统计>30的人数 cout << num << endl; // 1 } int main() { test01(); test02(); } /* 总结： 按值统计用count，按条件统计用count_if */
