STL常用算法——查找算法

2023-05-16

文章目录

STL常用算法——查找算法
- 1、find()
- 2、find_if()
- 3、adjacent_find()
- 4、binary_search()
- 5、count()和count_if()
- - 5.1、count()
  - 5.2、count_if()

STL常用算法——查找算法

1、find()

find() 函数是一个模板函数，用于在指定范围内查找和目标元素值相等的第一个元素。

函数原型：

find(iterator beg,iterator end,value);

参数说明：

beg和 end：开始和结束迭代器
[beg, end)：指定该函数的查找范围
value：查找的目标元素

find() 函数会返回一个输入迭代器，当 find() 函数查找到目标元素时，其指向查找到的第一个目标元素位置迭代器；如果查找失败，则该迭代器的指向和 end相同。

find()函数的底层实现就是用==运算符将目标值和查找范围内的元素逐个进行比对。

查找内置数据类型

void test01() {
	vector<int> v;
	for (int i = 0;i < 10;i++) {
		v.push_back(i);
	}
	//查找容器中是否有3这个元素
	vector<int>::iterator it = find(v.begin(), v.end(), 3);
	if (it != v.end()) {
		cout << "容器中有3这个元素" << endl;
	}
	else {
		cout << "容器中没有3这个元素" << endl;
	}
}

查找自定义数据类型

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<string>

class Person {
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}
	//重载==运算符,find()函数的底层实现就是用==运算符将目标值和查找范围内的元素逐个进行比对
	bool operator ==(const Person &p) {
		if ((this->name == p.name) && (this->age == p.age)){
			return true;
		}
		else{
			return false;
		}
	}
	string name;
	int age;
};
void test02() {
	vector<Person> v1;
	Person p1("张三", 13);
	Person p2("李四", 14);
	Person p3("王五", 15);
	Person p4("赵六", 16);
	v1.push_back(p1);
	v1.push_back(p2);
	v1.push_back(p3);
	v1.push_back(p4);

	vector<Person>::iterator it = find(v1.begin(), v1.end(), p2);
	if (it == v1.end()) {
		cout << "容器中没有p2这个元素" << endl;
	}
	else {
		cout << "姓名："<<it->name<<"年龄："<<it->age << endl;
	}
}
int main() {
	test02();
	system("pause");
	return 0;
}

在这里插入图片描述

2、find_if()

find_if() 函数用于在指定区域内执行查找操作。

和find() 函数不同的是，find() 函数需要明确指定要查找的元素的值，而find_if() 允许自定义条件来查找元素。

函数原型：

find_if(iterator beg,iterator end,_Pred);

参数说明：

beg 开始迭代器
end 结束迭代器
_Pred 函数或一元谓词函数（有一个形参且返回值类型为 bool 的仿函数）

当 find_if() 函数查找到目标元素时，其指向查找到的第一个目标元素位置迭代器；如果查找失败，则该迭代器的指向和 end相同。

查找内置数据类型

//自定义查找规则
class GreaterFive {
public:
	bool operator()(int val) {
		return val > 5;
	}
};
void test01() {
	vector<int> v;
	v.push_back(1);
	v.push_back(3);
	v.push_back(5);
	v.push_back(7);
	v.push_back(9);
	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
	if (it != v.end()) {
		cout << "找到了大于5的数字" << endl;
		cout << "在这个容器中第一个大于5的数字是" << *it << endl;
	}
}

自定义查找元素规则

#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>

class Person{
public:
	Person(string name, int age) {
		this->name = name;
		this->age = age;
	}
	string name;
	int age;
};
//自定义查找元素规则函数对象
class Greater20 {
public:
	bool operator()(const Person& p) {
		return p.age > 20;
	}
};

void test01() {
	vector<Person> v;
	Person p1("张三", 13);
	Person p2("李四", 14);
	Person p3("王五", 23);
	Person p4("赵六", 24);
	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 << "在容器v中找到年龄大于20的人" << endl;
		cout << "第一个的姓名为" << (*it).name << " 年龄为 " << (*it).age << endl;
	}
	else {
		cout << "没有找到年龄大于20的" << endl;
	}
}

int main() {
	test01();
	system("pause");
	return 0;
}

在这里插入图片描述

find_if_not()

find_if_not() 函数和 find_if() 函数的功能恰好相反，用于查找第一个不符合查找规则的目标元素。

find_if_not()函数的返回和 find_if() 函数相同。

// 一元谓词函数作为查找规则
bool mycomp(int i) {
	return ((i % 2) == 1);
}
void test01() {

	vector<int> v{ 4,2,3,1,5 };
    //查找不符合 (i%2)==1的元素，并返回一个指向该元素的迭代器
	vector<int>::iterator it = find_if_not(v.begin(), v.end(), mycomp);
	cout << "*it = " << *it << endl; //*it = 4
}

3、adjacent_find()

adjacent_find() 函数用于在指定范围内查找 2 个连续相等的元素。

函数原型：该函数有以下两种语法格式

//查找 2 个连续相等的元素
adjacent_find(iterator beg,iterator end);
//查找 2 个连续满足 pred 规则的元素
adjacent_find(iterator beg,iterator end,BinaryPredicate pred);

参数说明：

beg 开始迭代器
end 结束迭代器
pred：接收一个包含 2 个参数且返回值类型为 bool 的函数，以实现自定义查找规则。

