STL算法——常用查找算法（find、find_if、adjacent_find、binary_search、count、count_if）

5.2 常用查找算法

學習目标：

掌握常用的查找算法

算法簡介：

find //查找元素
find_if //按條件查找元素
adjacent_find //查找相鄰重複元素
binary_search //二分查找法
count //統計元素個數
count_if //按條件統計元素個數

5.2.1 find

功能描述：

查找指定元素，找到傳回指定元素的疊代器，找不到傳回結束疊代器

函數原型：

find(iterator beg, iterator end, value);
- 按值查找元素，找到傳回指定位置疊代器，找不到傳回結束疊代器位置
- beg 開始疊代器
- end 結束疊代器
- value 查找的元素

示例：

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

//查找 find

class Person {
public:
	string m_name;
	int m_age;

	Person(string name, int age) {
		this->m_name = name;
		this->m_age = age;
	}
	
	//重寫==操作符，為了底層 find 如何對比
	//可以寫入一個元素查找，或者直接輸入自定義類型查找
	//看個人需求
	bool operator==(const string name) {
		return this->m_name == name;
	}

};

//内置資料類型查找
void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	
	//利用疊代器接收查找到的資料
	vector<int>::iterator it = find(v.begin(), v.end(), 40);

	if (it != v.end()) {
		cout << "找到了：" << *it << endl;
	}
	else {
		cout << "沒有找到" << endl;
	}
}

//自定義資料類型查找
void test02() {
	vector<Person> v;

	//建立資料
	Person p1("張三", 10);
	Person p2("李四", 20);
	Person p3("王五", 30);
	Person p4("趙六", 10);

	//加入容器
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	//查找
	//若不重寫，find 不知道比較哪一個元素
	vector<Person>::iterator it = find(v.begin(), v.end(), "李四");

	if (it != v.end()) {
		cout << "找到了，姓名：" << (*it).m_name << " 年齡：" << (*it).m_age << endl;
	}
	else {
		cout << "沒找到" << endl;
	}
}


//主函數
int main() {
	test01();
	test02();
	system("pause");
	return 0;
}

總結：利用find可以在容器中找到指定的元素，傳回值是疊代器

5.2.2 find_if

功能描述：

按條件查找元素

函數原型：

find_if(iterator beg, iterator end, _Pred);
- 按值查找元素，找到傳回指定位置疊代器，找不到傳回結束疊代器位置
- beg 開始疊代器
- end 結束疊代器
- _Pred 函數或者謂詞（傳回bool 類型的仿函數）

示例：

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

//按條件查找元素 find_if

//自定義資料類型
class Person {
public:
	string m_name;
	int m_age;
	Person(string name, int age) {
		this->m_name = name;
		this->m_age = age;
	}
};

//寫一個謂詞（内置資料類型判斷）
class GreatThirty {
public:
	bool operator()(int val) {
		return val > 30;
	}
};

//換一種寫法，用函數（自定義資料類型判斷）
bool DIY_GreatTwenty(const Person& p) {
	return p.m_age > 20;
}


//内置資料類型
void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(50);
	v.push_back(40);
	v.push_back(30);

	vector<int>::iterator it = find_if(v.begin(), v.end(), GreatThirty());

	if (it != v.end()) {
		cout << "找到了 大于30 的元素為：" << (*it) << endl;
	}
	else {
		cout << "沒有找到" << endl;
	}
}

//自定義資料類型
void test02() {
	vector<Person> v;

	Person p1("張三", 10);
	Person p2("李四", 20);
	Person p3("王五", 30);
	Person p4("趙六", 40);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	vector<Person>::iterator it = find_if(v.begin(), v.end(), DIY_GreatTwenty);

	if (it != v.end()) {
		cout << "找到了 大于20 的元素,姓名為：" << (*it).m_name << " 年齡為：" << (*it).m_age << endl;
	}
	else {
		cout << "沒有找到" << endl;
	}
}

//主函數
int main() {
	test01();
	test02();
	system("pause");
	return 0;
}

5.2.3 adjacent_find

功能描述：

查找相鄰重複元素

函數原型：

adjacent_find(iterator beg, iterator end);
- 查找相鄰重複元素，傳回相鄰元素的第一個位置的疊代器
- beg 開始疊代器
- end 結束疊代器

示例：

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

