C++(22):STL之泛型算法初步

2017-01-01 12:34:54来源:CSDN作者:qcyfred人点击

这篇文章里的东西,都是需要猛学的,需要花时间去积淀,去总结……

PKU的110米栏飞人胡翼给我吐血推荐《STL源码剖析》……


Algorithms


Generic & rich standalone template functions
– Operate on containers
– Perform container access through iterators
– Generally unaware of containers


Category of Algorithms
– non-mutating sequence algorithm
– mutating algorithms
– sorting/searching algorithms
– generalized numeric algorithms

……


Non-mutating Sequence Algorithms


Apply to sequence containers
– NOT modify container’s contents
– search for elements in sequences, check for equality and to count sequence elements

Include:
– for_each(), count(), mismatch(), equal(), search(), find(), adjacent_find(), find_if(), find_end() and more.


find


对于C语言风格的字符串中字符的查找。
	char * str = "S12/0/0";	cout<<str<<endl;	int len = strlen(str);	cout<<"字符串长度"<<len<<endl;	char * pos = find(&str[0], &str[len],'S');	cout<<pos<<endl;	cout<<*pos<<endl;
字符串长度是3(从第一位开始,直到"/0"。显式地写,就是直到'/0',否则就是直到编译器自动添加的'/0')。char * pos = find(&str[0], &str[len],'S'); // 从哪里,到哪里,找谁。
cout<<指向C语言风格字符串的指针; 将输出从指针指向的那一位开始的char,直到'/0';(这个‘/0’可以显式地人为添加,也可以让编译器自动添加…)// 毕竟C语言风格的字符串是连续存储的吧…cout<<*pos; // 输出这个指针指向的char变量了。
对于string中某字符的查找
	string s1 = "cdeabcdeabcd";	string::iterator it = find(s1.begin(),s1.end(),'a'); // 返回指向'a'的迭代器(指针)	for (;it!=s1.end();it++)	{		*it = toupper(*it); // 变成大写		cout<<*it;	}
返回的是迭代器(其实也就是个指针)
对于int型数组中某个元素的查找
	const int N = 10;	int iarray[N] = {1,2,3,4,5,6,7,8,9,10};	int * res = find(iarray,iarray+(N-1),5);	cout<<*res<<endl;
也是返回指针了…find是一种generic algorithm……
对于vector元素中的查找
	vector<int> iv;	// vector<int> :: iterator it2;	for (int i = 0; i<20; i++)		iv.push_back(i*20);	vector<int>::const_iterator pos2;	pos2 = find(iv.begin(),iv.end(),40); // *pos=??	if (pos2!=iv.end())	{		cout<<"找到了"<<*pos2<<endl;	}


find_if


带有条件的查找。e.g. 在一堆数中,找到第一个比60大的数
	// findif ... 带有条件地查找	pos2 = find_if(iv.begin(),iv.end(),gt60()); // 带有条件地查找!	if (pos2!=iv.end())	{		cout<<"找到了"<<*pos2<<endl;	}
最后的条件,要带上一个function object(functor)。仿函数,用class的样子去写,用重载运算符的样子去写。
// 仿函数 functorclass gt60 {public:	bool operator() (int x) {		return x > 60;	}};


Mutating Sequence Algorithms


Modify contents of containers
Many have
– if version: perform actions only if data member evaluates to be true
– copy version: copy output to new containers
Include:
– copy(), copy_backward(), swap(), fill(), generate(), partition(), replace(), reverse(), rotate(), swap_ranges(), transform(), unique() and more.

copy

	vector <int> v1;	v1.push_back(1);	v1.push_back(11);	v1.push_back(21);	v1.push_back(31);	cout<<"v1/n";	for (int i : v1)	{		cout<<i<<" ";	}	cout<<"/n";		// vector<int> v2; // 直接这么写,是错的!	// copy(v1.begin(),v1.end(),v2.begin()); 	// v2 现在一个都还没有! 现在 v2的容量为0!!!		vector <int> v2(v1.size());	copy(v1.begin(),v1.end(),v2.begin()); 		cout<<"v2/n";	for (int i : v2)	{		cout<<i<<" ";	}	cout<<"/n";
注意,用copy之前,一定要确保目标的capacity足够大!!!!!

copy_backward

	// -_-! 什么情况……	copy_backward(v1.begin(),v1.end(),v3.end()); // v3不能写begin!要写end!	cout<<"v3/n";	for (int i : v3)	{		cout<<i<<" ";	}	cout<<"/n";
反向copy,要从v3.end()反向copy回来!不能写begin!但实际上,v3的顺序还是和v1的顺序是一样的。那就不知道为什么还会有copy_backward这个函数了……
	vector <int> v4 (3);	copy(v1.begin(),v1.begin()+3,v4.begin()); // 从 begin 到 begin+3,居然只有3个元素! 好神奇!	// end指的是最后一个的下一个	// end - begin 是整个容器一共有多少个元素!	// 好神奇!
copy的参数只能这样理解了。对于string,vector,list这些,开始是什么,结束的下一个元素是什么,这一段要放到目标容器的哪个起始位置对于普通的int [], char [], ...

Sorting/Searching Algorithms

Used to either search or sort container contentsVersions
– use < operator for comparison
– use user-defined comparison functor(此处暂未涵盖)
Inlcude
– sort(), stable_sort(), partial_sort(), nth_element(), merge(), equal_range(), binary_search(), lower_bound() and more.

sort

	int iArray[] = {3,4,5,6,1};	sort(iArray,iArray+4,comp());	for (auto i:iArray)	{		cout<<i<<" ";	}	cout<<"/n";
对于int[], char[] 简单数据类型,开始位置,last one,比较方式。对于string, vector, list, 这些类型,开始位置,the one past last one,比较方式。comp也是一个functor。
class comp{public:	bool operator() (int x, int y) {		return x>y;	}};
现有一需求。高考成绩排序。2011年重庆高考理科总分750分,本人高考562分,语文93,数学112,英语124,理综233,垫着底进了重庆邮电通信学院。。。只能说,……,我也不能说什么……,毕竟现在没什么资格说什么……据说,高考成绩的排序方式是这样的。总分优先,数学优先,理综优先,语文优先,英语优先……现:有一个list<Stu> stu_list; 如何根据上述需求排序?解答:用functor吧……



最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台