c++之STL(13) STL 算法 - 查找算法（1）

常用的查找算法如下：

find()

find_if()

//

search_n()

search()

find_end()

find_first_of()

adjacent_find()

//

這兩種方法通用，對所有容器試用，但是查找效率慢，是線性查找

find() 此複雜度是線性複雜度

find_if() 此複雜度是線性複雜度

注意：

1，如果是已序區間，可以使用  已序區間查找算法(binary_search includes()  lower_bound()  upper_bound())。

2，關聯式容器（set multiset map multimap）有等效的成員函數find() , 此find()複雜度是對數複雜度，速度快

3,，string有等效的成員函數find()

//

#include<iostream>
#include<algorithm>
#include<list>

using namespace std;

int main()
{
	list<int> ilist;
	for (int i = 1; i <= 8; i++)
	{
		ilist.insert(ilist.end(), i);
	}
	for (int i = 1; i <= 8; i++)
	{
		ilist.insert(ilist.end(), i);
	}
	for (list<int>::iterator iter = ilist.begin(); iter != ilist.end(); iter++)
	{
		cout << *iter << ' ';
	}
	cout << endl;

	list<int>::iterator pos1;
	pos1 = find(ilist.begin(), ilist.end(), 4);
	list<int>::iterator pos2;
	if (pos1 != ilist.end())
	{
		pos2 = find(++pos1, ilist.end(), 4);
	}
	else
		cout << "沒找到 4！" << endl;
	if (pos1 != ilist.end() && pos2 != ilist.end())
	{
		--pos1;
		++pos2;
		for (list<int>::iterator iter = pos1; iter != pos2; iter++)
			cout << *iter;
	}
	cout << endl;

	//
	system("pause");
	return 0;
}
           

#include<iostream>
#include<algorithm>
#include<vector>
//
#include<functional>

using namespace std;

int main()
{
	vector<int> ivec;
	vector<int>::iterator pos;

	for (int i = 1; i <= 9; i++)
		ivec.push_back(i);
	for (vector<int>::iterator iter = ivec.begin(); iter != ivec.end(); iter++)
		cout << *iter << ' ';
	cout << endl;

	pos = find_if(ivec.begin(), ivec.end(), bind2nd(greater<int>(), 3));	// 函數對象是 > 3

	cout << *pos << endl;

	// modulus  取模運算
	pos = find_if(ivec.begin(), ivec.end(), not1(bind2nd(modulus<int>(), 3)));
	cout << *pos << endl;
	//
	system("pause");
	return 0;
}
           

//

預定義的函數對象：

negate<type>()    equal_to<type>()     plus<type>()       not_equal_to<type>()       minus<type>()  less<type>()  

multiplies<type>()  greater<type>()   divides<type>()  less_equal<type>()  modulus<type>()

greater_equal<type>()  logical_not<type>()  logical_and<type>()  logical_or<type>()

預定義的函數擴充卡

bindlst(op, value)

bind2nd(op, value)

not1(op)

not2(op)

mem_fun(op) 

ptr_fun(op)

已序區間查找算法

binary_search()

includes()

lower_bound()

upper_bound()

#include<iostream>
#include<set>
//
using namespace std;

int main()
{
	// set 自動排序，是自動平衡的進階的紅黑樹
	set<int> iset;
	iset.insert(43);
	iset.insert(78);
	iset.insert(-1);
	iset.insert(124);

	for (set<int>::iterator iter = iset.begin(); iter != iset.end(); iter++)
		cout << *iter << ' ';
	cout << endl;

	set<int>::iterator pos;
	pos = iset.find(78);	// find  是set  的 成員 函數
	if (pos != iset.end())
	{
		cout << "找到了！" << *pos << endl;
	}
	else
	{
		cout << "沒找到！" << endl;
	}
	//
	system("pause");
	return 0;
}
           

#include<iostream>
#include<string>
//
using namespace std;

int main()
{
	string s("AnnaBelle");
	string::size_type pos = s.find("Belle");
	
	pos = s.find("bell");
	if (pos != string::npos)
		cout << "找到了！" << pos << endl;
	else
		cout << "沒找到！" << endl;
	//
	system("pause");
	return 0;
}