《C++ STL-數(shù)據(jù)結(jié)構(gòu)與算法實現(xiàn)》課件第10章 數(shù)值算法與預(yù)定義函數(shù)對象

第十章數(shù)值算法相關(guān)遞增填充iota累加和accumulate序列和partial_sum內(nèi)積inner_product相鄰差adjacent_difference預(yù)定義函數(shù)對象全局數(shù)學函數(shù)數(shù)值數(shù)組類valarray復(fù)數(shù)運算<complex>1／35數(shù)值算法頭文件#include<numeric>iotaStoresastartingvalue,beginningwiththefirstelementandfillingwithsuccessiveincrementsofthatvalue(_Value++)ineachoftheelementsintheinterval[_First,_Last).template<classForwardIterator,classType>void

iota(ForwardIterator_First, //range:tobefilledForwardIterator_Last,

Type_Value); //初值為起始值，隨后_Value

++遞增填充：iota2／35accumulateComputesthesumofalltheelementsinaspecifiedrangeincludingsomeinitialvalue

bycomputingsuccessivepartialsums

orcomputestheresultofsuccessivepartialresultssimilarlyobtainedfromusingaspecifiedbinaryoperationotherthanthesum.template<classInputIterator,classType,classBinaryOperation>Type

accumulate( //求和算法，返回結(jié)果InputIterator_First, //運算區(qū)間InputIterator_Last,

Type_Val, //初值：決定元素類型，并參與運算

BinaryOperation_op

); //二元函數(shù)對象：自定義運算 //缺省運算：加法Return:取決于初值_Val的類型，因此，_Val不可缺省。累加和：accumulate3／35partial_sumComputesaseriesofsumsinaninputrangefromthefirstelementthroughtheithelementandstorestheresultofeachsuchsum

intheithelementofadestinationrange

orcomputestheresultofageneralizedprocedurewherethesumoperationisreplacedbyanotherspecifiedbinaryoperation.template<classInputIterator,classOutputIterator,classBinaryOperation>OutputIterator

partial_sum( InputIterator_First, //inputrangeInputIterator_Last,

OutputIterator_Result, //destinationrange：ith

BinaryOperation_op

); //二元函數(shù)對象：自定義運算 //缺省運算：加法，前一個+后一個Return:addressingtheendofthedestinationrange序列和：partial_sum4／35inner_productComputesthesumoftheelement-wiseproduct

乘積oftworangesandaddsittoaspecifiedinitialvalueorcomputestheresultofageneralizedprocedurewherethesumandproductbinaryoper-ationsarereplacedbyotherspecifiedbinaryoperations.template<classInputIterator1,classInputIterator2,classType,classBinaryOperation1,classBinaryOperation2>Type

inner_product(InputIterator1_First1, //range:向量A=(a1,a2,…an)InputIterator1_Last1,InputIterator2_First2, //range:向量B=(b1,b2,…bn)

Type_Val, //初值：決定元素類型，并參與運算

BinaryOperation1_op1, //自定義運算，缺?。?

BinaryOperation2_op2

);//自定義運算，缺?。?Return:result=_Val

+(a1*b1)+(a2*b2)+...+(an*bn)內(nèi)積：inner_product矢量點積：A·B=|A|*|B|*cosθ5／35adjacent_differenceComputes1thesuccessivedifferences后差

between

eachelement

and

itspredecessorinaninputrangeandoutputstheresultstoadestinationrangeorcomputes2theresultofageneralizedprocedurewherethedifferenceoperationisreplacedbyanother,specifiedbinaryoperation.template<classInputIterator,classOutIterator,classBinaryOperation>OutputIterator

adjacent_difference(InputIterator_First, //inputrangeInputIterator_Last,

OutputIterator_Result, //destinationrange

BinaryOperation_op

); //自定義運算。 //缺?。簻p法，后一個

