本周課程主要內(nèi)容為STL6大部件中的迭代器猴贰、算法麦轰、泛函數(shù)和適配器淑倾。其中算法與其他STL部件的區(qū)別之一是算法是函數(shù)模板馏鹤，其他的是類模板。

1娇哆、各部件的關(guān)系

圖1.1

STL的6大部件是相互聯(lián)系的湃累。算法雖然對容器一無所知，但是它通過問答迭代器碍讨，通過迭代器實現(xiàn)了對容器的操作治力。當?shù)鳠o法回答迭代器的問題時，編譯就會報錯垄开。算法也是泛函數(shù)的應用場合之一琴许。適配器則是在容器、迭代器溉躲、泛函數(shù)的基礎(chǔ)上再次封裝榜田，用這三大部件實現(xiàn)所需功能。

2锻梳、迭代器

本節(jié)主要分兩部分：iterator_category和iterator_category對算法的影響箭券。

2.1 iterator_category

共有五種迭代器類型，其中input——farward——bidirectional——random_access疑枯，從右向左是依次繼承的關(guān)系辩块，還有一種單獨的類型為output_iterator。

圖2.1

圖2.2

圖2.3

本小節(jié)內(nèi)容小結(jié)如下：

（1）使用隨機訪問迭代器的容器：array荆永， vector废亭，deque；

使用雙向迭代器的容器：list具钥，紅黑樹作為底層支撐的容器豆村；

使用單向迭代器的容器：forward_list；

兩個特殊的迭代器類型：input迭代器（istream_iterator）和output迭代器（ostream_iterator）骂删；

（2）五種迭代器均是class掌动，是通過迭代器的萃取器來得到類型；

（3）istream_iterator和ostream_iterator的迭代器種類的格式相同宁玫，G2.9版中有兩個模板參數(shù)粗恢，G3.3和G4.9版本中有四個模板參數(shù)。

2.2? iterator_category對算法的影響

圖2.4

圖2.5

圖2.6

圖2.7

本小節(jié)內(nèi)容小結(jié)如下：

（1）distance：計算兩個迭代器間的距離時欧瘪，內(nèi)部首先會識別iterator的類型眷射，之后根據(jù)不同的迭代器類型調(diào)用不同的__distance(first, second, category())函數(shù)計算距離，category()是個臨時對象佛掖，表示iterator的類型妖碉；

（2）若可以直接相減則選用上述圖2.4中的方法2，尾-頭苦囱，速度快嗅绸；若不能直接相減則選用上述圖2.4中的方法1，一步一步走撕彤，計算總共走多少步鱼鸠；

（3）advance：實現(xiàn)iterator移動n個元素的位置時，其內(nèi)部會調(diào)用__advance(i, n, iterator_category(i)), iterator_category函數(shù)用于獲取iterator的類型羹铅，根據(jù)不同的迭代器類型調(diào)用不同的__advance函數(shù)蚀狰，如圖2.5所示，有3中情況职员，如果是input迭代器麻蹋，那么會將iterator逐個移動n個位置；如果是雙向迭代器焊切，那么會先判斷n是正整數(shù)還是負整數(shù)扮授，再決定是向前還是向后逐個移動芳室；如果是隨機訪問迭代器，那么直接將指針加n個位置刹勃；

（4）在調(diào)用distance,advance等這類重載的函數(shù)時堪侯，如果沒有特別對這種迭代器類型的實現(xiàn)函數(shù)，那么會根據(jù)迭代器類型的父類找到重載的函數(shù)荔仁，例如伍宦，若iterator是forward_iterator_tag，返回類型為inline乏梁，用方法1（原因為forward_iterator_tag繼承input）次洼；

（5）copy：實現(xiàn)復制內(nèi)容時，內(nèi)部有多出檢查遇骑，首先會檢查first和last的類型卖毁，如果是const char類型，那么會調(diào)用memmove()质蕉；如果是const wchar_t類型势篡，那么也會調(diào)用memmove()；如果是InputIterator類型模暗，那么就調(diào)用__copy_dispatch()禁悠，再去判斷是const T, 還是T，還是迭代器兑宇，如果是迭代器碍侦，那么會再去檢查是隨機的還是其他類型的迭代器，如果是指針類型隶糕，那么會利用type traits詢問它的拷貝構(gòu)造重不重要（has trivial op=(), has non-trivial op=()瓷产，對于不需要自己定義，可以使用編譯器給的默認拷貝構(gòu)造函數(shù)枚驻，才叫做不重要的拷貝構(gòu)造）濒旦；

（6）destroy和copy類似，都是會將傳入的類型做判斷再登，不同的類型采用不同的處理方式尔邓；

（7）unique_copy：(first, last, result)函數(shù)中result如果是outputIterator，由于output iterator無法read, 無法執(zhí)行result !=first, 對于這種情況的處理就不同于result傳入的是forward iterator锉矢。

3梯嗽、算法

總共介紹了12種算法，包括算法accumulate沽损、算法for_each灯节、算法replace,replace_if,replace_copy、算法count,cout_copy、算法find,find_if炎疆、算法sort以及算法binary_search卡骂。

圖3.1

圖3.2

圖3.3

圖3.4

圖3.5

圖3.6

圖3.7

圖3.8

本節(jié)內(nèi)容總結(jié)如下：

（1）accumulate(first, last, init)，元素直接相加磷雇；

accumulate(first, last, init, binary_op)偿警， 元素累計躏救，binary_op可以傳自定義的函數(shù)唯笙，或是泛函數(shù)，binary_op(init,first)這個函數(shù)定義了初值init和first之間的計算方法盒使；

（2）replace()是將first到last內(nèi)等于old_value的元素替換為new_value崩掘；

