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

第六~七章非可變序列算法與迭代器算法分類(lèi)迭代器及其分類(lèi)循環(huán)算法查詢算法計(jì)數(shù)算法比較算法1／50算法、容器、迭代器、函數(shù)對(duì)象之關(guān)系圖STL

算法概述容器1某算法迭代器1讀取寫(xiě)入?yún)?shù)傳入返回容器2迭代器2讀取寫(xiě)入?yún)?shù)傳入返回容器n迭代器n讀取寫(xiě)入?yún)?shù)傳入返回…………函數(shù)對(duì)象參數(shù)傳入算法通過(guò)迭代器去操作容器中數(shù)據(jù)2／50MSDNTheSTLalgorithmsaregenericbecausetheycanoperateonavarietyofdatastructures.Thedatastructuresthattheycanoperateonincludenotonly

theSTLcontainer

classessuchasvectorandlist,butalso

program-defineddatastructuresandarraysofelementsthatsatisfytherequirementsofaparticularalgorithm.STLalgorithmsachievethislevelofgeneralitybyaccessingandtraversingtheelementsofacontainerindirectlythroughiterators.TheSTLalgorithmsextendtheactionssupportedbytheoperationsandmemberfunctionsofeachSTLcontainerandallowworking,forexample,withdifferenttypesofcontainerobjectsatthesametime.STL

算法概述3／50算法和容器成員函數(shù)的區(qū)別算法：函數(shù)模板，不是容器(類(lèi)模板)的成員函數(shù)

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

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

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

算法要修改容器元素的值或順序復(fù)制、填充、交換、變換、替換、生成、刪除、反轉(zhuǎn)、唯一、環(huán)移、分區(qū)、搬移、隨機(jī)重排。排序相關(guān)算法排序、折半查找、歸并排序、有序集操作、堆排序數(shù)值算法復(fù)數(shù)運(yùn)算、向量運(yùn)算(值數(shù)組valarray)、通用數(shù)值計(jì)算(求和、內(nèi)積、部分和、序列相鄰差)STL算法分類(lèi)5／50非可變序列算法功能函數(shù)名稱(chēng)說(shuō)

明循環(huán)for_each()

對(duì)每個(gè)元素執(zhí)行同一指定操作，返回函數(shù)對(duì)象查詢find()

返回元素值=指定值的第一次出現(xiàn)位置find_if()

返回元素值符合謂詞函數(shù)對(duì)象的第一次出現(xiàn)位置迭代器find_first_of()

返回元素值=指定值之一的第一次出現(xiàn)位置adjacent_find()

返回相鄰元素值相等的第一次出現(xiàn)位置find_end()

返回指定子序列匹配的最后一次出現(xiàn)位置search()

返回指定子序列匹配的第一次出現(xiàn)位置search_n

返回元素值=指定值、連續(xù)n次匹配的第一次位置計(jì)數(shù)count()

返回元素值=指定值的元素個(gè)數(shù)count_if()

返回元素值符合謂詞的元素個(gè)數(shù)比較equal()

返回true：兩個(gè)序列的對(duì)應(yīng)元素都相等mismatch()

返回兩個(gè)序列不同的第一個(gè)元素位置

2個(gè)容器的位置min_element()

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

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

(InputIterator)輸出型迭代器

(OutputIterator)前向型迭代器(ForwardIterator)雙向型迭代器(BidirectionalIterator)隨機(jī)訪問(wèn)型迭代器(RandomIterator)后者包含前者，功能越強(qiáng)具體迭代器的類(lèi)型定義在相應(yīng)容器的頭文件中，預(yù)定義迭代器定義在<iterator>中抽象的語(yǔ)義描述，不是具體的類(lèi)7／50Input能力弱單步向前讀取元素單步：自增iter++或++iter，錯(cuò)：iter+1向前：不能反向。錯(cuò)：iter--，iter-1讀取：不能寫(xiě)入迭代器所指元素。

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

