ITKeyword,专注技术干货聚合推荐

注册 | 登录

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

taotaoah 分享于 2016-08-04

推荐:C++ STL 算法列表

非修改性序列操作:   all_of  Test condition on all elements in range    any_of  Test if any element in range fulfills condition    none_of  Test if no

2020腾讯云共同战“疫”,助力复工(优惠前所未有!4核8G,5M带宽 1684元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1054

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

常用的查找算法如下:


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

//

推荐:c++之STL(13) STL 算法 - 查找算法(2)search_n() search_n(b, e, c, v) search_n(b, e, c, v, p)

search_n() 用来查找连续的n个匹配的数值 或者 加谓词 search_n(b, e, c, v) search_n(b, e, c, v, p) 注意:该方法的第二种形式应该是search_n_if(b, e, c, p)

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



推荐:C++ STL相关的一些算法

sort()基于快速排序:是不稳定排序 使用方法1:sort(v.begin(),v.end()) 排序方式:从小到大 使用方法2:sort(v.begin(),v.end(),greater<int>()) 排序方式:从

常用的查找算法如下: find() find_if() // search_n() search() find_end() find_first_of() adjacent_find() // 这两种方法通用,对所有容器试用,但是查找效率慢,是线性查找 find() 此复杂

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。