20 标准模板库(三)

6.2settemplateclassKey,classPred=lessKey,classA=allocatorKeyclassset{…}插入set中已有的元素时，插入不成功。程序设计实习第二十讲标准模板库(三)pair模板:templateclassT,classUstructpair{typedefTfirst_type;typedefUsecond_type;Tfirst;Usecond;pair();pair(constT&x,constU&y);templateclassV,classWpair(constpairV,W&pr);};pair模板可以用于生成key-value对#includeset#includeiostreamusingnamespacestd;main(){typedefsetdouble,lessdoubledouble_set;constintSIZE=5;doublea[SIZE]={2.1,4.2,9.5,2.1,3.7};double_setdoubleSet(a,a+SIZE);ostream_iteratordoubleoutput(cout,);cout1);copy(doubleSet.begin(),doubleSet.end(),output);coutendl;输出：1)2.13.74.29.52)9.5notinsertedpairdouble_set::const_iterator,boolp;p=doubleSet.insert(9.5);if(p.second)cout2)*(p.first)insertedendl;elsecout2)*(p.first)notinsertedendl;}//insert函数返回值是一个pair对象,其first是被插入元素的迭代//器，second代表是否成功插入了输出：1)2.13.74.29.52)9.5notinserted6.3multimaptemplateclassKey,classT,classPred=lessKey,classA=allocatorTclassmultimap{….typedefpairconstKey,Tvalue_type;…….};//Key代表关键字multimap中的元素由关键字,值组成，每个元素是一个pair对象。multimap中允许多个元素的关键字相同。元素按照关键字升序排列，缺省情况下用lessKey定义关键字的“小于”关系#includeiostream#includemapusingnamespacestd;intmain(){typedefmultimapint,double,lessintmmid;mmidpairs;cout1)pairs.count(15)endl;pairs.insert(mmid::value_type(15,2.7));pairs.insert(mmid::value_type(15,99.3));cout“2)”pairs.count(15)endl;//求某关键值的个数pairs.insert(mmid::value_type(30,111.11));pairs.insert(mmid::value_type(10,22.22));输出:1)02)2(10,22.22),(15,2.7),(15,99.3),(20,9.3),(25,33.333),(30,111.11)pairs.insert(mmid::value_type(25,33.333));pairs.insert(mmid::value_type(20,9.3));for(mmid::const_iteratori=pairs.begin();i!=pairs.end();i++)cout(i-first,i-second),;}//输出：1)02)2(10,22.22),(15,2.7),(15,99.3),(20,9.3),(25,33.333),(30,111.11)6.4maptemplateclassKey,classT,classPred=lessKey,classA=allocatorTclassmap{….typedefpairconstKey,Tvalue_type;…….};map中的元素关键字各不相同。元素按照关键字升序排列，缺省情况下用less定义“小于”可以用pairs[key]访形式问map中的元素。pairs为map容器名，key为关键字的值。该表达式返回的是对关键值为key的元素的值的引用。如果没有关键字为key的元素，则会往pairs里插入一个关键字为key的元素，并返回其值的引用如：mapint,doublepairs;则pairs[50]=5;会修改pairs中关键字为50的元素，使其值变成5#includeiostream#includemapusingnamespacestd;ostream&operator(ostream&o,constpairint,double&p){o(p.first,p.second);returno;}intmain(){typedefmapint,double,lessintmmid;mmidpairs;cout1)pairs.count(15)endl;pairs.insert(mmid::value_type(15,2.7));pairs.insert(make_pair(15,99.3));//make_pair生成一个pair对象cout2)pairs.count(15)endl;pairs.insert(mmid::value_type(20,9.3));mmid::iteratori;cout3);for(i=pairs.begin();i!=pairs.end();i++)cout*i,;输出：1)02)13)(15,2.7),(20,9.3),4)(15,2.7),(20,9.3),(40,0),5)(15,6.28),(20,9.3),(40,0),coutendl;cout4);intn=pairs[40];//如果没有关键字为40的元素，则插入一个for(i=pairs.begin();i!=pairs.end();i++)cout*i,;coutendl;cout5);pairs[15]=6.28;//把关键字为15的元素值改成6.28for(i=pairs.begin();i!=pairs.end();i++)cout*i,;}输出：1)02)13)(15,2.7),(20,9.3),4)(15,2.7),(20,9.3),(40,0),5)(15,6.28),(20,9.3),(40,0),输出：1)02)13)(15,2.7),(20,9.3),4)(15,2.7),(20,9.3),(40,0),5)(15,6.28),(20,9.3),(40,0),7容器适配器7.1stack可用vector,list,deque来实现,缺省情况下，用deque实现stack是后进先出的数据结构，只能插入，删除，访问栈顶的元素用vector和deque实现，比用list实现性能好templateclassT,classCont=dequeTclassstack{…..};stack上可以进行以下操作：push:插入元素pop:弹出元素top:返回栈顶元素的引用7.2queue和stack基本类似，可以用list和deque实现，缺省情况下用deque实现templateclassT,classCont=dequeTclassqueue{……};同样也有push,pop,top函数但是push发生在队尾，pop,top发生在队头，先进先出7.3priority_queue和queue类似，可以用vector和deque实现，缺省情况下用vector实现。priority_queue通常用堆排序技术实现，保证最大的元素总是在最前面。即执行pop操作时，删除的是最大的元素,执行top操作时，返回的是最大元素的引用。默认的元素比较器是lessT#includequeue#includeiostreamusingnamespacestd;main(){priority_queuedoublepriorities;priorities.push(3.2);priorities.push(9.8);priorities.push(5.4);while(!priorities.empty()){coutpriorities.top();priorities.pop();}}//输出结果：9.85.43.28算法1)random_shuffle:templateclassRanItvoidrandom_shuffle(RanItfirst,RanItlast);随机打乱[first,last)中的元素，适用于能随机访问的容器2）count:templateclassInIt,classTsize_tcount(InItfirst,InItlast,constT&val);计算[first,last)中等于val的元素个数3)count_iftemplateclassInIt,classPred,classDistsize_tcount_if(InItfirst,InItlast,Predpr);计算[first,last)中符合pr(e)==true的元素e的个数3）min_element:templateclassFwdItFwdItmin_element(FwdItfirst,FwdItlast);返回[first,last)中最小元素的迭代器,以“”作比较器4）max_element:templateclassFwdItFwdItmax_element(FwdItfirst,FwdItlast);返回[first,last)中最大(不小）元素的迭代器,以“”作比较器5）accumulatetemplateclassInIt,classTTaccumulate(InItfirst,InItlast,Tval);对[first,last)区间中的每个迭代器I,执行val=val+*I;返回valtemplateclassInIt,classT,classPredTaccumulate(InItfirst,InItlast,Tval,Predpr);对[first,last)区间中的每个迭代器I,执行val=pr(val,*I),返回val6）for_eachtemplateclassInIt,classFunFunfor_each(InItfirst,InItlast,Funf);对[first,last)中的每个元素e,执行f(e),要求f(e)不能改变e7)transformtemplateclassInIt,classOutIt,classUnopOutIttransform(InItfirst,InItlast,OutItx,Unopuop);对[first,last)中的每个迭代器I,执行uop(*I);并将结果依次放入从x开始的地方。要求uop(*I)不得改变*I的值本模板返回值是个迭代器，即x+(last-first)x可以和first相等#includevector#includeiostream#includenumeric#includelist#inclu