*iter=…，不能讀…=*iterSTL預(yù)定義迭代器：ostream迭代器,inserter迭代器Forward能力弱單步向前讀寫(xiě)元素。Input和Output的結(jié)合。Bidirectional能力較強(qiáng)單步雙向讀寫(xiě)元素。在Forward基礎(chǔ)上增加：自減--支持所有的容器迭代器。Random能力強(qiáng)隨機(jī)讀寫(xiě)元素，在Bidirectional基礎(chǔ)上增加：iter+i,iter–i,iter[i],iter.at(i)支持容器迭代器：vector,deque,string,array迭代器語(yǔ)義分類(lèi)9／50MSDNThetemplateclassisaniteratoradaptorthatdescribesareverseiteratorobjectthatbehaveslikearandom-accessorbidirectionaliterator,onlyinreverse.Itenablesthebackwardtraversalofarange.template<classRandomIterator>classreverse_iterator{…}//所有標(biāo)準(zhǔn)容器都支持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 //類(lèi)模板：創(chuàng)建迭代器對(duì)象{…}//---------------------------------------------------------------------------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 //類(lèi)模板：創(chuàng)建迭代器對(duì)象{…}//---------------------------------------------------------------------------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)建迭代器對(duì)象*Iter=100;back_inserter(L)=200;//直接用模板函數(shù)預(yù)定義迭代器：insert型12／50insert_iteratortemplate<classContainer>classinsert_iterator //類(lèi)模板：創(chuàng)建迭代器對(duì)象{…}//-------------------------------------------------------------------------template<classContainer> //函數(shù)模板：直接調(diào)用insert_iterator<Container>inserter(Container&_Cont, //指定容器：插入元素typenameContainer::iterator_Where);

_Where:

Aniteratorlocatingthepointofinsertion.支持容器：所有標(biāo)準(zhǔn)容器。都有insert()成員函數(shù)