-前一個相鄰差：adjacent_difference6／35例：五個數(shù)值算法遞增填充缺省運算：加法自定義運算：乘法輸出到屏幕，缺省運算：加法輸出到a3，自定義運算：減法缺省運算缺省運算缺省運算：減法自定義運算：加法7／35函數(shù)對象頭文件#include<functional>函數(shù)對象Defines

StandardLibraryfunctionsthathelpconstruct

functionobjects

—alsoknownasfunctors—andtheirbinders.

Afunctionobjectisanobjectofatypethatdefines

operator().

Afunctionobjectcanbeafunctionpointer普通函數(shù),butmoretypically,theobjectisusedtostoreadditionalinformation類thatcanbeaccessedduringafunctioncall.functor：定義了operator()，函數(shù)（模板）或行為類似函數(shù)的對象。函數(shù)行為：用(…)傳遞參數(shù)。可在類中重載()STL預(yù)定義的functor都是類模板而非函數(shù)，優(yōu)點：時間效率通常比普通函數(shù)高（inline展開函數(shù)）。對象作函數(shù)參數(shù)，若干成員變量可存儲數(shù)據(jù)，不用傳遞。作為函數(shù)參數(shù)，使用更簡便。函數(shù)對象概述8／35Algorithms

require

twotypesoffunctionobjects:unaryandbinary.Unaryfunctionobjectsrequireoneargument,andbinaryfunctionobjectsrequiretwoarguments.

Afunctionobjectandfunctionpointerscanbepassedasapredicatetoanalgorithm,butfunctionobjectsarealsoadaptableandincreasethescope,flexibility,andefficiencyoftheSTL.

predicate

functionobject:takes

singleargumentandreturnstrueorfalse.

binarypredicate

functionobject:takes

twoargumentsandreturnstrueorfalse.謂詞：返回bool型的函數(shù)對象。函數(shù)對象概述9／35unary_functionStructAnemptybasestructthatdefinestypesthatmaybeinheritedbyderivedclassesthatprovidesaunaryfunctionobject.template<classArg,classResult> //兩個模板參數(shù)類型struct

unary_function //C++的結(jié)構(gòu)體就是類{typedefArgargument_type; //參數(shù)類型：任意具體類型typedefResultresult_type; //結(jié)果類型：任意具體類型};//默認權(quán)限：public實例化例：unary_function<int,bool>s1;類繼承例：template<classT>//一元：一個參數(shù)。class

STLfun:public

