




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
第六~七章非可變序列算法與迭代器算法分類迭代器及其分類循環(huán)算法查詢算法計數(shù)算法比較算法1/50算法、容器、迭代器、函數(shù)對象之關系圖STL
算法概述容器1某算法迭代器1讀取寫入?yún)?shù)傳入返回容器2迭代器2讀取寫入?yún)?shù)傳入返回容器n迭代器n讀取寫入?yún)?shù)傳入返回…………函數(shù)對象參數(shù)傳入算法通過迭代器去操作容器中數(shù)據(jù)2/50MSDNTheSTLalgorithmsaregenericbecausetheycanoperateonavarietyofdatastructures.Thedatastructuresthattheycanoperateonincludenotonly
theSTLcontainer
classessuchasvectorandlist,butalso
program-defineddatastructuresandarraysofelementsthatsatisfytherequirementsofaparticularalgorithm.STLalgorithmsachievethislevelofgeneralitybyaccessingandtraversingtheelementsofacontainerindirectlythroughiterators.TheSTLalgorithmsextendtheactionssupportedbytheoperationsandmemberfunctionsofeachSTLcontainerandallowworking,forexample,withdifferenttypesofcontainerobjectsatthesametime.STL
算法概述3/50算法和容器成員函數(shù)的區(qū)別算法:函數(shù)模板,不是容器(類模板)的成員函數(shù)
——直接使用,不是通過容器對象調用算法:有些與容器的成員函數(shù)同名且功能相同
——用法不同頭文件算法:<algorithm>數(shù)值算法:<numeric>函數(shù)對象:<functional>STL算法概述4/50STL算法分類非可變序列算法
算法不修改容器元素的值或順序for_each、線性查找、子序列匹配、元素個數(shù)、元素比較、最大與最小值可變序列算法
算法要修改容器元素的值或順序復制、填充、交換、變換、替換、生成、刪除、反轉、唯一、環(huán)移、分區(qū)、搬移、隨機重排。排序相關算法排序、折半查找、歸并排序、有序集操作、堆排序數(shù)值算法復數(shù)運算、向量運算(值數(shù)組valarray)、通用數(shù)值計算(求和、內積、部分和、序列相鄰差)STL算法分類5/50非可變序列算法功能函數(shù)名稱說
明循環(huán)for_each()
對每個元素執(zhí)行同一指定操作,返回函數(shù)對象查詢find()
返回元素值=指定值的第一次出現(xiàn)位置find_if()
返回元素值符合謂詞函數(shù)對象的第一次出現(xiàn)位置迭代器find_first_of()
返回元素值=指定值之一的第一次出現(xiàn)位置adjacent_find()
返回相鄰元素值相等的第一次出現(xiàn)位置find_end()
返回指定子序列匹配的最后一次出現(xiàn)位置search()
返回指定子序列匹配的第一次出現(xiàn)位置search_n
返回元素值=指定值、連續(xù)n次匹配的第一次位置計數(shù)count()
返回元素值=指定值的元素個數(shù)count_if()
返回元素值符合謂詞的元素個數(shù)比較equal()
返回true:兩個序列的對應元素都相等mismatch()
返回兩個序列不同的第一個元素位置
2個容器的位置min_element()
返回最小值元素的位置max_element()
返回最大值元素的位置關系6/50迭代器語義分類功能輸入型迭代器
(InputIterator)輸出型迭代器
(OutputIterator)前向型迭代器(ForwardIterator)雙向型迭代器(BidirectionalIterator)隨機訪問型迭代器(RandomIterator)后者包含前者,功能越強具體迭代器的類型定義在相應容器的頭文件中,預定義迭代器定義在<iterator>中抽象的語義描述,不是具體的類7/50Input能力弱單步向前讀取元素單步:自增iter++或++iter,錯:iter+1向前:不能反向。錯:iter--,iter-1讀?。翰荒軐懭氲魉冈亍?/p>
對:…=*iter,錯:*iter=…迭代器賦值與比較iter1=iter2<><=>=!===STL預定義迭代器istream迭代器迭代器語義分類本章“非可變序列算法”用Input型迭代器,8/50Output能力弱單步向前寫入元素。類似Input,區(qū)別在于:Output:只能寫
*iter=…,不能讀…=*iterSTL預定義迭代器:ostream迭代器,inserter迭代器Forward能力弱單步向前讀寫元素。Input和Output的結合。Bidirectional能力較強單步雙向讀寫元素。在Forward基礎上增加:自減--支持所有的容器迭代器。Random能力強隨機讀寫元素,在Bidirectional基礎上增加:iter+i,iter–i,iter[i],iter.at(i)支持容器迭代器:vector,deque,string,array迭代器語義分類9/50MSDNThetemplateclassisaniteratoradaptorthatdescribesareverseiteratorobjectthatbehaveslikearandom-accessorbidirectionaliterator,onlyinreverse.Itenablesthebackwardtraversalofarange.template<classRandomIterator>classreverse_iterator{…}//所有標準容器都支持rbegin(),rend()
(const_)reverse_iterator
rbegin()(const_)reverse_iterator
rend()預定義迭代器:reverse_iterator10/50insert型迭代器Satisfiestherequirementsofanoutputiterator.Insertsratherthanoverwriteselementsintoasequence.Threeclasses:front,back,andgeneral.front_insert_iteratortemplate<classContainer>classfront_insert_iterator //類模板:創(chuàng)建迭代器對象{…}//---------------------------------------------------------------------------template<classContainer> //函數(shù)模板:直接調用front_insert_iterator<Container>front_inserter(
Container&_Cont); //指定容器:前插元素支持容器:deque,list.
有push_front()成員函數(shù)預定義迭代器:insert型11/50back_insert_iteratortemplate<classContainer>classback_insert_iterator //類模板:創(chuàng)建迭代器對象{…}//---------------------------------------------------------------------------template<classContainer> //函數(shù)模板:直接調用back_insert_iterator<Container>back_inserter( Container&_Cont); //指定容器:插入元素支持容器:vector,deque,list,string.有push_back()舉例:list<int>L;back_insert_iterator<list<int>>Iter(L);//創(chuàng)建迭代器對象*Iter=100;back_inserter(L)=200;//直接用模板函數(shù)預定義迭代器:insert型12/50insert_iteratortemplate<classContainer>classinsert_iterator //類模板:創(chuàng)建迭代器對象{…}//-------------------------------------------------------------------------template<classContainer> //函數(shù)模板:直接調用insert_iterator<Container>inserter(Container&_Cont, //指定容器:插入元素typenameContainer::iterator_Where);
_Where:
Aniteratorlocatingthepointofinsertion.支持容器:所有標準容器。都有insert()成員函數(shù)
對關聯(lián)容器而言,位置參數(shù)沒有意義預定義迭代器:insert型13/50advance()迭代器移動函數(shù)template<classInputIterator,classDistance>voidadvance( //函數(shù)模板
InputIterator
&_InIt,//_InIt:輸入型迭代器Distance_Off
//_Off:int,±移動量元素個數(shù));移動方向和增量_Off:后退-
+前進InputIterator:
所有容器迭代器都支持RandomIterator:隨機訪問c[i],c.at(i) vector,deque,string,array迭代器輔助函數(shù):advance()回顧14/50迭代器輔助函數(shù):advance()移動迭代器移動迭代器不支持隨機訪問并不提高時間效率方便了編程15/50distance()計算兩個迭代器之間的距離
元素個數(shù)template<classInputIterator
>intdistance(
InputIterator_First,
//from_Firstto_Last
InputIterator_Last );_Firstmustbeincrementeduntilitequal_Last.即:返回值>=0注:兩個迭代器必須是同一個容器的迭代器InputIterator:所有容器迭代器都支持iter_swap()函數(shù)的頭文件algorithm,不是輔助函數(shù)迭代器輔助函數(shù):distance()16/50迭代器輔助函數(shù):distance()17/50MSDNAppliesaspecifiedfunctionobjecttoeachelementinaforwardorderwithinarangeandreturnsthefunctionobject.template<classInputIterator,classFunction>Function
for_each(
//函數(shù)模板InputIterator_First, //迭代器:首個元素InputIterator_Last, //迭代器:最后元素
Function
_Func
//函數(shù)名或函數(shù)對象名);范圍:[_First,_Last)
如[begin(),end())循環(huán)算法
for_each()定義回顧18/50for_each()以vector舉例
ShowCube
有且只有一個參數(shù)(元素)19/50for_each()與函數(shù)對象以vector舉例函數(shù)對象類
Mult下頁定義函數(shù)對象類Mult修改初值函數(shù)對象類A下頁定義20/50for_each()與函數(shù)對象21/50MSDNLocatesthepositionofthefirstoccurrenceofanelementinarangethathasaspecifiedvalue.template<classInputIterator,classType>InputIterator
find(InputIterator_First,InputIterator_Last,
constType&_Val //指定值);
//_Val:常值或變量引用沒找到:返回_Last比較:元素值==_Val,若兩端類型不配:重載==查詢算法find()定義比較22/50查詢算法
find()find:范圍與結果以list舉例23/50MSDNLocatesthepositionofthefirstoccurrenceofanelementinarangethatsatisfiesaspecifiedcondition.template<classInputIterator,class
Predicate>InputIterator
find_if(InputIterator_First,InputIterator_Last,
Predicate
_Pred 謂詞:查找條件); 返回bool型的函數(shù)對象_Pred:user-definedpredicatefunctionobjectpredicate:takessingleargumentandreturnstrueorfalse.查詢算法find_if()定義比較一元謂詞24/50查詢算法find_if()以list舉例find_if
范圍與結果還有find_if_not()把find_if返回值求反
25/50MSDNSearchesfor1thefirstoccurrenceofanyofseveralvalueswithinatargetrangeor
for2thefirstoccurrenceofanyofseveralelementsthatareequivalentinasensespecifiedbyabinarypredicatetoaspecifiedsetoftheelements.匹配方式:
缺?。J)
template<classForwardIterator1,classForwardIterator2>ForwardIterator1
find_first_of( //返回:搜索容器的迭代器ForwardIterator1_First1, //搜索范圍:[_First1,_Last1)ForwardIterator1_Last1,ForwardIterator2_First2, //匹配范圍:[_First2,_Last2)ForwardIterator2_Last2);
兩個容器元素逐個匹配:搜索元素==目標元素,==可改變②
匹配過程:搜索容器中元素逐個與匹配容器的每個元素比較==查詢算法find_first_of()定義二元謂詞26/50匹配方式:二元謂詞指定
template<classForwardIterator1,classForwardIterator2,
class
BinaryPredicate>ForwardIterator1
find_first_of(ForwardIterator1_First1,//搜索范圍:[_First1,_Last1)ForwardIterator1_Last1,ForwardIterator2_First2,//匹配范圍:[_First2,_Last2)ForwardIterator2_Last2,
BinaryPredicate_Comp//二元謂詞:自編匹配條件); //缺?。孩?=_Comp:User-definedpredicatefunctionobjectthatdefinestheconditiontobesatisfiediftwoelementsaretobetakenasequivalent.Abinarypredicatetakestwoargumentsandreturnstruewhensatisfiedandfalsewhennotsatisfied.查詢算法
find_first_of()定義27/50查詢算法find_first_of()匹配方式:缺省方式①匹配方式:謂詞指定②改為<,>等二元謂詞:自編匹配代碼28/50MSDNSearchesfortwoadjacentelementsthatareeitherequalorsatisfyaspecifiedcondition.template<classForwardIterator>
ForwardIterator
adjacent_find( ForwardIterator_First, ForwardIterator_Last
);template<classForwardIterator,classBinaryPredicate>
ForwardIterator
adjacent_find(ForwardIterator_First,ForwardIterator_Last,
BinaryPredicate_Comp//二元謂詞:匹配條件
); //缺?。?=查詢算法adjacent_find()定義29/50查詢算法adjacent_find()缺省方式謂詞指定以deque舉例30/50查詢算法search()和find_end()回顧子序列匹配與find_first_of的區(qū)別是?31/50MSDNSearchesforthefirstsubsequenceinarangethatofaspecifiednumberofelementshavingaparticularvalueorarelationtothatvalueasspecifiedbyabinarypredicate.template<classForwardIterator1,classDiff2,
classType,classBinaryPredicate>ForwardIterator1
search_n(ForwardIterator1_First1,//搜索范圍[_First1,_Last1)ForwardIterator1_Last1,Diff2_Count, //子序列元素個數(shù)(重復個數(shù))
constType&_Val, //子序列元素值(一個元素)
BinaryPredicate_Comp //缺?。?=);查詢算法
search_n()定義回顧32/50查詢算法
search_n()33/50MSDNReturnsthenumberofelementsinarangewhosevaluesmatchaspecifiedvalueorsatisfy
aspecifiedcondition.
count()
count_if()template<classInputIterator,classTypeorPredicate>int
count(//intcount_if(InputIterator_First, //range:[_First,_Last)InputIterator_Last,constType
&_Val //==aspecifiedvalue:count()
//Predicate_Pred
//aspecifiedcondition:count_if());計數(shù)算法
count/count_if()定義回顧34/50計數(shù)算法
count/count_if()count()?count_if()?以set
為例35/50MSDNComparestworangeselementbyelementeitherforequality1orequivalenceinasensespecifiedbyabinarypredicate2.template<classInputIterator1,classInputIterator2,classBinaryPredicate>bool
equal(InputIterator1_First1, //range:[_First1,Last1)InputIterator1_Last1, InputIterator2_First2, //第二個容器開始位置
BinaryPredicate_Comp//二元謂詞:自定義比較條件); //缺?。J):==比較算法equal()
定義回顧36/50比較算法
equal()equal()37/50MSDNComparestworangeselementbyelementeitherforequality1orequivalentinasensespecifiedbyabinarypredicate2.Return:
thefirstpositionwhereadifferenceoccurs.(2個容器)template<classInputIterator1,classInputIterator2,classBinaryPredicate>pair<InputIterator1,InputIterator2>
mismatch(InputIterator1_First1, //range:[_First1,Last1)InputIterator1_Last1, InputIterator2_First2, //第二個容器開始位置
BinaryPredicate_Comp //二元謂詞:自定義比較條件); //缺省==,可重載==pair<first,second
>:第一容器和第二容器不匹配的開始位置
若全匹配,分別位于二個容器的末尾比較算法mismatch()
定義回顧38/50比較算法mismatch()怎么定義變量:result誰和誰比較?39/50比較算法mismatch()
數(shù)組版以普通數(shù)組為例顯示數(shù)組名及每個元素怎么定義result?40/50比較算法mismatch()
自定義類型定義私有成員41/50比較算法mismatch()
自定義類型比較前例42/50MSDNCompareselementbyelementbetweentwosequencestodeterminewhichislesserofthetwo.template<classInputIterator1,classInputIterator2,classBinaryPredicate>bool
lexicographical_compare(InputIterator1_First1, //range1:不要求排序InputIterator1_Last1,InputIterator2_First2, //range2:不要求排序InputIterator2_Last2,
BinaryPredicate_Comp
); //比較謂詞。缺省<:不含==Returntrue:ifrange1is
lexicographicallylessthanrange2.lexicographically:一個接一個的逐個比較。類似字符串的比較方式,
但返回值只有bool型。字典式比較lexicographical_compare43/50字典式比較lexicographical_compare顯示數(shù)組所有元素a1<a1?a1<a2?44/50MSDNFindsthefirstoccurrenceoflargestelementinaspecifiedrangewheretheorderingcriterionmaybespecifiedbyabinarypredicate.template<
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度智能制造行業(yè)勞動合同解除及保密協(xié)議模板
- 2025年度購物中心店面轉租與租賃期滿續(xù)約合同
- 天津市2025年度租賃房屋裝修與維修責任協(xié)議
- 二零二五年度美容院轉讓合同附帶技術培訓與售后服務
- 二零二五年度專業(yè)培訓機構教師團隊建設與培養(yǎng)合同
- 2025年遂寧考從業(yè)資格證貨運試題
- 2025年銀川貨運從業(yè)資格證考試題目及答案解析
- 2025年商洛b2貨運資格證全題
- 2025年太原貨運從業(yè)資格考試模擬考試題及答案大全
- 2025年十堰a2駕駛證貨運從業(yè)資格證模擬考試
- Adobe-Illustrator-(Ai)基礎教程
- 沒頭腦和不高興-竇桂梅.精選優(yōu)秀PPT課件
- 鋼棧橋計算書(excel版)
- 租賃合同審批表
- 事業(yè)單位綜合基礎知識考試題庫 綜合基礎知識考試題庫.doc
- 巖石堅固性和穩(wěn)定性分級表
- 譯林初中英語教材目錄
- 律師事務所函[]第號
- 物業(yè)交付后工程維修工作機制
- 農(nóng)作物病蟲害專業(yè)化統(tǒng)防統(tǒng)治管理辦法
- 新形勢下如何做一名合格的鄉(xiāng)鎮(zhèn)干部之我見
評論
0/150
提交評論