replace_if()這里predicate表示要傳一個能返回真假的判斷函數(shù)pred(*first), 返回真的話，會做替換少办；

replace_copy()是將將first到last區(qū)間內(nèi)的值拷貝給res, 如果是old_value苞慢，替換為new_value再拷貝給res，原有的值不做替換英妓；

（3）count(first, last, value) 對于其中等于value的元素進行計數(shù)挽放；

count_if(first, last, pred) 對于其中符合pred(*first)的元素進行計數(shù).；

如果容器中有自己的版本蔓纠，要用自己的辑畦，效率更高；

（4）sort(first, last, op); op可以是自定義比較大小的函數(shù)腿倚，也可以是泛函數(shù)纯出；

sort要求容器可跳躍，而list和forword_list不能跳躍敷燎；

（5）r.begin()和r.end()是通過reverse iterator實現(xiàn)的暂筝。

4、仿函數(shù)

總共分為三大類仿函數(shù)：算術(shù)類硬贯、邏輯運算類和相對關(guān)系類焕襟。標準庫提供的仿函數(shù)都有繼承關(guān)系。

圖4.1

圖4.2

圖4.3

本節(jié)內(nèi)容總結(jié)如下：

（1）identify饭豹、select1st鸵赖、select2nd是GUN C++獨有的仿函數(shù)，是非標準的墨状，identify傳入什么元素就傳出什么元素,select1st傳入pair, 傳出pair中第一個元素,select2nd傳入pair, 傳出pair中第二個元素;

G4.9版本中名稱有所改變卫漫，_Identify、_Select1st肾砂、_Select2nd列赎；

（2）3種仿函數(shù)的共同點：都是繼承自unary_function或是binary_function類，他們內(nèi)部定義了一些typedef, 共適配器詢問，他們的內(nèi)部并沒有數(shù)據(jù)成員包吝，對于自定義的泛函數(shù)只有遵循STL的體系架構(gòu)饼煞，繼承于unary_function或是binary_function才能作為泛函數(shù)適配器。

5诗越、適配器

適配器可以改造泛函數(shù)砖瞧、迭代器和容器。適配器中可以擁有泛函數(shù)嚷狞、迭代器或容器块促。

圖5.1

圖5.2

圖5.3

圖5.4

圖5.5

圖5.6

本節(jié)內(nèi)容總結(jié)如下：

（1）A改造B，A需要取用B的功能床未，有兩種實現(xiàn)方法：A繼承B或者A擁有B竭翠，適配器中使用的是A擁有B這種方法；

（2）binder2nd（泛函數(shù)適配器）：2nd指第二參數(shù)薇搁，bind2nd(less(), 40)給less函數(shù)綁定第二個參數(shù)為40斋扰，使得第一個參數(shù)和40進行比較，這里less()是一個臨時對象啃洋，并沒有被調(diào)用 传货；

（3） not1(泛函數(shù)適配器)：not1(pred), 對pred的結(jié)果取非;

（4）bind （新型適配器）：C++11標準中才有，可以綁定函數(shù)宏娄、泛函问裕、成員函數(shù)（_1必須是某個object地址）、數(shù)據(jù)成員（_1必須是某個object地址）绝编；

（5）inserter（迭代器適配器）：是函數(shù)模板僻澎，將元素插入到另一個容器中。copy(bar.begin(), bar.end(), inserter(foo, it)); 將bar的元素全部插入到foo容器的it位置十饥，并不覆蓋foo原有的元素窟勃，如果是copy(bar.begin(), bar.end(), foo.begin());這樣寫會覆蓋foo中原有的元素；

（6）ostream_iterator（X適配器逗堵，三大類之外的適配器）：其內(nèi)部定義了拷貝賦值函數(shù)秉氧，將value賦值給標準輸出，所以copy會調(diào)用ostream_iterator的拷貝賦值蜒秤，輸出各個元素汁咏；

ostream_iterator相當于count（輸出），istream_iterator相當于cin（輸入）作媚。

6攘滩、課堂難點知識理解

（1）inserter

C++ 語言提供了三種插入器，其差別在于插入元素的位置不同纸泡。

back_inserter漂问，創(chuàng)建使用push_back實現(xiàn)插入的迭代器。

front_inserter，使用push_front實現(xiàn)插入蚤假。

inserter栏饮，使用insert實現(xiàn)插入操作。

也許有人認為可使用inserter和容器的begin迭代器來模擬front_inserter的效果磷仰。然而袍嬉，inserter的行為與front_inserter的有很大差別。在使用front_inserter時灶平，元素始終在容器的第一個元素前面插入伺通。而使用inserter時，元素則在指定位置前面插入民逼。即使此指定位置初始化為容器中的第一個元素泵殴，但是，一旦在該位置前插入一個新元素后拼苍，插入位置就不再是容器的首元素了。

（2）ostream_iterator

ostream_iterator是流迭代器调缨，流迭代器是標準模板庫中的疮鲫，因此是類模板。

ostream_iterator<int>指定了類型弦叶，就是迭代器讀寫的類型俊犯。通過這個流迭代器可以把你要輸入的寫入到指定的流中。cout就是指定的流,就是標準輸出伤哺⊙嘞溃可以改成一個輸出流就可以，比如一個文件立莉。通俗的一點說绢彤，你把它看成一個指向輸出流的指針,通過這個指針你可以把東西寫的輸出流中。

copy (v.begin(),v.end(),output);這個意思就是說蜓耻，把向量V中的數(shù)據(jù)放到cout輸出流中茫舶，通過流迭代器output.

ostream_iterator output(cout ,"*");這個的意思說，放到輸出流的時候刹淌，沒放一個整數(shù)饶氏，就末尾添加一個*.