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

第六~七章非可變序列算法與迭代器算法分類迭代器及其分類循環(huán)算法查詢算法計數(shù)算法比較算法1／50算法、容器、迭代器、函數(shù)對象之關(guān)系圖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ù)

——直接使用，不是通過容器對象調(diào)用算法：有些與容器的成員函數(shù)同名且功能相同

——用法不同頭文件算法：<algorithm>數(shù)值算法：<numeric>函數(shù)對象：<functional>STL算法概述4／50STL算法分類非可變序列算法

算法不修改容器元素的值或順序for_each、線性查找、子序列匹配、元素個數(shù)、元素比較、最大與最小值可變序列算法

算法要修改容器元素的值或順序復(fù)制、填充、交換、變換、替換、生成、刪除、反轉(zhuǎn)、唯一、環(huán)移、分區(qū)、搬移、隨機重排。排序相關(guān)算法排序、折半查找、歸并排序、有序集操作、堆排序數(shù)值算法復(fù)數(shù)運算、向量運算(值數(shù)組valarray)、通用數(shù)值計算(求和、內(nèi)積、部分和、序列相鄰差)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：兩個序列的對應(yīng)元素都相等mismatch()

返回兩個序列不同的第一個元素位置

2個容器的位置min_element()

返回最小值元素的位置max_element()

返回最大值元素的位置關(guān)系6／50迭代器語義分類功能輸入型迭代器

(InputIterator)輸出型迭代器

(OutputIterator)前向型迭代器(ForwardIterator)雙向型迭代器(BidirectionalIterator)隨機訪問型迭代器(RandomIterator)后者包含前者，功能越強具體迭代器的類型定義在相應(yīng)容器的頭文件中，預(yù)定義迭代器定義在<iterator>中抽象的語義描述，不是具體的類7／50Input能力弱單步向前讀取元素單步：自增iter++或++iter，錯：iter+1向前：不能反向。錯：iter--，iter-1讀?。翰荒軐懭氲魉冈?。

對：…=*iter，錯：*iter=…迭代器賦值與比較iter1=iter2<><=>=!===STL預(yù)定義迭代器istream迭代器迭代器語義分類本章“非可變序列算法”用Input型迭代器，8／50Output能力弱單步向前寫入元素。類似Input，區(qū)別在于：Output：只能寫

*iter=…，不能讀…=*iterSTL預(yù)定義迭代器：ostream迭代器,inserter迭代器Forward能力弱單步向前讀寫元素。Input和Output的結(jié)合。Bidirectional能力較強單步雙向讀寫元素。在Forward基礎(chǔ)上增加：自減--支持所有的容器迭代器。Random能力強隨機讀寫元素，在Bidirectional基礎(chǔ)上增加：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()預(yù)定義迭代器：reverse_iterator10／50insert型迭代器Satisfiestherequirementsofanoutputiterator.Insertsratherthanoverwriteselementsintoasequence.Threeclasses:front,back,andgeneral.front_insert_iteratortemplate<classContainer>classfront_insert_iterator //類模板：創(chuàng)建迭代器對象{…}//---------------------------------------------------------------------------template<classContainer> //函數(shù)模板：直接調(diào)用front_insert_iterator<Container>front_inserter(

Container&_Cont); //指定容器：前插元素支持容器：deque,list.

有push_front()成員函數(shù)預(yù)定義迭代器：insert型11／50back_insert_iteratortemplate<classContainer>classback_insert_iterator //類模板：創(chuàng)建迭代器對象{…}//---------------------------------------------------------------------------template<classContainer> //函數(shù)模板：直接調(diào)用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ù)預(yù)定義迭代器：insert型12／50insert_iteratortemplate<classContainer>classinsert_iterator //類模板：創(chuàng)建迭代器對象{…}//-------------------------------------------------------------------------template<classContainer> //函數(shù)模板：直接調(diào)用insert_iterator<Container>inserter(Container&_Cont, //指定容器：插入元素typenameContainer::iterator_Where);

_Where:

Aniteratorlocatingthepointofinsertion.支持容器：所有標準容器。都有insert()成員函數(shù)

對關(guān)聯(lián)容器而言，位置參數(shù)沒有意義預(yù)定義迭代器：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:范圍與結(jié)果以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

范圍與結(jié)果還有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ù)（重復(fù)個數(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<