adjacent_find()函数会返回一个迭代器，当查找成功时，该迭代器指向的是连续相等元素的第 1 个元素；而如果查找失败，该迭代器的指向和 end 迭代器相同。

#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>

//以函数对象的形式定义一个查找规则
class mycomp {
public:
	bool operator()(const int& _Left, const int& _Right) {
		return (_Left == _Right);
	}
};

void test01() {
	vector<int> v{3,2,1,5,5,6,7,7};

	//查找 2 个连续相等的元素
	vector<int>::iterator it = adjacent_find(v.begin(), v.end());
	if (it != v.end()) {
		cout << "找到了重复相邻元素" << endl;
		cout << "最早的相邻元素为" << *it << endl;
	}
	else {
		cout << "没有重复的相邻元素" << endl;
	}
	//查找 2 个连续满足 pred 规则的元素
	it = adjacent_find(++it, v.end(), mycomp());
	if (it != v.end()) {
		cout << "相邻元素为 " << *it;
        cout << endl;
	}
}
int main() {
	test01();
	system("pause");
	return 0;
}

在这里插入图片描述

4、binary_search()

binary_search() 函数用于查找指定范围内是否包含某个目标元素。

函数原型：该函数有以下两种语法格式

//查找 [beg, end) 区域内是否包含 value
bool binary_search (iterator beg,iterator end,value);
//根据 comp 指定的规则，查找 [beg, end) 区域内是否包含 value
bool binary_search (iterator beg,iterator end,value, Compare comp);

参数说明：

beg 开始迭代器
end 结束迭代器
value 查找的元素
comp 用于自定义查找规则的普通函数或函数对象。此函数接收一个包含 2 个形参且返回值为 bool 类型

如果 binary_search() 函数在 [beg, end) 区域内找到目标元素，则返回 true；反之返回 false。

binary_search() 底层实现采用的是二分查找的方式，在无序序列中查找是时好时坏，结果不稳定。因此该函数仅适用于“已排好序”的序列，在无序序列中不可用。

#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>

//以函数对象的形式定义查找规则
class mycomp {
public:
	bool operator()(const int& i, const int& j) {
		return i > j;
	}
};

void test01() {
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	//从 v 容器查找元素 9
	bool res = binary_search(v.begin(), v.end(), 9);
	cout << "res：" << res << endl; //res：1
	vector<int> v1{ 6,5,3,1,7 };
	//从 v1 容器查找元素 3
	bool res1 = binary_search(v1.begin(), v1.end(), 3, mycomp());
	cout << "res1：" << res1 << endl; //res1：1
}
int main() {
	test01();
	system("pause");
	return 0;
}

5、count()和count_if()

5.1、count()

count()函数：统计区域内目标元素的个数

函数原型：

count(iterator beg,iterator end,value);

参数说明：

beg 开始迭代器
end 结束迭代器
value 统计的目标元素

#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>

//1.统计内置数据类型个数
void test01() {
	vector<int> v{2,4,6,7,4,2,4};
	int num = count(v.begin(), v.end(), 2);
	int num1 = count(v.begin(), v.end(), 4);
	cout << "容器中2的个数为：" << num << endl;
	cout << "容器中4的个数为：" << num1 << 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_Name == p.m_Name) && (this->m_Age == p.m_Age)) {
			return true;
		}
		else {
			return false;
		}
	}
	string m_Name;
	int m_Age;
};
void test02() {
	Person p1("a", 13);
	Person p2("b", 23);
	Person p3("s", 23);
	Person p4("c", 23);
	Person p5("h", 23);
	Person p6("a", 13);
	Person p7("a", 13);
	vector<Person> v{p1,p2,p3,p4,p5,p6,p7};
	Person p("a", 13);
	int num = count(v.begin(), v.end(), p);
	cout << "姓名为a年龄为13的有" << num << "个" << endl;
}
int main() {
	test01();
	test02();
	system("pause");
	return 0;
}

5.2、count_if()

count_if()：按自定义规则统计范围内目标元素的个数

函数原型：

count_if(iterator beg,iterator end,_Pred);

参数说明：

beg 开始迭代器
end 结束迭代器
_Pred 函数或一元谓词函数

//1.统计内置数据类型
class Greater3 {
public:
	bool operator()(int val) {
		return val > 3;
	}
};
void test01() {
	vector<int> v{2,2,4,6,7,2};
	int num = count_if(v.begin(), v.end(), Greater3());
	cout << "容器中大于3的个数为：" << num << endl; //容器中大于3的个数为：3
}

//2.统计自定义数据类型
class Person {
public:
	Person(string name, int age) {
		this->m_Name = name;
		this->m_Age = age;
	}
	string m_Name;
	int m_Age;
};
class MyCompare30 {
public:
	bool operator()(const Person& p) {
		if (p.m_Age > 30) {
			return true;
		}
		else {
			return false;
		}
	}
};
void test02() {
	
	Person p1("a", 13);
	Person p2("b", 23);
	Person p3("s", 33);
	Person p4("c", 43);
	Person p5("h", 53);
	Person p6("a", 13);
	Person p7("a", 63);
	vector<Person> v{p1,p2,p3,p4,p5,p6,p7};
	int num = count_if(v.begin(), v.end(), MyCompare30());
	cout << "年龄大于30的人员个数：" << num << endl; //年龄大于30的人员个数：4
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)