《C++ STL-數(shù)據(jù)結(jié)構(gòu)與算法實(shí)現(xiàn)》課件第8章 可變序列算法

第八章可變序列算法復(fù)制copy填充fill交換swap變換transform替換replace生成generate刪除remove唯一unique反轉(zhuǎn)reverse環(huán)移rotate重排random_shuffle排列_permutation分區(qū)partition搬移stable_partition1／39可變序列算法：修改容器中的元素值或位置元素復(fù)制復(fù)制方式：修改而不是插入目標(biāo)容器的元素容量不自動(dòng)增加，需保證足夠template<classInputIterator,classOutputIterator>OutputIteratorcopy(

InputIterator_First, //sourcerange

InputIterator_Last,

OutputIterator_DestBeg); //destinationbegintemplate<classBidirectionalIterator1,classBidirectionalIterator2>BidirectionalIterator2

copy_backward(

BidirectionalIterator1_First, //sourcerange

BidirectionalIterator1_Last,

BidirectionalIterator2_DestEnd

);//destinationend復(fù)制copy2／39template<classInputIterator,classOutputIterator,classBinaryPredicate>OutputIterator

copy_if(

InputIterator_First,

InputIterator_Last,

OutputIterator_Dest,

Predicate_Pred); //一元謂詞：拷貝條件template<classInputIterator,classSize,class OutputIterator>OutputIterator

copy_n(

InputIterator_First,

Size_Count, //拷貝元素的個(gè)數(shù)

OutputIterator_Dest);其他：還有MS的擴(kuò)展，在此不介紹復(fù)制copy3／39例：復(fù)制copycopycopy_backwardcopy_ncopy_if一元謂詞4／39Assignsavaluetoeveryelementinaspecifiedrange.template<classForwardIterator,classType>voidfill(

ForwardIterator_First,//range:[_First,_Last)

ForwardIterator_Last,constType&_Val

); //要賦的元素值A(chǔ)ssignsavaluetoaspecifiednumberofelementsinarangebeginningwithaparticularelement.template<classOutputIterator,classSize,classType>OutputIterator