unary_function<T,bool>{public:

bool

operator()(Telem)//重載(){return(elem>0);}};unary_functionStruct10／35Anempty

basestructthatdefinestypesthatmaybeinheritedbyderivedclassesthatprovidesabinaryfunctionobject.template<classArg1,classArg2,classResult>struct

binary_function{

typedefArg1first_argument_type;typedefArg2second_argument_type;//多一個參數(shù)typedefResultresult_type;};函數(shù)對象的使用

作為函數(shù)的參數(shù)使用；調(diào)用函數(shù)需要函數(shù)對象的參數(shù)個數(shù)；（STL：一元、二元）

編寫或者選用預(yù)定義函數(shù)對象。binary_functionStruct11／35例：unary_function重載operator(),且一個參數(shù)重載operator(),且一個參數(shù)編寫一個參數(shù)的普通函數(shù)-3,-2,-1,0,1,212／35例：unary_functionremove_if舉例：去除elem<0remove_if舉例：去除elem<1remove_if舉例：去除elem<-113／35主要：算術(shù)運算、關(guān)系運算、邏輯運算等三類函數(shù)對象。另有：證同、投射、特殊、內(nèi)存及其他函數(shù)對象適配器。預(yù)定義函數(shù)對象分類名稱類型結(jié)果算術(shù)運算加法：plus<T>()二元arg1+arg2減法：minus<T>()arg1-arg2乘法：multiples<T>()arg1*arg2除法：divides<T>()arg1/arg2取余：modules<T>()arg1%arg2取反：negate<T>()一元-arg1比較運算謂詞等于：equal_to<T>()二元arg1==arg2不等于：not_equal_to<T>()arg1!=arg2大于：greater<T>()arg1>arg2大于等于：greater_equal<T>()arg1>=arg2小于：less<T>()arg1<arg2小于等于：less_equal<T>()arg1<=arg2邏輯運算謂詞與：logical_and<T>()arg1&&arg2或：logical_or<T>()arg1||arg2非：logical_not<T>()!arg114／35C++對函數(shù)的一些數(shù)據(jù)類型進行了重載，可用于多種數(shù)據(jù)類型。

例如：int,float,double,longint,longlongint,__int64cmath打開include<cmath>C++數(shù)學函數(shù)庫，繼承于C的math.h①取余函數(shù)fmod

②分解函數(shù)modf③取整函數(shù)ceil,floor ④三角函數(shù)cos,sin,tan⑤反三角函數(shù)acos,asin,atan,atan2⑥雙曲函數(shù)cosh,sinh,tanh⑦對數(shù)函數(shù)log,log10⑧指數(shù)函數(shù)pow,sqrt,exp⑨絕對值函數(shù)abs⑩其他frexp,ldexp,hypotcstdlib打開include<cstdlib>C++函數(shù)庫，繼承于C的stdlib.h①絕對值函數(shù)labs,llabs②ASCII串轉(zhuǎn)int等atoi,atof,atol

③取余和商div,ldiv,lldiv④生成隨機數(shù)rand,srand……全局數(shù)學函數(shù)15／35

#include<valarray>valarray類概述

設(shè)計目的：處理數(shù)值數(shù)組時獲得最佳性能，而非靈活性和通用性。

充分利用高性能計算機的性能。否則，用容器即可。一維數(shù)值數(shù)組，下標從0開始。對一個或多個數(shù)值數(shù)組的整體或部分進行數(shù)值處理，例如：z=a*x*x+b*x+c

a,b,c,x,z都是同類型的數(shù)值數(shù)組優(yōu)點：使用簡便，性能很好。理由：valarray作了專門優(yōu)化處理。提供輔助類處理其子集及多維如矩陣。數(shù)值數(shù)組類valarray16／35相關(guān)類的聲明打開包含文件<valarray>template<classT>classgslice_array;template<classT>classindirect_array;template<classT>classmask_array;template<classT>classslice_array;template<classT>class

valarray;valarray類：核心類，管理一個數(shù)值數(shù)組。4個輔助類：存放臨時數(shù)值。不能在程序中直接使用，它們由valarray的某些操作產(chǎn)生。valarray雖然模板化，可用任意數(shù)據(jù)類型，但是鑒于其天性，

還是應(yīng)該用數(shù)值類別。數(shù)值數(shù)組類valarray4個輔助類模板17／35valarray構(gòu)造構(gòu)造va1：va1.size()=0va2：賦值va1：添加元素構(gòu)造va3構(gòu)造va4錯誤構(gòu)造va5顯示valarray每個元素遺留問題：如何用一個valarray的一部分構(gòu)造另一個valarray構(gòu)造va2：5個0元素18／35操作對象：valarray的全部元素。遺留問題：如何操作部分元素？操作結(jié)果：不改變原valarray的內(nèi)容。操作結(jié)果：返回值apply()valarray<T>

apply(T

_Func(T

))const;//返回一個valarrayAppliesaspecifiedfunctiontoeachelementofavalarray.example:va=va.apply(myfun);不支持函數(shù)對象和成員函數(shù)cshift()valarray<T>

cshift(int_Count)const;Cyclicallyshiftsalltheelementsinavalarraybyaspecifiednumberofpositions.shift()valarray<T>

shift(int_Count)const;shiftsalltheelementsinavalarraybyaspecifiednumberofpositions.valarray類：成員函數(shù)19／35free()voidfree();Freesthememoryusedbythevalarray.va.free()equivalenttova=valarray<T>()//無名對象max()／min()Tmax()const;//T:valarray元素類型Findsthelargestelementinavalarray.swap()voidswap(valarray&_Right);//va1.swap(va2);Exchangestheelementsoftwovalarrays.sum()Tsum()const;//T:valarray元素類型Thesumoftheelementsoftheoperand操作valarray.valarray類：成員函數(shù)20／35valarray類成員函數(shù)普通函數(shù)func1對va1每個元素用func1處理對va2作4次循環(huán)移位，每次移1位清空va321／35一元運算符（單目）的運算對象一個valarray數(shù)組的全體元素都參與運算二元運算符（雙目）的運算對象兩個valarray大小和類型相同

全體對應(yīng)元素element-wise

進行運算一個valarray全體元素與一個數(shù)值類型相同進行運算返回值返回：一個valarray數(shù)組而不是一個數(shù)，存放對應(yīng)元素的運算結(jié)果。操作符符號函數(shù)：-變反（加-號）算術(shù)運算：+=-=*=/=%==表示賦值，可不賦值比較運算：==!=>>=<<=返回valarray<bool>邏輯運算：!單目||&&返回valarray<bool>位運算：&=位與,|=位或,^=位異或,>>=右移,<<=左移,~位反

=表示賦值，可不賦值valarray：操作符Operators22／35例：valarray操作符算術(shù)運算比較與邏輯運算錯誤的構(gòu)造、運算23／35數(shù)學函數(shù)超越函數(shù)使用這些全局數(shù)學函數(shù)對valarray進行運算。打開頭文件valarray，其中#include<cmath>運算對象對valarray數(shù)組的每一個元素進行運算。運算結(jié)果返回：一個valarray數(shù)組。舉例：pow()二元函數(shù)template<classT> //函數(shù)模板valarray<T>

pow( //計算abconstvalarray<T>&_Left, //底數(shù)a

constvalarray<T>&_Right); //指數(shù)b

b=常量,稱冪兩個操作數(shù)可以是同類數(shù)值：constT&_Left,constT&_Rightvalarray：數(shù)學函數(shù)運算函數(shù)24／35例：valarray數(shù)學函數(shù)運算各種pow()二元函數(shù)函數(shù)25／35形成子數(shù)組有4種方法：slice,gslice,mask_array,indirect_arrayslice類：一維切片抽取子數(shù)組Autilityclasstovalarraythatisusedtodefineone-dimensional一維subsetsofaparentvalarray.Ifavalarrayisregardedasatwo-dimensionalmatrixwithallelementsinanarray,thentheslice

extractsavectorinonedimensionoutofthetwo-dimensionalarray.slice::slice()構(gòu)造函數(shù)Defines

asubsetofavalarraythatconsistsofanumberofelementsthatareanequaldistanceapartandthatstartataspecifiedelement.slice();

//缺省參數(shù)：三個參數(shù)均為0slice( //抽取valarray的一部分形成新的valarraysize_t_StartIndex, //開始抽取的元素下標，unsignintsize_t_Len, //抽取的元素個數(shù)size_t_Stride); //抽取元素的距離（相隔幾個元素）valarray：sliceClass26／35例：valarray的sliceClass

構(gòu)造元素指針賦值對valarray使用算法對普通數(shù)組使用算法？slice形成va3slice形成va4創(chuàng)建slice對象27／35Ifavalarrayisregardedasatwo-dimensionalmatrixwithallelementsinanarray,thentheslice

extractsavectorinonedimensionoutofthetwo-dimensionalarray.STL沒有提供矩陣類，用silce類可構(gòu)造各種矩陣算法：可用slice(i,j,k)

提取各種向量（按行或按列或某種規(guī)律）理解：下圖valarray二維概念回顧：矩陣的一維存儲概念valarray二維概念與sliceva[silce(0,4,3)]=va[slice(1,4,3)]+va[slice(2,4,3)]28／35gslice類：多維切片

g:generalAutilityclasstovalarraythatisusedtodefinemulti-dimensional

slicesofavalarray.——比slice更為一般化，功能更強gslice::gslice()構(gòu)造函數(shù)gslice(); //缺省參數(shù)：三個參數(shù)都為0gslice(size_