C++ STL（2）--算法(1)

算法(1)----STL里的查找函数，主要分顺序查找和二分查找。

一、顺序查找9个，元素若是对象必须支持 == 运算符。

1. find: 用于在指定范围内查找和目标元素值相等的第一个元素。

find() 函数除了可以作用于序列式容器，还可以作用于普通数组。

代码示例：

	vector<int> v1 = { 8, 3, 5, 4, 1, 6, 2 };
	vector<int>::iterator it = find(v1.begin(), v1.end(), 6);
	if (it != v1.end()) {
		cout << "找到:" << *it << endl;
	}
	else {
		cout << "没找到" << endl;
	}

2. find_end: 在序列 A 中查找序列 B 最后一次出现的位置。

可以传入普通函数或函数对象，作为自定义查找规则。

代码示例：

//以函数对象的形式定义一个匹配规则
class compare {
public:
	bool operator()(const int& i, const int& j) {
		return (i % j == 0);
	}
};
int main() {
	vector<int> v1{ 2,4,6,4,8,12,18,1,2,3 };
	int arr[] = { 2,4,6 };
	vector<int>::iterator it = find_end(v1.begin(), v1.end(), arr, arr + 3, compare());
	if (it != v1.end()) {
		cout << "最后一个被{2,4,6}整除的起始位置为：" << it - v1.begin() << ",*it = " << *it;
	}
	return 0;
}

3. search: 在序列 A 中查找序列 B 第一次出现的位置。

可以传入普通函数或函数对象，作为自定义查找规则。

代码示例：

	vector<int> v1{ 1,2,3,4,1,2,3,8,1,2,3 };
	int arr[] = { 1,2,3 };
	vector<int>::iterator it = search(v1.begin(), v1.end(), arr, arr + 3);
	if (it != v1.end()) {
		cout << "第一个{1,2,3}的起始位置为：" << it - v1.begin() << ",*it = " << *it << endl;
	}

4. search_n: 用于在指定区域内查找第一个符合要求的子序列(里面的元素相同)。

可以传入普通函数或函数对象，作为自定义查找规则。

代码示例：

	vector<int> v1{ 1,2,3,4,6,6,6,8,1,2,6,6,6 };
	vector<int>::iterator it = search_n(v1.begin(), v1.end(), 3, 6);//找{6,6,6}
	if (it != v1.end()) {
		cout << "第一个{6,6,6}的起始位置为：" << it - v1.begin() << endl;
	}

5. find_first_of: 在 A 序列中查找和 B 序列中任意元素相匹配的第一个元素。

可以传入普通函数或函数对象，作为自定义查找规则。

代码示例：

    char a[] = "abcdefg";
	char ch[] = "fc";
	char* it = find_first_of(a, a + 7, ch, ch + 2);
	if (it != a + 7) {
		cout << "找到的第一个是：" <<*it<<",位置是："<<it - a << '\n';
	}

6. find_if: 根据指定的查找规则，在指定区域内查找第一个符合要求的元素。

find_if_not: 和find_if相反，查找第一个不符合要求的元素。

传入普通函数或函数对象，作为自定义查找规则。

代码示例：

class compare {
public:
	bool operator()(const int& i) {
		return ((i % 2) == 1);
	}
};
int main() {
	vector<int> v1{ 4,2,3,1,5 };
	//查找第一个奇数
	vector<int>::iterator it = find_if(v1.begin(), v1.end(), compare());
	cout << "*it = " << *it<<endl;
	//查找第一个非奇数
	it = find_if_not(v1.begin(), v1.end(), compare());
	cout << "*it = " << *it<<endl;
	return 0;
}

7. adjacent_find: 在指定范围内查找最先 2 个连续相等的元素。

可以传入普通函数或函数对象，作为自定义查找规则。

代码示例：

    std::vector<int> v1{ 5,6,6,3,2,1,2,2 };
	auto it = adjacent_find(v1.begin(), v1.end());
	if (it != v1.end()) {
		cout << "找到: " << *it << endl;
	}
	else {
		cout << "没找到. " << endl;
	}

8. count: 统计指定元素的个数

可以传入普通函数或函数对象，作为自定义查找规则。

代码示例：

class AA
{
	int m_v;
public:
	AA(int v) :m_v(v) {

	}
	bool operator == (const AA& other) 
	{
		return other.m_v == m_v;
	}
};
int main() {
	AA a(2);
	std::vector<AA> v1{ 5,6,6,3,2,1,2,2 };
	int num = count(v1.begin(), v1.end(), a);
	cout << "对象AA(2)的个数:" <<num << endl;
	return 0;
}

关联式容器set、map自带成员函数count().

9. count_if: 统计满足条件的元素个数

可以传入普通函数或函数对象，作为自定义查找规则。

bool CompFind(int val)
{
	return val == 6;
}
int main() {
	std::vector<int> v1{ 5,6,6,3,2,1,2,2 };
	int num = count_if(v1.begin(), v1.end(), [](int val) { return val == 2; });
	cout << "数字2的个数:" <<num << endl;

	int num2 = count_if(v1.begin(), v1.end(), CompFind);
	cout << "数字6的个数:" << num2 << endl;
	return 0;
}

二、二分查找4个，元素若是对象必须支持 < 运算符。

仅适用于已排好序的序列。所谓“已排好序”，指的是查找区域内所有令 element<val（或者 comp(element,val)，其中element 为指定范围内的元素）成立的元素都位于不成立元素的前面。

1. lower_bound: 在指定区域内查找不小于目标值的第一个元素。

使用此函数查找，最终找到的是大于或等于目标值的元素。

代码示例：

	vector<int> v1{ 2,1,4,5,9,6,8 };
	vector<int>::iterator it = lower_bound(v1.begin(), v1.end(), 3);
	if (it != v1.end()) {
		cout << "找到:" << *it;
	}

2. upper_bound: 在指定范围内查找大于目标值的第一个元素。

代码示例：

vector<int> v1{ 2,1,4,5,9,6,8 };
	vector<int>::iterator it = upper_bound(v1.begin(), v1.end(), 4);
	if (it != v1.end()) {
		cout << "找到:" << *it;
	}

3. equal_ranage: 用于在指定范围内查找等于目标值的所有元素。

实现调用的是lower_bound和upper_bound。

代码示例：

class compare {
public:
	bool operator()(const int& i, const int& j) {
		return i > j;
	}
};
int main() {
	vector<int> v1{ 7,8,9,6,6,6,3,2,1,5,4 };
	pair<vector<int>::iterator, vector<int>::iterator> range2;
	//在容器中找到所有的元素6
	range2 = equal_range(v1.begin(), v1.end(), 6, compare());
	for (auto it = range2.first; it != range2.second; ++it) {
		cout << *it << " ";
	}
	return 0;
}

说明：v1容器中存储的序列虽然整体是乱的，但对于目标元素 6 来说，所有符合 compare(element, 6) 规则的元素都位于其左侧，不符合的元素都位于其右侧，因此认为有序。

4. binary_search: 查找指定区域内是否包含某个目标元素。

实现调用的是lower_bound。

代码示例：

class compare {
public:
	bool operator()(const int& i, const int& j) {
		return i > j;
	}
};
int main() {
	vector<int> v1{ 6,4,5,1,2,0 };
	//从容器查找元素 3
	bool hasElem = binary_search(v1.begin(), v1.end(), 3, compare());
	cout << "hasElem:" << hasElem;
	return 0;
}