目录
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—— 查找的元素
功能:
- 查找指定元素,找到返回指定元素的迭代器,找不到返回结束迭代器
函数原型:
find(iterator beg, iterator end, value);
beg —— 开始迭代器
end —— 结束迭代器
value—— 查找的元素
测试代码:
#includeusing namespace std; #include #include #include class Person { public: Person(string name, int age) :m_Name(name), m_Age(age) {} // 重载 == 让底层 find 知道 == 方式 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 test1() { vector v; for (int i = 0; i < 10; ++i) { v.push_back(i); } int find_x = 9; // 返回迭代器 vector ::iterator it = find(v.begin(), v.end(), find_x); if (it != v.end()) { cout << "找到了" << *it << endl; } else { cout << "未找到" << endl; } } // 查找自定义数据类型 void test2() { vector v; Person p1("李四", 19); Person p2("张三", 19); Person p3("王五", 19); v.push_back(p1); v.push_back(p2); v.push_back(p3); Person find_p("张三", 19); vector ::iterator it = find(v.begin(), v.end(), find_p); if (it != v.end()) { cout << "找到" << (*it).m_Name << " " << it->m_Age << endl; } else { cout << "未找到" << endl; } } int main() { test1(); test2(); system("pause"); return 0; }
运行结果:
自定义数据类型查找的时候需要重载 == 运算符,让底层代码知道如何进行比较判断
重载 == 改变解引用First 与 Val 的比较方式
find_if
功能:
- 按条件查找元素,找到返回指定元素的迭代器,找不到返回结束迭代器
函数原型:
find_if(iterator beg, iterator end, _Pred);
beg —— 开始迭代器
end —— 结束迭代器
_Pred —— 函数或者谓词(返回 bool 类型的仿函数)
功能:
- 按条件查找元素,找到返回指定元素的迭代器,找不到返回结束迭代器
函数原型:
find_if(iterator beg, iterator end, _Pred);
beg —— 开始迭代器
end —— 结束迭代器
_Pred —— 函数或者谓词(返回 bool 类型的仿函数)
测试代码:
#includeusing namespace std; #include #include #include class Person { public: Person(string name, int age) :m_Name(name), m_Age(age) {} string m_Name; int m_Age; }; class Greater5 { public: bool operator()(const int& x) { if (x > 5) return true; else return false; } }; class Greater20 { public: bool operator()(const Person& p) { if (p.m_Age > 20) return true; else return false; } }; bool Greater8(const int& x) { if (x > 8) return true; else return false; } bool Greater30(const Person& p) { if (p.m_Age > 30) return true; else return false; } // 内置数据类型 find_if void test01() { vector v; for (int i = 0; i < 10; ++i) v.push_back(i + 1); vector ::iterator it1 = find_if(v.begin(), v.end(), Greater5()); // 传入仿函数(谓词) vector ::iterator it2 = find_if(v.begin(), v.end(), Greater8); // 传入普通函数 if (it1 != v.end()) { cout << "find it " << *it1 << endl; } else { cout << "no find it" << endl; } if (it2 != v.end()) { cout << "find it " << *it2 << endl; } else { cout << "no find it" << endl; } } // 自定义数据类型 find_if void test02() { vector v; Person p1("张三", 18); Person p2("张三", 30); Person p3("李四", 19); Person p4("王五", 40); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); vector ::iterator it1 = find_if(v.begin(), v.end(), Greater20()); // 传入仿函数(谓词) vector ::iterator it2 = find_if(v.begin(), v.end(), Greater30); // 传入普通函数 if (it1 != v.end()) { cout << "找到了" << it1->m_Name << " " << (*it1).m_Age << endl; } else { cout << "未找到" << endl; } if (it2 != v.end()) { cout << "找到了" << it2->m_Name << " " << (*it2).m_Age << endl; } else { cout << "未找到" << endl; } } int main() { test01(); test02(); system("pause"); return 0; }
运行结果:
find_it 底层代码
只要是调用传入的函数(条件),所以无需重载操作符,只需要在函数或者仿函数里写清楚条件就可以,返回类型要能进行判断,所以为 bool 类型
adjacent_find
功能:
- 查找相邻重复元素,返回相邻元素的第一个位置的迭代器,没找到返回结束迭代器
函数原型:
adjacent_find(iterator beg, iterator end);
beg —— 开始迭代器
end —— 结束迭代器
功能:
- 查找相邻重复元素,返回相邻元素的第一个位置的迭代器,没找到返回结束迭代器
函数原型:
adjacent_find(iterator beg, iterator end);
beg —— 开始迭代器
end —— 结束迭代器
测试代码:
#includeusing namespace std; #include #include void test() { vector v; v.push_back(10); v.push_back(20); v.push_back(10); // 相邻 v.push_back(10); // 相邻 v.push_back(40); v.push_back(30); vector ::iterator it = adjacent_find(v.begin(), v.end()); if (it != v.end()) { cout << "find " << *it << endl; } else { cout << "no find" << endl; } } int main() { test(); system("pause"); return 0; }
运行代码:
binary_search
功能:
- 查找指定元素是否存在,存在返回 true ,不存在返回 false
函数原型:
bool binary_search(iterator beg, iterator end, value);
beg —— 开始迭代器
end —— 结束迭代器
value —— 查找的元素
注意:在 无序 、降序 序列中不可用
功能:
- 查找指定元素是否存在,存在返回 true ,不存在返回 false
函数原型:
bool binary_search(iterator beg, iterator end, value);
beg —— 开始迭代器
end —— 结束迭代器
value —— 查找的元素
注意:在 无序 、降序 序列中不可用
测试代码:
#includeusing namespace std; #include #include #include class Person { public: Person(string name, int age) :m_Name(name), m_Age(age) {} int m_Age; string m_Name; }; // 测试 升序 void test01() { vector v; for (int i = 1; i < 11; ++i) { v.push_back(i); } for (vector ::iterator it = v.begin(); it != v.end(); ++it) { cout << *it << " "; // 1 - 10 } cout << endl; int find_x = 9; bool ret = binary_search(v.begin(), v.end(), find_x); if (ret != false) cout << "find it " << find_x << endl; else cout << "no find " << find_x << endl; } // 测试 倒序 void test02() { vector v; for (int i = 10; i > 0; --i) { v.push_back(i); } for (vector ::iterator it = v.begin(); it != v.end(); ++it) { cout << *it << " "; // 10 - 1 } cout << endl; int find_x = 9; bool ret = binary_search(v.begin(), v.end(), find_x); if (ret != false) cout << "find it " << find_x << endl; else cout << "no find " << find_x << endl; } // 测试 无序 void test03() { vector v; v.push_back(1); v.push_back(3); v.push_back(2); v.push_back(0); for (vector ::iterator it = v.begin(); it != v.end(); ++it) { cout << *it << " "; // 1 3 2 0 } cout << endl; int find_x = 3; bool ret = binary_search(v.begin(), v.end(), find_x); // 无序序列结果是未知的 if (ret != false) cout << "find it " << find_x << endl; else cout << "no find " << find_x << endl; } int main() { test01(); test02(); test03(); system("pause"); return 0; }
运行结果:
count
功能:
- 统计元素个数,返回 __int64 (元素出现的次数)
函数原型:
count(iterator beg, iterator end, value);
beg —— 开始迭代器
end —— 结束迭代器
value —— 统计的元素
功能:
- 统计元素个数,返回 __int64 (元素出现的次数)
函数原型:
count(iterator beg, iterator end, value);
beg —— 开始迭代器
end —— 结束迭代器
value —— 统计的元素
Val == *_UFirst,自定义数据类型的判断就需要改变 == 的方式,也就是重载
测试代码:
#includeusing namespace std; #include #include #include class Person { public: Person(string name, int age) :m_Name(name), m_Age(age) {} 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 test01() { vector v; v.push_back(10); v.push_back(30); v.push_back(20); v.push_back(10); int count_x = 10; __int64 nums = count(v.begin(), v.end(), count_x); cout << count_x << "出现次数:" << nums << endl; } // 统计自定义数据类型 void test02() { vector v; Person p1("张三", 19); Person p2("李四", 20); Person p3("王五", 17); Person p4("王五", 17); Person p5("王五", 17); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); v.push_back(p5); Person count_Person("王五", 17); __int64 nums = count(v.begin(), v.end(), count_Person); cout << count_Person.m_Name << " " << count_Person.m_Age << " 出现次数:" << nums << endl; } int main() { test01(); test02(); system("pause"); return 0; }
运行结果:
count_if
功能:
- 按条件统计元素个数,返回 __int64 (元素出现次数)
函数原型:
count_if(iterator beg, iterator end, _Pred);
beg —— 开始迭代器
end —— 结束迭代器
_Pred —— 谓词(仿函数)、函数
功能:
- 按条件统计元素个数,返回 __int64 (元素出现次数)
函数原型:
count_if(iterator beg, iterator end, _Pred);
beg —— 开始迭代器
end —— 结束迭代器
_Pred —— 谓词(仿函数)、函数
测试代码:
#includeusing namespace std; #include #include #include class Person { public: Person(string name, int age) :m_Name(name), m_Age(age) {} string m_Name; int m_Age; }; // 自定义数据类型 count_if 仿函数 class Person_find { public: bool operator()(const Person& p) { if (p.m_Age > 18) return true; else return false; } }; // 内置数据类型 count_if 仿函数 class my_find { public: bool operator()(const int& x) { if (x > 2 && x < 5) return true; else return false; } }; // 内置数据类型 count_if void test01() { vector v; v.push_back(5); v.push_back(1); v.push_back(2); v.push_back(4); // √ v.push_back(3); // √ __int64 nums = count_if(v.begin(), v.end(), my_find()); cout << "满足大于 2 小于 5 条件的数: " << nums << endl; // 2 } // 自定义数据类型 count_if void test02() { vector v; Person p1("李四", 19); Person p2("张三", 20); Person p3("王五", 15); Person p4("李华", 10); v.push_back(p1); // √ v.push_back(p2); // √ v.push_back(p3); v.push_back(p4); __int64 nums = count_if(v.begin(), v.end(), Person_find()); cout << "成年人数为:" << nums << endl; // 2 } int main() { test01(); test02(); system("pause"); return 0; }
运行额结果: