體系結(jié)構(gòu)與內(nèi)核分析第三講

算法

從語言層面講（標(biāo)準(zhǔn)庫六大部件）：

容器Container是個(gè)class template

算法Algorithm是個(gè)function template

迭代器Iterator是個(gè)class template

仿函數(shù)Functor是個(gè)class template

適配器Adapter是個(gè)class template

分配器Allocator是個(gè)class template

算法（Algorithm）看不見容器（Container）箕宙，彼此無直接關(guān)聯(lián)充岛，對(duì)其一無所知症昏；所以，它所需要的一切信息都必須從迭代器（Iterators）取得，而Iterators（Containers供應(yīng)）必須能夠回答Algorithm的所有提問蜕乡，才能搭配該Algorithm的所有操作空民。

迭代器的分類

五種iterator category

struct input_iterator_tag{ };（輸入迭代器）

struct output_iterator_tag{ };（輸出迭代器）

struct forward_iterator_tag;public input_iterator_tag{ }; （單向迭代器）前向

struct bidrectional_iterator_tag;public forward_iterator_tag{ }; （雙向迭代器）

struct random_access_iterator_tag;public bidrectional_iterator_tag{ };（隨機(jī)訪問迭代器）空間是連續(xù)的

五種iterator的關(guān)系

共有五種迭代器類型，其中四種是相互繼承的關(guān)系input（父類）<-farward<-bidirectional<-random_access（子類）. 還有一種output_iterator是單獨(dú)的酪呻。

容器種類

random_access_iterator_tag（隨機(jī)訪問迭代器）：array,vector,deque

bidrectional_iterator_tag（雙向迭代器）：list,set,map,multiset,multimap

forward_iterator_tag（單向迭代器）：forward_list, unordered_set, unordered_map, unordered_multiset, unordered_multimap

output_iterator_tag（輸出迭代器）：ostream

input_iterator_tag（輸入迭代器）：istream

查看迭代器 category：

display_category(array::iterator());

cout<<"typeid(itr).name()="<

迭代器分類對(duì)算法的影響

random_access_iterator_tag空間是連續(xù)的

判斷了迭代器分類后distance算法的執(zhí)行效率相差非常大：1.為random_access_iterator直接last-first 2.其他的一步步計(jì)算减宣，效率低

其他算法也會(huì)先判斷迭代器分類然后采取不同策略以期提高效率。

以copy算法為例玩荠，通過迭代器的分類和迭代器萃取機(jī)的分類漆腌，對(duì)于某些分類有特化版本贼邓，直接調(diào)用低階動(dòng)作函數(shù)速度極快，針對(duì)不同分類采取不同策略闷尿，這樣極大提高了代碼效率塑径。

算法源碼中對(duì)iterator_category的暗示：通過寫出一些明顯的類型名稱

算法源代碼剖析