對(duì)關(guān)聯(lián)容器而言，位置參數(shù)沒(méi)有意義預(yù)定義迭代器：insert型13／50advance()迭代器移動(dòng)函數(shù)template<classInputIterator,classDistance>voidadvance( //函數(shù)模板

InputIterator

&_InIt,//_InIt:輸入型迭代器Distance_Off

//_Off:int,±移動(dòng)量元素個(gè)數(shù));移動(dòng)方向和增量_Off：后退-

+前進(jìn)InputIterator：

所有容器迭代器都支持RandomIterator：隨機(jī)訪問(wèn)c[i],c.at(i) vector,deque,string,array迭代器輔助函數(shù)：advance()回顧14／50迭代器輔助函數(shù)：advance()移動(dòng)迭代器移動(dòng)迭代器不支持隨機(jī)訪問(wèn)并不提高時(shí)間效率方便了編程15／50distance()計(jì)算兩個(gè)迭代器之間的距離

元素個(gè)數(shù)template<classInputIterator

>intdistance(

InputIterator_First,

//from_Firstto_Last

InputIterator_Last );_Firstmustbeincrementeduntilitequal_Last.即：返回值>=0注：兩個(gè)迭代器必須是同一個(gè)容器的迭代器InputIterator：所有容器迭代器都支持iter_swap()函數(shù)的頭文件algorithm,不是輔助函數(shù)迭代器輔助函數(shù)：distance()16／50迭代器輔助函數(shù)：distance()17／50MSDNAppliesaspecifiedfunctionobjecttoeachelementinaforwardorderwithinarangeandreturnsthefunctionobject.template<classInputIterator,classFunction>Function

for_each(

//函數(shù)模板InputIterator_First, //迭代器：首個(gè)元素InputIterator_Last, //迭代器：最后元素

Function

_Func

//函數(shù)名或函數(shù)對(duì)象名);范圍：[_First,_Last)

如[begin(),end())循環(huán)算法

for_each()定義回顧18／50for_each()以vector舉例

ShowCube

有且只有一個(gè)參數(shù)(元素)19／50for_each()與函數(shù)對(duì)象以vector舉例函數(shù)對(duì)象類(lèi)

Mult下頁(yè)定義函數(shù)對(duì)象類(lèi)Mult修改初值函數(shù)對(duì)象類(lèi)A下頁(yè)定義20／50for_each()與函數(shù)對(duì)象21／50MSDNLocatesthepositionofthefirstoccurrenceofanelementinarangethathasaspecifiedvalue.template<classInputIterator,classType>InputIterator

find(InputIterator_First,InputIterator_Last,

constType&_Val //指定值);

//_Val：常值或變量引用沒(méi)找到：返回_Last比較：元素值==_Val，若兩端類(lèi)型不配：重載==查詢算法find()定義比較22／50查詢算法

find()find:范圍與結(jié)果以list舉例23／50MSDNLocatesthepositionofthefirstoccurrenceofanelementinarangethatsatisfiesaspecifiedcondition.template<classInputIterator,class

Predicate>InputIterator

find_if(InputIterator_First,InputIterator_Last,

Predicate

_Pred 謂詞：查找條件); 返回bool型的函數(shù)對(duì)象_Pred:user-definedpredicatefunctionobjectpredicate:takessingleargumentandreturnstrueorfalse.查詢算法find_if()定義比較一元謂詞24／50查詢算法find_if()以list舉例find_if

范圍與結(jié)果還有find_if_not()把find_if返回值求反

25／50MSDNSearchesfor1thefirstoccurrenceofanyofseveralvalueswithinatargetrangeor

for2thefirstoccurrenceofanyofseveralelementsthatareequivalentinasensespecifiedbyabinarypredicatetoaspecifiedsetoftheelements.匹配方式：

缺?。J(rèn)）

template<classForwardIterator1,classForwardIterator2>ForwardIterator1

find_first_of( //返回：搜索容器的迭代器ForwardIterator1_First1, //搜索范圍：[_First1,_Last1)ForwardIterator1_Last1,ForwardIterator2_First2, //匹配范圍：[_First2,_Last2)ForwardIterator2_Last2);

兩個(gè)容器元素逐個(gè)匹配：搜索元素==目標(biāo)元素，==可改變②

匹配過(guò)程：搜索容器中元素逐個(gè)與匹配容器的每個(gè)元素比較==查詢算法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, //子序列元素個(gè)數(shù)（重復(fù)個(gè)數(shù)）

constType&_Val, //子序列元素值（一個(gè)元素）

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());計(jì)數(shù)算法

count／count_if()定義回顧34／50計(jì)數(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, //第二個(gè)容器開(kāi)始位置

BinaryPredicate_Comp//二元謂詞：自定義比較條件); //缺?。J(rèn)）：==比較算法equal()

定義回顧36／50比較算法

equal()equal()37／50MSDNComparestworangeselementbyelementeitherforequality1orequivalentinasensespecifiedbyabinarypredicate2.Return:

thefirstpositionwhereadifferenceoccurs.（2個(gè)容器）template<classInputIterator1,classInputIterator2,classBinaryPredicate>pair<InputIterator1,InputIterator2>

mismatch(InputIterator1_First1, //range:[_First1,Last1)InputIterator1_Last1, InputIterator2_First2, //第二個(gè)容器開(kāi)始位置

BinaryPredicate_Comp //二元謂詞：自定義比較條件); //缺省==，可重載==pair<first,second

>：第一容器和第二容器不匹配的開(kāi)始位置

若全匹配，分別位于二個(gè)容器的末尾比較算法mismatch()

定義回顧38／50比較算法mismatch()怎么定義變量：result誰(shuí)和誰(shuí)比較？39／50比較算法mismatch()

數(shù)組版以普通數(shù)組為例顯示數(shù)組名及每個(gè)元素怎么定義result?40／50比較算法mismatch()

自定義類(lèi)型定義私有成員41／50比較算法mismatch()

自定義類(lèi)型比較前例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:一個(gè)接一個(gè)的逐個(gè)比較。類(lèi)似字符串的比較方式，

但返回值只有bool型。字典式比較lexicographical_compare43／50字典式比較lexicographical_compare顯示數(shù)組所有元素a1<a1?a1<a2?44／50MSDNFindsthefirstoccurrenceoflargestelementinaspecifiedrangewheretheorderingcriterionmaybespecifiedbyabinarypredicate.template<