//查找相鄰重複元素 adjacent_find
void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(10);
	v.push_back(30);
	v.push_back(30);
	v.push_back(40);

	vector<int>::iterator it = adjacent_find(v.begin(), v.end());

	if (it != v.end()) {
		cout << "找到了相鄰重複元素：" << (*it) << endl;
	}
	else {
		cout << "沒有找到" << endl;
	}
}


//主函數
int main() {
	test01();
	system("pause");
	return 0;
}

5.2.4 binary_search

功能描述：

查找指定元素是否存在

函數原型：

bool binary_search(iterator beg, iterator end, value);
- 查找指定元素，查到傳回true，否則false
- 注意：在無序序列中不可用！，而且隻能用于升序序列例如 set 容器
- beg 開始疊代器
- end 結束疊代器
- value 查找的元素

示例：

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

//二分查找指定元素是否存在 binary_search
void test01() {
	set<int> s;
	s.insert(20);
	s.insert(50);
	s.insert(30);
	s.insert(10);
	s.insert(40);

	if (binary_search(s.begin(), s.end(),50)) {
		cout << "在 set 容器中找到了50" << endl;
	}
	else {
		cout << "在 set 容器中沒有找到" << endl;
	}

	//試用 binary_search 查找無序容器
	vector<int> v;
	v.push_back(50);
	v.push_back(40);
	v.push_back(30);
	v.push_back(20);

	if (binary_search(v.begin(), v.end(), 50)) {
		cout << "在 vector 容器中找到了50" << endl;
	}
	else {
		cout << "在 vector 容器中沒有找到" << endl;
	}
}

//主函數
int main() {
	test01();
	system("pause");
	return 0;
}

總結：二分查找法效率很高，值得注意的是查找的容器中元素必須是有序序列

5.2.5 count

功能描述：

統計元素個數

函數原型：

count(iterator beg, iterator end, value);
- 統計元素出現次數
- beg 開始疊代器
- end 結束疊代器
- value 查找的元素

示例：

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

//統計元素個數 count

//自定義資料類型
class Person {
public:
	string m_name;
	int m_age;
	Person(string name, int age) {
		this->m_name = name;
		this->m_age = age;
	}

	//重載==符号，友善元素查找
	bool operator==(const int val) {
		return this->m_age == val;
	}
};

//内置資料類型
void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(10);
	v.push_back(40);
	v.push_back(10);

	int sum = count(v.begin(), v.end(), 10);
	cout << "容器中10的個數為：" << sum << endl;
}

//自定義資料類型
void test02() {
	vector<Person> v;

	Person p1("張三", 10);
	Person p2("李四", 20);
	Person p3("王五", 30);
	Person p4("趙六", 20);
	Person p5("賈七", 20);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);

	cout << "年齡是20歲的人的個數是：" << count(v.begin(), v.end(), 20) << endl;
}

//主函數
int main() {
	test01();
	test02();
	system("pause");
	return 0;
}

總結：統計自定義資料類型時候，需要配合 operator==

5.2.6 count_if

功能描述：

按條件統計元素個數

函數原型：

count_if(iterator beg, iterator end, _Pred);
- 按條件統計元素出現次數
- beg 開始疊代器
- end 結束疊代器
- _Pred 謂詞

示例：

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

//按條件統計元素個數

//謂詞（尋找小于30）
class LessThirty {
public:
	bool operator()(int val) {
		return val < 30;
	}
};

//統計内置資料類型
void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);

	int sum = count_if(v.begin(), v.end(), LessThirty());

	cout << "小于30的數有 " << sum << " 個" << endl;
}

//主函數
int main() {
	test01();
	system("pause");
	return 0;
}

STL算法——常用查找算法（find、find_if、adjacent_find、binary_search、count、count_if）

5.2 常用查找算法

5.2.1 find

5.2.2 find_if

5.2.3 adjacent_find

5.2.4 binary_search

5.2.5 count

5.2.6 count_if

繼續閱讀

swmm與lisflood-fp源碼如何一起編譯 CMake指令

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

Windows下VS開發環境環境安裝工程項目設定關于Debug和Release的提示

一文看懂字元串的加減乘除

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

C++實作簡單順序表

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列二、優先級規律

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

線性表之順序表的實作

C++判斷素數、求最大公約數代碼判斷一個數是否為素數求兩個數的最大公約數

SequoiaDB巨杉資料庫C++驅動概述

hdu7108哈希