C++（22）：STL初步之泛型算法

2017-01-01 21:44:36来源: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

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;

cout<<指向C语言风格字符串的指针; 将输出从指针指向的那一位开始的char，直到'/0';（这个‘/0’可以显式地人为添加，也可以让编译器自动添加…）// 毕竟C语言风格的字符串是连续存储的吧…cout<<*pos; // 输出这个指针指向的char变量了。

string s1 = "cdeabcdeabcd";	string::iterator it = find(s1.begin(),s1.end(),'a'); // 返回指向'a'的迭代器（指针）	for (;it!=s1.end();it++)	{		*it = toupper(*it); // 变成大写		cout<<*it;	}

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;

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

// findif ... 带有条件地查找	pos2 = find_if(iv.begin(),iv.end(),gt60()); // 带有条件地查找！	if (pos2!=iv.end())	{		cout<<"找到了"<<*pos2<<endl;	}

// 仿函数 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_backward

// -_-! 什么情况……	copy_backward(v1.begin(),v1.end(),v3.end()); // v3不能写begin！要写end！	cout<<"v3/n";	for (int i : v3)	{		cout<<i<<" ";	}	cout<<"/n";

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";

class comp{public:	bool operator() (int x, int y) {		return x>y;	}};