《C++ STL-数据结构与算法实现》课件第8章 可变序列算法

第八章可变序列算法复制copy填充fill交换swap变换transform替换replace生成generate删除remove唯一unique反转reverse环移rotate重排random_shuffle排列_permutation分区partition搬移stable_partition1／39可变序列算法：修改容器中的元素值或位置元素复制复制方式：修改而不是插入目标容器的元素容量不自动增加，需保证足够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复制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, //拷贝元素的个数

OutputIterator_Dest);其他：还有MS的扩展，在此不介绍复制copy3／39例：复制copycopycopy_backwardcopy_ncopy_if一元谓词4／39Assignsavaluetoeveryelementinaspecifiedrange.template<classForwardIterator,classType>voidfill(

ForwardIterator_First,//range:[_First,_Last)

ForwardIterator_Last,constType&_Val

); //要赋的元素值Assignsavaluetoaspecifiednumberofelementsinarangebeginningwithaparticularelement.template<classOutputIterator,classSize,classType>OutputIterator

fill_n(

OutputIteratorFirst, //赋值开始位置SizeCount, //赋值元素个数constType&Val); //要赋的元素值填充方式：修改而不是插入目标容器的元素容量不自动增加填充

fill5／39例：填充

fill如果把整个结构体装入vector,如何改写程序？6／39Thefirstoverload:individualobjects

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

swap(

Type&_Left, //单一对象交换：_Left和_Right

Type&_Right //Type:简单或复杂，类型相同); //元素直接交换，非迭代器template<classType,size_tN>voidswap(

Type(&_Left)[N], //一次交换：两个数组，大小相同N

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

swap_ranges(

ForwardIterator1_First1,//区间元素交换：用迭代器实现

ForwardIterator1_Last1,

ForwardIterator2_First2//保证空间足够，不会自动扩展);Exchangestwovaluesreferredtobyapairofspecifiediterators.template<classForwardIterator1,classForwardIterator2>voiditer_swap(

ForwardIterator1_Left,//单一元素交换：用迭代器实现

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);//一元函数对象：对元素作运算函数功能：对sourcerange每个元素用函数对象进行各种变换；将变换结果覆盖写入

destinationrange.对于目标区间，可改用插入型迭代器自动扩展空间变换：transform源区间目标区间op覆盖10／39template<classInputIterator1,classInputIterator2,class

OutputIterator,classBinaryFunction>OutputIteratortransform(

InputIterator1_First1, //sourcerange1

InputIterator1_Last1,

InputIterator2_First2, //sourcerange2

OutputIterator_Result, //destinationrange，保证空间足够

BinaryFunction_Func);//二元函数对象：对元素作运算函数功能：对两个sourcerange的一对元素用函数对象进行变换；将变换结果覆盖写入

destinationrange.对于目标区间，可改用插入型迭代器自动扩展空间变换：transform源区间2目标区间op源区间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, //一元谓词：替换条件。系统：==constType&_Val); //新值替换替换：replace13／39Examineseachelementinasourcerangeandreplacesitifitmatchesaspecifiedvalue1

oraspecifiedpredicate2

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

InputIterator_First, //Input:只能读不能写

InputIterator_Last,

OutputIterator_Result,//目标区间：替换结果拷入constType&_OldVal,//旧值constType&_NewVal);//新值替换OutputIteratorreplace_copy_if( ……同上Predicate_Pred, //一元谓词：替换条件。系统：==constType&_Val); //新值替换替换：replace14／39例：replacelist15／39Assignsthevalues

generatedbyafunctionobject

to1

eachelement

orto2

aspecifiednumberofelementsinarange.template<classForwardIterator,classGenerator>voidgenerate(

ForwardIterator_First, //赋值范围

ForwardIterator_Last,Generator_Gen

); //函数对象：产生值template<classOutputIterator,classDiff,classGenerator>voidgenerate_n(

OutputIterator_First, //赋值范围开始位置Diff_Count, //赋值元素个数Generator_Gen

); //函数对象：产生值_Gen:iscalledwithnoarguments.生成：generate16／39例：generatedequearray17／39例：generate产生随机数无名函数对象改为函数模板改为函数重载18／39例：generate产生随机数19／39Eliminates

1aspecifiedvalue

or

2elementsthatsatisfyapredicate

fromagivenrangewithoutdisturbingtheorderoftheremainingelementsandreturningtheendofanewrangefreeofthespecifiedvalue.template<classForwardIterator,classType>ForwardIterator

remove( //返回：删除后新区域的end

ForwardIterator_First, //删除区间：R/W

ForwardIterator_Last,

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

remove_if(

ForwardIterator_First,

ForwardIterator_Last,

Predicate_Pred); //一元谓词：删除条件。系统：==新区域：不包含删除的元素。删除：remove类似20／39Copieselementsfromasourcerangetoadestinationrange,exceptthatelementsofaspecifiedvaluearenotcopied,withoutdisturbingtheorderoftheremainingelementsandreturningtheendof

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

InputIterator_First, //删除的源区间：不可写

InputIterator_Last,

OutputIterator_Result, //目标区间开始位置：拷贝constType&_Val); //指定值：删除OutputIteratorremove_copy_if( ……同上

Predicate_Pred); //一元谓词：删除条件删除：remove类似21／39例：remove理解remove并非真正删除元素而是后面元素向前赋值，并作新end标记。O(n)list成员函数效率更高。重连指针22／39Removes

duplicateelementsthatareadjacenttoeachotherinaspecifiedrange.emplate<classForwardIterator>ForwardIteratorunique( //两两比较：去除相邻重复元素

ForwardIterator_First, //处理范围

ForwardIterator_Last);template<classForwardIterator,classPredicate>ForwardIteratorunique(

ForwardIterator_First,

ForwardIterator_Last,

Predicate_Comp);//二元谓词：去除条件

缺省：==去除的元素：去除后一个重复元素。同remove：并非真正删除元素，而是后面元素向前赋值，并作新end标记。唯一：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反转：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

);//目标区间：结果拷入环移：rotate210543交换结果543210_Middle_First_Last交换28／3929／39543210_Middle_First_Last交换210543交换结果例：rotaterotate比较与swap比较异同30／39RearrangesasequenceofNelementsinarangeintooneofN!全排列possiblearrangementsselectedatrandom.template<classRandomAccessIterator>voidrandom_shuffle(

RandomAccessIterator_First,//随机shuffle区间

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

RandomAccessIterator_First,

RandomAccessIterator_Last,

RandomNumberGenerator&_Rand);//指定：随机数发生器 //缺省：系统定义的_Rand：canacceptaseedvalue带一个参数注意要求：RandomAccessIterator回顾第六章支持容器：vector,queue,string,array重排：random_shuffle洗牌比较31／39例：random_shuffle洗牌srand缺省方式缺省方式srand自编随机数发生器结合srand，用缺省的随机数发生器足够32／3901234533／39随机产生另一个交换元素[result]待交换的元素从下标[1]开始result=0交换结果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

); //比较规则。缺省<

Returntrue:thelexicographicallynext

greaterpermutation

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

ifitexists.

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