fill_n(

OutputIteratorFirst, //賦值開始位置SizeCount, //賦值元素個(gè)數(shù)constType&Val); //要賦的元素值填充方式：修改而不是插入目標(biāo)容器的元素容量不自動(dòng)增加填充

fill5／39例：填充

fill如果把整個(gè)結(jié)構(gòu)體裝入vector,如何改寫程序？6／39Thefirstoverload:individualobjects

Thesecondoverload:betweentwoarrays交換方式：overrideexchangetemplate<classType>void

swap(

Type&_Left, //單一對象交換：_Left和_Right

Type&_Right //Type:簡單或復(fù)雜，類型相同); //元素直接交換，非迭代器template<classType,size_tN>voidswap(

Type(&_Left)[N], //一次交換：兩個(gè)數(shù)組，大小相同N

Type(&_Right)[N] //元素直接交換，非迭代器);交換：swap7／39Exchangestheelementsofonerangewiththeelementsofanother,equalsizedrange.template<classForwardIterator1,classForwardIterator2>ForwardIterator2

swap_ranges(

ForwardIterator1_First1,//區(qū)間元素交換：用迭代器實(shí)現(xiàn)

ForwardIterator1_Last1,

ForwardIterator2_First2//保證空間足夠，不會(huì)自動(dòng)擴(kuò)展);Exchangestwovaluesreferredtobyapairofspecifiediterators.template<classForwardIterator1,classForwardIterator2>voiditer_swap(

ForwardIterator1_Left,//單一元素交換：用迭代器實(shí)現(xiàn)

ForwardIterator2_Right);交換：swap8／39例：交換swap//v1,v2大小可不同9／39Appliesaspecifiedfunctionobjectto1

eachelementinasourcerangeorto2

apairofelementsfromtwosourcerangesandcopiesthereturnvaluesofthefunctionobjectintoadestinationrange.template<classInputIterator,classOutputIterator,classUnaryFunction>OutputIteratortransform(

InputIterator_First1,//sourcerange

InputIterator_Last1,

OutputIterator_Result,//destinationrange，保證空間足夠

UnaryFunction_Func);//一元函數(shù)對象：對元素作運(yùn)算函數(shù)功能：對sourcerange每個(gè)元素用函數(shù)對象進(jìn)行各種變換；將變換結(jié)果覆蓋寫入

destinationrange.對于目標(biāo)區(qū)間，可改用插入型迭代器自動(dòng)擴(kuò)展空間變換：transform源區(qū)間目標(biāo)區(qū)間op覆蓋10／39template<classInputIterator1,classInputIterator2,class

OutputIterator,classBinaryFunction>OutputIteratortransform(

InputIterator1_First1, //sourcerange1

InputIterator1_Last1,

InputIterator2_First2, //sourcerange2

OutputIterator_Result, //destinationrange，保證空間足夠

BinaryFunction_Func);//二元函數(shù)對象：對元素作運(yùn)算函數(shù)功能：對兩個(gè)sourcerange的一對元素用函數(shù)對象進(jìn)行變換；將變換結(jié)果覆蓋寫入

destinationrange.對于目標(biāo)區(qū)間，可改用插入型迭代器自動(dòng)擴(kuò)展空間變換：transform源區(qū)間2目標(biāo)區(qū)間op源區(qū)間1覆蓋11／39例：transformarray:a→bvectorv1,v2(-1)*v1→v2listLv1+v2→L覆蓋12／39Examineseachelementinarangeandreplacesitifitmatchesaspecifiedvalue1

oraspecifiedpredicate2.template<classForwardIterator,classType>voidreplace(

ForwardIterator_First, //Forward:R/W可讀可寫

ForwardIterator_Last,constType&_OldVal, //舊值constType&_NewVal); //新值替換template<classForwardIterator,classPredicate,classType>voidreplace_if(

ForwardIterator_First,

ForwardIterator_Last,Predicate_Pred, //一元謂詞：替換條件。系統(tǒng)：==constType&_Val); //新值替換替換：replace13／39Examineseachelementinasourcerangeandreplacesitifitmatchesaspecifiedvalue1

oraspecifiedpredicate2

whilecopyingtheresultintoanewdestinationrange.template<classInputIterator,classOutputIterator,classType>OutputIteratorreplace_copy(

InputIterator_First, //Input:只能讀不能寫

InputIterator_Last,

OutputIterator_Result,//目標(biāo)區(qū)間：替換結(jié)果拷入constType&_OldVal,//舊值constType&_NewVal);//新值替換OutputIteratorreplace_copy_if( ……同上Predicate_Pred, //一元謂詞：替換條件。系統(tǒng)：==constType&_Val); //新值替換替換：replace14／39例：replacelist15／39Assignsthevalues

generatedbyafunctionobject

to1

eachelement

orto2

aspecifiednumberofelementsinarange.template<classForwardIterator,classGenerator>voidgenerate(

ForwardIterator_First, //賦值范圍

ForwardIterator_Last,Generator_Gen

); //函數(shù)對象：產(chǎn)生值template<classOutputIterator,classDiff,classGenerator>voidgenerate_n(

OutputIterator_First, //賦值范圍開始位置Diff_Count, //賦值元素個(gè)數(shù)Generator_Gen

); //函數(shù)對象：產(chǎn)生值_Gen:iscalledwithnoarguments.生成：generate16／39例：generatedequearray17／39例：generate產(chǎn)生隨機(jī)數(shù)無名函數(shù)對象改為函數(shù)模板改為函數(shù)重載18／39例：generate產(chǎn)生隨機(jī)數(shù)19／39Eliminates

1aspecifiedvalue

or

2elementsthatsatisfyapredicate

fromagivenrangewithoutdisturbingtheorderoftheremainingelementsandreturningtheendofanewrangefreeofthespecifiedvalue.template<classForwardIterator,classType>ForwardIterator

remove( //返回：刪除后新區(qū)域的end

ForwardIterator_First, //刪除區(qū)間：R/W

ForwardIterator_Last,

constType&_Val); //指定值：刪除template<classForwardIterator,classPredicate>ForwardIterator

remove_if(

ForwardIterator_First,

ForwardIterator_Last,

Predicate_Pred); //一元謂詞：刪除條件。系統(tǒng)：==新區(qū)域：不包含刪除的元素。刪除：remove類似20／39Copieselementsfromasourcerangetoadestinationrange,exceptthatelementsofaspecifiedvaluearenotcopied,withoutdisturbingtheorderoftheremainingelementsandreturningtheendof

anewdestinationrange.template<classInputIterator,classOutputIterator,classType>OutputIteratorremove_copy(

InputIterator_First, //刪除的源區(qū)間：不可寫

InputIterator_Last,

OutputIterator_Result, //目標(biāo)區(qū)間開始位置：拷貝constType&_Val); //指定值：刪除OutputIteratorremove_copy_if( ……同上

Predicate_Pred); //一元謂詞：刪除條件刪除：remove類似21／39例：remove理解remove并非真正刪除元素而是后面元素向前賦值，并作新end標(biāo)記。O(n)list成員函數(shù)效率更高。重連指針22／39Removes

duplicateelementsthatareadjacenttoeachotherinaspecifiedrange.emplate<classForwardIterator>ForwardIteratorunique( //兩兩比較：去除相鄰重復(fù)元素

ForwardIterator_First, //處理范圍

ForwardIterator_Last);template<classForwardIterator,classPredicate>ForwardIteratorunique(

ForwardIterator_First,

ForwardIterator_Last,

Predicate_Comp);//二元謂詞：去除條件

缺?。?=去除的元素：去除后一個(gè)重復(fù)元素。同remove：并非真正刪除元素，而是后面元素向前賦值，并作新end標(biāo)記。唯一：unique23／39Copieselementsfromasourcerangeintoadestinationrangeexceptfortheduplicateelementsthatareadjacenttoeachother.template<classInputIterator,classOutputIterator>OutputIteratorunique_copy(InputIterator_First,InputIterator_Last,OutputIterator_Result);template<classInputIterator,classOutputIterator,classBinaryPredicate>OutputIteratorunique_copy(InputIterator_First,InputIterator_Last,OutputIterator_Result,

BinaryPredicate_Comp

); //二元謂詞：去除條件 //缺?。?=唯一：unique24／39例：unique25／39Reversestheorderoftheelementswithinarange.template<classBidirectionalIterator>voidreverse(BidirectionalIterator_First,BidirectionalIterator_Last);Reversestheorderoftheelementswithinasourcerangewhilecopyingthemintoadestinationrangetemplate<classBidirectionalIterator,classOutputIterator>OutputIteratorreverse_copy(

BidirectionalIterator_First,//sourcerange

BidirectionalIterator_Last,

OutputIterator_Result);//destinationrange反轉(zhuǎn)：reverse26／39例：reverse27／39Exchangestheelementsintwoadjacentranges.template<classForwardIterator>voidrotate(ForwardIterator_First,ForwardIterator_Middle,ForwardIterator_Last

);Exchangestheelementsintwoadjacentrangeswithinasource

rangeandcopiestheresulttoadestinationrange.template<classForwardIterator,classOutputIterator>OutputIteratorrotate_copy(ForwardIterator_First,ForwardIterator_Middle,ForwardIterator_Last,

OutputIterator_Result

);//目標(biāo)區(qū)間：結(jié)果拷入環(huán)移：rotate210543交換結(jié)果543210_Middle_First_Last交換28／3929／39543210_Middle_First_Last交換210543交換結(jié)果例：rotaterotate比較與swap比較異同30／39RearrangesasequenceofNelementsinarangeintooneofN!全排列possiblearrangementsselectedatrandom.template<classRandomAccessIterator>voidrandom_shuffle(

RandomAccessIterator_First,//隨機(jī)shuffle區(qū)間

RandomAccessIterator_Last);//[_First,_Last)template<classRandomAccessIterator,classRandomNumberGenerator>voidrandom_shuffle(

