本周課程主要內(nèi)容為STL6大部件中的迭代器、算法、泛函數(shù)和適配器。其中算法與其他STL部件的區(qū)別之一是算法是函數(shù)模板，其他的是類模板。
1、各部件的關(guān)系
STL的6大部件是相互聯(lián)系的。算法雖然對容器一無所知，但是它通過問答迭代器，通過迭代器實現(xiàn)了對容器的操作。當(dāng)?shù)鳠o法回答迭代器的問題時，編譯就會報錯。算法也是泛函數(shù)的應(yīng)用場合之一。適配器則是在容器、迭代器、泛函數(shù)的基礎(chǔ)上再次封裝，用這三大部件實現(xiàn)所需功能。
2、迭代器
本節(jié)主要分兩部分：iterator_category和iterator_category對算法的影響。
2.1 iterator_category
共有五種迭代器類型，其中input——farward——bidirectional——random_access，從右向左是依次繼承的關(guān)系，還有一種單獨的類型為output_iterator。
本小節(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對算法的影響
本小節(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ù)還是負(fù)整數(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)復(fù)制內(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=()，對于不需要自己定義，可以使用編譯器給的默認(rèn)拷貝構(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。
本節(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)系類。標(biāo)準(zhǔn)庫提供的仿函數(shù)都有繼承關(guān)系。
本節(jié)內(nèi)容總結(jié)如下：
（1）identify、select1st、select2nd是GUN C++獨有的仿函數(shù)，是非標(biāo)準(zhǔn)的，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ù)、迭代器或容器。
本節(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標(biāo)準(zhǔn)中才有，可以綁定函數(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賦值給標(biāo)準(zhǔn)輸出，所以copy會調(diào)用ostream_iterator的拷貝賦值，輸出各個元素；
ostream_iterator相當(dāng)于count（輸出），istream_iterator相當(dāng)于cin（輸入）。
6、課堂難點知識理解
（1）inserter
C++ 語言提供了三種插入器，其差別在于插入元素的位置不同。
back_inserter，創(chuàng)建使用push_back實現(xiàn)插入的迭代器。
front_inserter，使用push_front實現(xiàn)插入。
inserter，使用insert實現(xiàn)插入操作。
也許有人認(rèn)為可使用inserter和容器的begin迭代器來模擬front_inserter的效果。然而，inserter的行為與front_inserter的有很大差別。在使用front_inserter時，元素始終在容器的第一個元素前面插入。而使用inserter時，元素則在指定位置前面插入。即使此指定位置初始化為容器中的第一個元素，但是，一旦在該位置前插入一個新元素后，插入位置就不再是容器的首元素了。
（2）ostream_iterator
ostream_iterator是流迭代器，流迭代器是標(biāo)準(zhǔn)模板庫中的，因此是類模板。
ostream_iterator<int>指定了類型，就是迭代器讀寫的類型。通過這個流迭代器可以把你要輸入的寫入到指定的流中。cout就是指定的流,就是標(biāo)準(zhǔn)輸出?？梢愿某梢粋€輸出流就可以，比如一個文件。通俗的一點說，你把它看成一個指向輸出流的指針,通過這個指針你可以把東西寫的輸出流中。
copy (v.begin(),v.end(),output);這個意思就是說，把向量V中的數(shù)據(jù)放到cout輸出流中，通過流迭代器output.
ostream_iterator output(cout ,"*");這個的意思說，放到輸出流的時候，沒放一個整數(shù)，就末尾添加一個*.