qsort（快速排序）,bsearch(二分法搜尋）均為C語言的函數(shù)function；count_if（返回在[first, last)范圍內(nèi)滿足特定條件的元素的數(shù)目）,find（查找）,sort（排序）是C++標(biāo)準(zhǔn)庫提供的算法填具。

accumulate：用來計(jì)算特定范圍內(nèi)（包括連續(xù)的部分和初始值）所有元素的和统舀，除此之外，還可以用指定的二進(jìn)制操作來計(jì)算特定范圍內(nèi)的元素結(jié)果劳景。兩個(gè)版本：1.接受頭尾兩個(gè)指針還有初值2.接受頭尾兩個(gè)指針誉简，初值還有binaryoperation。

for_each：用于逐個(gè)遍歷容器元素盟广，它對(duì)迭代器區(qū)間[first闷串，last)所指的每一個(gè)元素，執(zhí)行由單參數(shù)函數(shù)對(duì)象f所定義的操作筋量。接受頭尾兩個(gè)指針還有一個(gè)function烹吵。

//range-based for statement since C++11

for( dec1:coll ) {

statement

}

for( int i : {2,3,4,5,3,23,424,5} ){

cout << i << endl;

}

在前面的學(xué)習(xí)中也有涉及

算法replace，replace_if,replace_copy

replace： 所有容器適用,范圍內(nèi)所有等同于old_value者都以new_value取代.

replace_if：范圍內(nèi)所有滿足pred()（特定條件）為true之元素都以new_value取代.

replace_copy：范圍內(nèi)所有等同于old_value者都以new_value放至新區(qū)間.

count：用于統(tǒng)計(jì)某一值在一定范圍內(nèi)出現(xiàn)的次數(shù)

count_if：返回在[first, last)范圍內(nèi)滿足特定條件的元素的數(shù)目

容器不帶成員函數(shù)count()：array,vector,list,forward_list,deque

容器帶有成員函數(shù)count()：set/multiset桨武，map/multimap肋拔，unordered_set/unordered_multiset,unordered_map/unordered_multimap

find：返回區(qū)間[first，end）中第一個(gè)值等于value的元素位置玻募；若未找到只损，返回end。函數(shù)返回的是迭代器或指針七咧，即位置信息跃惫。循序式查找

find_if：返回區(qū)間[first，end)中使一元判斷式pred為true的第一個(gè)元素位置艾栋；若未找到爆存，返回end。循序式查找

容器不帶成員函數(shù)find()：array,vector,list,forward_list,deque

容器帶有成員函數(shù)find()：set/multiset蝗砾，map/multimap先较，unordered_set/unordered_multiset,unordered_map/unordered_multimap

sort：對(duì)給定區(qū)間所有元素進(jìn)行排序

容器不帶成員函數(shù)count()：array,vector,deque, set/multiset，map/multimap悼粮，unordered_set/unordered_multiset,unordered_map/unordered_multimap

容器帶有成員函數(shù)count()：list,forward_list

reverse iterator是一種反向遍歷容器的迭代器rbegin()++-

binary_search二分查找法闲勺，之前一定要先排序，調(diào)用的是lower_bound,與之相對(duì)應(yīng)的有upper_bound扣猫。

low=lower_bound(v.begin(),v.end(),20);

up=upper_bound(v.begin(),v.end(),20);

仿函數(shù)/函數(shù)對(duì)象

按照功能的不同菜循，仿函數(shù)functors可分為算術(shù)類（plus, minus...），邏輯運(yùn)算類（logical_and...）申尤，相對(duì)關(guān)系類（equal_to, less...）等三種

算術(shù)類：return x+y;return x-y;

邏輯類：return x&&y;

關(guān)系類：return x==y;return x

gnu c++獨(dú)有的泛函:下面是G2.9下的泛函G4.9的名稱改了癌幕。

identify傳入什么元素就傳出什么元素衙耕。

select1st傳入pair, 傳出pair中第一個(gè)元素。

select2nd傳入pair, 傳出pair中第二個(gè)元素勺远。

可適配條件：他們的共同點(diǎn)在于繼承自u(píng)nary_function（一個(gè)操作數(shù)）或是binary_function（兩個(gè)操作數(shù)）類橙喘，他們內(nèi)部定義了一些typedef, 共適配器詢問，他們的內(nèi)部并沒有數(shù)據(jù)成員胶逢，對(duì)于自定義的泛函數(shù)只有遵循stl的體系架構(gòu)厅瞎，繼承于unary_function或是binary_function才能作為泛函數(shù)適配器。繼承binary_function的意義在于宪塔，告訴算法傳進(jìn)來的是二元運(yùn)算磁奖。仿函數(shù)在傳遞進(jìn)算法的時(shí)候囊拜，需要告訴算法兩個(gè)參與運(yùn)算的類型某筐，以及一個(gè)用于接受結(jié)果的類型。

適配器Adapters

適配器按照類型的不同冠跷，可分為容器適配器南誊、迭代器適配器和仿函數(shù)適配器三種

函數(shù)適配器：binder2nd

eg. bind2nd(less(), 40)給less函數(shù)綁定第二個(gè)參數(shù)為40，使得第一個(gè)參數(shù)和40進(jìn)行比較蜜托，這里less()是一個(gè)臨時(shí)對(duì)象抄囚，并沒有被調(diào)用 。bind2nd內(nèi)部調(diào)用binder2nd, 重載()（這里會(huì)詢問less第一個(gè)參數(shù)類型和返回值類型）橄务，將操作的第二個(gè)參數(shù)傳入綁定的值幔托，再以返回值的形式傳出操作。對(duì)于需要綁定的值在調(diào)用binder2nd的時(shí)候會(huì)檢查蜂挪，首先bind2nd會(huì)向operation詢問他的第二個(gè)參數(shù)的類型重挑，之后創(chuàng)建一個(gè)這個(gè)類型的臨時(shí)對(duì)象，并將需要綁定的值賦給它棠涮。這時(shí)會(huì)檢查類型是否匹配谬哀。typename是因?yàn)榫幾g器在編譯時(shí)還不知道其要傳入的類型，所以要告訴編譯器這是一個(gè)類型严肪。

新型適配器 bind可以替代bind1st史煎、bind2nd、binder1st驳糯、binder2nd篇梭。

泛函數(shù)適配器： not1

not1(pred), 對(duì)pred的結(jié)果取非。

bind (C++11) 可以綁定函數(shù)酝枢、泛函恬偷、成員函數(shù)（_1必須是某個(gè)object地址）、數(shù)據(jù)成員（_1必須是某個(gè)object地址）隧枫。返回一個(gè)函數(shù)對(duì)象ret喉磁，調(diào)用ret相當(dāng)于調(diào)用函數(shù)谓苟、泛函、成員函數(shù)或者相當(dāng)于取出數(shù)據(jù)成員协怒。

迭代器適配器

reverse_iterator

rbegin()

{return reverse_iterator(end());}

reverse_iterator

rend()

{return reverse_iterator(begin());}

self&operator++(){--current;return *this;}

self&operator--(){++current;return *this;}

rend()——begin()? ? ? ? ? ? rbegin()—— end()

reverse_iterator類中有一個(gè)正向迭代器涝焙，都是由這個(gè)正向迭代器實(shí)現(xiàn)的。

inserter是個(gè)函數(shù)模板孕暇，將元素插入到另一個(gè)容器中仑撞。copy(bar.begin(), bar.end(), inserter(foo, it)); 將bar的元素全部插入到foo容器的it位置，并不覆蓋foo原有的元素妖滔。如果是copy(bar.begin(), bar.end(), foo.begin());這樣寫會(huì)覆蓋foo中原有的元素隧哮。

X適配器

輸出ostream_iterator內(nèi)部定義了拷貝賦值函數(shù)，將value賦值給標(biāo)準(zhǔn)輸出座舍。所以copy會(huì)調(diào)用ostream_iterator的拷貝賦值沮翔，輸出各個(gè)元素。

std::ostream_iterator out_it(std::cout, ",");

copy(vec.begin(), vec.end(), out_it);

輸入istream_iterator重載operator++作為輸入數(shù)據(jù)曲秉。

istream_iterator iit(cin); 在構(gòu)造的時(shí)其內(nèi)部就會(huì)調(diào)用operator++采蚀。這里會(huì)等待輸入數(shù)據(jù)。