• STL常用算法——查找算法

    文章目录

    STL常用算法——查找算法

    1、find()

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

    函数原型：

    find(iterator beg,iterator end,value);

    • 1

    参数说明：

    • 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;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    查找自定义数据类型

    #include
using namespace std;
#include
#include
#include

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;
}

    • 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

    在这里插入图片描述

    2、find_if()

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

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

    函数原型：

    find_if(iterator beg,iterator end,_Pred);

    • 1

    参数说明：

    • 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;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    自定义查找元素规则

    #include
using namespace std;
#include
#include

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;
}

    • 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

    在这里插入图片描述

    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
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    3、adjacent_find()

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

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

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

    • 1
    • 2
    • 3
    • 4

    参数说明：

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

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

    #include
using namespace std;
#include
#include

//以函数对象的形式定义一个查找规则
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;
}

    • 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

    在这里插入图片描述

    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);

    • 1
    • 2
    • 3
    • 4

    参数说明：

    • beg 开始迭代器

    • end 结束迭代器

    • value 查找的元素

    • comp 用于自定义查找规则的普通函数或函数对象。此函数接收一个包含 2 个形参且返回值为 bool 类型

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

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

    #include
using namespace std;
#include
#include

//以函数对象的形式定义查找规则
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;
}

    • 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

    5、count()和count_if()

    5.1、count()

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

    函数原型：

    count(iterator beg,iterator end,value);

    • 1

    参数说明：

    • beg 开始迭代器
    • end 结束迭代器
    • value 统计的目标元素
    #include
using namespace std;
#include
#include

//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;
}

    • 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

    5.2、count_if()

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

    函数原型：

    count_if(iterator beg,iterator end,_Pred);

    • 1

    参数说明：

    • 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
}

    • 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
  • 相关阅读:
    Codeforces Round #823 (Div. 2) A-D
    docker 基本命令
    让两个电脑通信的方法（TCP连接，UDP连接，C/S架构）
    本地数据库迁移到云端服务器
    CSS 字体
    深度学习(part7)--Keras常用模块
    idea内存不足
    将dumpbin从VS中抠出来，并使用dumpbin查看exe和dll库的依赖关系
    【自然语言处理】【可解释性】NKB：用于预训练Transformers的神经知识银行
    linux网络-ARP协议
  • 原文地址：https://blog.csdn.net/wpc2018/article/details/127611803