RandomAccessIterator_First,

RandomAccessIterator_Last,

RandomNumberGenerator&_Rand);//指定：隨機(jī)數(shù)發(fā)生器 //缺?。合到y(tǒng)定義的_Rand：canacceptaseedvalue帶一個(gè)參數(shù)注意要求：RandomAccessIterator回顧第六章支持容器：vector,queue,string,array重排：random_shuffle洗牌比較31／39例：random_shuffle洗牌srand缺省方式缺省方式srand自編隨機(jī)數(shù)發(fā)生器結(jié)合srand，用缺省的隨機(jī)數(shù)發(fā)生器足夠32／3901234533／39隨機(jī)產(chǎn)生另一個(gè)交換元素[result]待交換的元素從下標(biāo)[1]開始result=0交換結(jié)果1023450122result=203result=110234510234510234513204524result=213204513402525result=4134025134052next_permutationReorderstheelementsinarange

sothat

theoriginalorderingisreplacedbythelexicographically字典方式nextgreater

permutationifitexists.next:maybespecifiedwithabinarypredicate.回顧：第六章lexicographical_compare算法template<classBidirectionalIterator,classBinaryPredicate>bool

next_permutation(BidirectionalIterator_First, //range:tobepermutedBidirectionalIterator_Last,

BinaryPredicate_Comp

); //比較規(guī)則。缺省<

Returntrue:thelexicographicallynext

greaterpermutation

exists andhasreplacedtheoriginalorderingoftherange.Returnfalse:otherwise,theoriginalorderingistransformedintothelexicographicallysmallestpermutation.排列next_permutation34／39prev_permutationReorderstheelementsinarangesothattheoriginalorderingisreplacedbythelexicographicallypreviousgreaterpermutation

ifitexists.

previous:maybespecifiedwithabinarypredicate.類似于next_permutationtemplate<classBidirectionalIterator,classBinaryPredicate>boolprev_permutation(BidirectionalIterator_First,//rang