第九章实用技巧与模版库

第九章C++第一节排序算使用排序算法必须包含algorithm头文件//将数组arr的下m的元素到下标为n-1的元素进行从小到 //与sort(arr+m,arr+n)相比，这个写法可以自己定义排序的//其中，comp为自定义的函数对于sort(arr+m,arr+n)我们举个简单的例子：usingnamespacestd;inta[10];int{for(inti=0;i<10;++i)cin>>a[i];for(inti=0;i<10;++i)cout<<a[i]<<'';return} p)之前我们需要自己写个comp函数。从大到小排序的comp函数可以这样写 p(constint&a,constint&{return //在两元素相同时一定要返回0 p函数的名字是由我们自己决定的，例如可以叫cat_cat,dog_dog等读入usingnamespacestd;inta[10]; p(constint&a,constint&{return //如果a>b则返1，否则返回}int{for(inti=0;i<10;++i)cin>>a[i]; for(inti=0;i<10;++i)cout<<a[i]<<'';return}在情况下，我们不仅对一个特征进行排序，而是多个特征。例如将学生的成绩进行排序，当然序结构体时，sort()默认结构体中的第一个成员为第一关键字，第二个成员为第二关键字，……，第N个元素为第N关键字，然后从小到大排序。这时我们可以定义这样的 p(conststudent&a,conststudent&{if(a.score>b.score)return1;if(a.score<b.score)return0;if(aname<bname)return1;return0;}例.1.；放第一行一个整数3XiaoxiaoXiaoxiaousingnamespacestd;structstudent{intscore;int p(conststudent&a,conststudent&{if(a.score>b.score)return1;if(a.score<b.score)return0;if(aname<bname)return1;return0;}int{for(int{cin>>a[i]name;} for(intreturn0;}第二节时，我们就会把它写成函数。或许你会疑问，我们难道不能向像inta=3,b=4,c;c=a+b;一样进行运算吗？答案是肯定的。接下来介绍如何利用重载运算符进行高精计算。 constintMAXN=4000; structBIGNUM{int作用就是进行初始化。每当我们定义一个BIGNUM类型的变量时，这个变量就会被初始化。例如定义BIGNUMx时，会得x.len==1,x.s中的所有元素均为0。BIGNUMoperatorconstchar*num for(inti=0;i<len;++i)s[i]=num[len-i-1]-'0';return*this;}当我们可以写例如x=” 01314520”的时候，我们肯定还想将 BIGNUMoperator=(constint{chara[MAXN];*this=a;return*this;}BIGNUM(intnum){*this=num;}BIGNUM(constchar*num){*this=num;}ostream&operator<<(ostream&out,constBIGNUM&{for(inti=x.len-1;i>=0;--i)return}重载完”<<”，顺便重载下”>>”，和重载”<<”时一样，要写在结构体外面istream&operator>>(istream&in,BIGNUM{charnum[MAXN];}BIGNUMoperator+(constBIGNUM&{BIGNUM for(inti=0,x=0;i<c.len;++i){}if(c.s[c.len-1]==0)--c.len; returnc;}BIGNUMoperator+=(constBIGNUM&a)return*this;}我们先重载下“<”然后利用“<”重载出其他关系运算booloperator<(constBIGNUM&x)constif(len!=x.len)returnlen<x.len; for(inti=len-1;i>=0;--i){if(s[i]!=x.s[i])return}return }booloperator>(constBIGNUM&x)const{returnx<*this;}booloperator<=(constBIGNUM&x)const{return!(x<*this);}booloperator>=(constBIGNUM&x)const{return!(*this<x);booloperator==(constBIGNUM&x)const{return!(x<*this||*this<x);}booloperator!=(constBIGNUM&x)const{returnx<*this||*this<x;}0<n<101,m<10^500.只有一行，包括一个n和一个如 1!+2!+3!+...+n!大于m，则输出”yes”,否则输出 usingnamespacestd;constintMAXN=4000;structBIGNUM{intBIGNUM(){memset(s,0,sizeof(s));len=1;}BIGNUMoperator=(constchar*num){for(inti=0;i<len;++i)s[i]=num[len-i-1]-'0';return*this;}BIGNUMoperator=(constint{chara[MAXN];*this=a;return*this;}BIGNUM(constintnum){*this=num;}BIGNUM(constchar*num){*this=num;}BIGNUMoperator+(constBIGNUM&a)for(int}if(c.s[c.len-1]==0)--c.len;returnc;}BIGNUMoperator+=(constBIGNUM&a)return*this;}BIGNUMoperator*(constBIGNUM&{BIGNUMfor(inti=0;i<len;++i)for(int{c.s[i+j]+=s[i]*x.s[j];}}if(c.s[c.len-1]==0)--c.len;returnc;}BIGNUMoperator*=(constBIGNUM&a)*this=*this*a;return*this;}booloperator<(constBIGNUM&x){if(len!=x.len)returnlen<x.len;for(inti=len-1;i>=0;--i){if(s[i]!=x.s[i])return}return}booloperator>(constBIGNUM&x)const{returnx<*this;}booloperator<=(constBIGNUM&x)const{return!(x<*this);}booloperator>=(constBIGNUM&x)const{return!(*this<x);booloperator==(constBIGNUM&x)const{return!(x<*this||*this<x);}booloperator!=(constBIGNUM&x)const{returnx<*this||*this<x;}ostream&operator<<(ostream&out,constBIGNUM&{for(inti=x.len-1;i>=0;--i)return}istream&operator>>(istream&in,BIGNUM{charnum[MAXN];return}int{intfor(int{num*=i;}elsecout<<"no"<<endl;return}第三节字符串这毋庸置疑是错的。不过，接下来介绍的一种数据类型——字符串类型(string)，它允许写s2=s1的赋值方在使用string类型时，须包含string头文件string类型的定义与初始string //定义一个字符串s1 string //s3初始化为strng //s4初始化为字符’c’的nstring类型的读string类型的读写就像其它类型的读写一样，使用cin,cout。不过值得注意的是，使用cin读入string类读入未知数目的string对象：usingnamespacestd;intmain(){strings;while(cin>>s)}return} oo正如介绍的那样，读入时忽略了空字符，读者可以将其记cin读字符串读的是单词。当然，有时我们更希望的是句子。幸好C++提供了getline函数以供使用。getline的原型是：getline(cin,s);cin指的是读入流，一般情况下我们直接写cin即可，s是字符串，即我们读入的东西要存放的字符串。我们用getline来上面的数据：usingnamespacestd;intmain(){strings;while(getline(cin,s)){ cout<<++tot<<''<<s<<endl;}return}ostring类型的操若s为空串，则返回true,否则返回返回s中字符的个数，s.length()用法与s.size返回s中位置为n的字符，位置0开始计数(可将值s1和s2连接成一个新字符串，返回新生成的字符比较v1v2的内容，相等则返回true,否则返回string o //等价于string o”; //等价于s1=s1+s2，此时s1=”ostrings1=”o”;strings3=s1+”,”; strings4=”o”+”world”;//strings5=s1+”,”+”world”;//合法，根据从左至右的strings6=” o”+”,“+s2;//，因为” o”与”,”都是字符数组类型 //现在str[1]变成了在s下标为pos的元素前插入string返回一个string类型，它包含s中下标为pos起的len个字删除s中下标为pos开始的len删除s中下标为pos的len个字符，并在下标为pos处插在s中以pos位置起查找s2一次出现的位置，返回一个与s字面值相同的C风格的字符串临时指usingnamespacestd;intmain(){return}正如前面所讲s1+s2是将两个字符串类usingnamespacestd;intmain(){inta,b; return0;}第四节FIFO用他们必须包含queue头文件。queue<类型名>queue<int //定义que为一个int类型FIFO队queue<char //a为一个char类型FIFO队queue<data> //定义c为一个data类型FIFO队//其中data为自定义的数据类型，可以为结构priority_queueint //定义heap为一个int类型的优先队priority_queue<double>k; //定义k为一个double类型的优先队列intbooloperatorconstdata&a)const returna }priority_queue< //q优先队列的优先规则由data若队列为空，则返回true,否则返回q对queue，在队尾压入一个新元对于priority_queue,在基于优先级的适当位置插入新元利用C++usingnamespacestd;intmain(){intn;for(int{que.push(-}intfor(int{ans-}return0；}第五节动态数 //定义que为一个int类型的动态数vector<char //定义a为一个char类型的动态数vector<data> 返回动态数组中的第i个元若动态数组为空，则返回true,否则a返回指向vector头部的迭代器（指针返回指向vector尾部元素的后一个元素的迭代器（指针#include<iostream>#include<cstdio>#include<vector>#include<algorithm>usingnamespacestd;intmain(){vector<inta;//动态数组intn;{inttmp;}for(inti=0;i<a.size();i++)printf("%d",a[i]);return}第六节关联式容器map容器来作为一个有序的映射表，可以将其看做是一个下标可以是任何类型的数组。对