常用查找算法
程序员文章站
2022-07-12 14:36:20
...
1.find:查找元素
功能:查找指定元素,找到返回指定元素的迭代器,找不到返回迭代器end()
#include "pch.h"
#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;
//find查找内置数据类型
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 << "没找到!" << endl;
}
else {
cout << "找到:" << *it << endl;
}
}
//查找自定义数据类型
class person {
public:
person(int age,string name) {
this->m_age = age;
this->m_name = name;
}
//重载==,让底层find知道如何对比
bool operator==(const person&p) {
if (this->m_name == p.m_name &&this->m_age == p.m_age) {
return true;
}
else {
return false;
}
}
int m_age;
string m_name;
};
void test02() {
vector<person> v2;
//创建数据
person p1(10,"aa");
person p2(10, "bb");
person p3(10, "cc");
person p4(10, "dd");
//放入容器
v2.push_back(p1);
v2.push_back(p2);
v2.push_back(p3);
v2.push_back(p4);
vector<person>::iterator it2 = find(v2.begin(), v2.end(), p2);
if (it2 == v2.end()) {//直接等等号,这是自定义类型,不能直接等于判断,应该在类中重载等号
cout << "没找到!" << endl;
}
else {
cout << "找到:" << it2->m_name << endl;
}
}
2.find_if:按条件查找元素
//常用查找算法find_if
//查找内置数据类型
class greatefive {
public:
bool operator()(int val) {
return val > 5;
}
};
void test01() {
vector<int> v3;
for (int i = 0; i < 10; i++) {
v3.push_back(i);
}
//查找容器中 是否有5这个元素
vector<int>::iterator it3 = find_if(v3.begin(), v3.end(), greatefive());
if (it3 == v3.end()) {
cout << "没找到!" << endl;
}
else {
//cout << "找到:" << *it3 << endl;
}
}
//查找自定义数据类型
class greatefive {
public:
bool operator()(person&p) {
return p.m_age > 20;
}
};
class person {
public:
person(int age, string name) {
this->m_age = age;
this->m_name = name;
}
//重载==,让底层find知道如何对比
bool operator==(const person&p) {
if (this->m_name == p.m_name &&this->m_age == p.m_age) {
return true;
}
else {
return false;
}
}
int m_age;
string m_name;
};
void test02() {
vector<person> v2;
//创建数据
person p1(10, "aa");
person p2(10, "bb");
person p3(10, "cc");
person p4(10, "dd");
//放入容器
v2.push_back(p1);
v2.push_back(p2);
v2.push_back(p3);
v2.push_back(p4);
vector<person>::iterator it2 = find_if(v2.begin(), v2.end(), greatefive());
if (it2 == v2.end()) {//直接等等号,这是自定义类型,不能直接等于判断,应该在类中重载等号
cout << "没找到!" << endl;
}
else {
cout << "找到:" << it2->m_name << endl;
}
}
3.adjacent_find:查找相邻重复元素
//查找相邻重复元素adjacent_find
void test01() {
vector<int> v3;
for (int i = 0; i < 10; i++) {
v3.push_back(i);
}
//查找容器中 是否有5这个元素
vector<int>::iterator it3 = adjacent_find(v3.begin(), v3.end());
if (it3 == v3.end()) {
cout << "没找到!" << endl;
}
else {
//cout << "找到:" << *it3 << endl;
}
}
4.binary_search:二分查找法,查找指定元素是否存在,不可用于无序序列中,查到返回true,否则false
void test01() {
vector<int> v3;
for (int i = 0; i < 10; i++) {
v3.push_back(i);
}
bool it3 = binary_search(v3.begin(), v3.end(),9);
if (it3 ) {
cout << "找到!" << endl;
}
else {
cout << "未找到:" << endl;
}
}
5.count:统计元素个数
//统计元素类型
void test01() {
vector<int> v3;
for (int i = 0; i < 10; i++) {
v3.push_back(i);
}
int num = count(v3.begin(), v3.end(), 2);
cout << "2的元素个数" << num << endl;
}
//统计自定义类型
class person {
public:
person(int age, string name) {
this->m_age = age;
this->m_name = name;
}
//重载
bool operator==(const person&p) {
if (this->m_age == p.m_age) {
return true;
}
else {
return false;
}
}
int m_age;
string m_name;
};
void test02() {
vector<person> v2;
//创建数据
person p1(10, "aa");
person p2(10, "bb");
person p3(10, "cc");
person p4(10, "dd");
//放入容器
v2.push_back(p1);
v2.push_back(p2);
v2.push_back(p3);
v2.push_back(p4);
int num = count(v2.begin(), v2.end(), p1);
cout << "p1同岁数的人数" << num << endl;
}
6.count_if:按条件统计元素个数
//按条件统计元素个数count_if
//统计自定义数据类型
class greatefive {
public:
bool operator()(const person&p) {
return p.m_age > 20;
}
};
class person {
public:
person(int age, string name) {
this->m_age = age;
this->m_name = name;
}
//重载
bool operator==(const person&p) {
if (this->m_age == p.m_age) {
return true;
}
else {
return false;
}
}
int m_age;
string m_name;
};
void test02() {
vector<person> v2;
//创建数据
person p1(10, "aa");
person p2(10, "bb");
person p3(10, "cc");
person p4(10, "dd");
//放入容器
v2.push_back(p1);
v2.push_back(p2);
v2.push_back(p3);
v2.push_back(p4);
int num = count_if(v2.begin(), v2.end(), greatefive());
cout << "大于p1的人数" << num << endl;
}
//统计内置数据类型
class greatefive {
public:
bool operator()(int val) {
return val > 20;
}
};
void test01() {
vector<int> v3;
for (int i = 0; i < 10; i++) {
v3.push_back(i);
}
int num = count_if(v3.begin(), v3.end(), greatefive());
cout << "大于20的元素个数" << num << endl;
}