泛型算法
概述
- 使用標(biāo)準(zhǔn)庫(kù)算法find查找vector中的特定元素
int val = 42;
auto result = find(vec.cbegin(),vec.cend(),val);
cout << (result == vec.cend() ? "not present" : "presend") << endl;
- 傳遞給find的前兩個(gè)參數(shù)是表示元素范圍的迭代器效拭，第三個(gè)參數(shù)是要尋找比對(duì)的值输吏，如果范圍中無(wú)匹配元素犬耻，則find返回第二個(gè)參數(shù)表示失敗
- find操作的是迭代器煎谍，所以可以用find在任何容器中查找值
- 可以用find在數(shù)組中擦護(hù)照值
int ia[] = {1,1,5,9,56,847,56};
int val = 83;
int * result = find(begin(ia),end(ia),val)
- 迭代器令算法不依賴于容器坊萝，但算法依賴于元素類(lèi)型的操作
- 算法用于不會(huì)執(zhí)行容器的操作
- [x] 泛型算法本身不會(huì)執(zhí)行容器的操作苛预，它們只會(huì)運(yùn)行在迭代器之上句狼，執(zhí)行迭代器的操作
- [x] 算法永遠(yuǎn)不會(huì)改變底層容器的大小，算法可能改變?nèi)萜髦斜４娴脑氐闹等饶常部赡茉谌萜鲀?nèi)移動(dòng)元素腻菇，但他永遠(yuǎn)不會(huì)直接添加或刪除元素
- [x] 標(biāo)準(zhǔn)庫(kù)定義了一類(lèi)特殊的迭代器，成為`插入器`昔馋，當(dāng)給這類(lèi)迭代器賦值時(shí)筹吐，它們會(huì)在底層的容器上執(zhí)行插入操作，因此秘遏，當(dāng)一個(gè)算法操作這樣的迭代器時(shí)丘薛，迭代器可以完成向容器添加元素的效果，但算法自身永遠(yuǎn)不會(huì)做這樣的操作
泛型算法
- 除了少數(shù)例外邦危，標(biāo)準(zhǔn)庫(kù)算法都對(duì)一個(gè)范圍內(nèi)的元素進(jìn)行操作
- 理解算法的最基本的方法就是了解它們是否讀取元素洋侨、改變?cè)鼗蛘咧嘏旁仨樞?/li>
只讀算法
- find、accumulate以及equal函數(shù)接受三個(gè)參數(shù)
- accumulate定義在頭文件'numeric'中倦蚪，它的前兩個(gè)參數(shù)指出了需要求和的元素的范圍希坚，第三個(gè)參數(shù)是和的初始值
int sum = accumulate(vec.cbegin(),vec.cend(),0); //對(duì)vec中的元素求和，和的初始值是0
string sum = accumulate(v.cbegin(),v.cend(),"");
- accumulate的第三個(gè)參數(shù)的類(lèi)型決定了函數(shù)中使用哪個(gè)加法運(yùn)算符以及返回值的類(lèi)型
- 對(duì)于只讀取而不改變?cè)氐乃惴昵遥詈檬褂胏begin()和cend()
- equal是操作兩個(gè)序列的算法
- [x] equal用于確定兩個(gè)序列是否保存相同的值裁僧，它將第一個(gè)序列中的每個(gè)元素與第二序列中的對(duì)應(yīng)元素進(jìn)行比較，如果所有對(duì)應(yīng)元素都相等滩报，則返回true锅知，否則返回false
- [x] 此算法接受三個(gè)迭代器，前兩個(gè)表示第一個(gè)序列中的元素范圍脓钾，第三個(gè)表示第二個(gè)序列的首元素
equal(roster1.cbegin(),roster1.cend(),roster2.cbegin()); //roster2中的元素?cái)?shù)目至少應(yīng)該與roster1一樣多
- equal基于一個(gè)非常重要的假設(shè)售睹，它假定第二個(gè)序列至少與第一個(gè)序列一樣長(zhǎng)
- 那些只接受一個(gè)單一迭代器來(lái)表示第二個(gè)序列的算法，都假定第二個(gè)序列至少與第一個(gè)序列一樣長(zhǎng)
寫(xiě)容器元素的算法
- 算法fill接受一對(duì)迭代器表示一個(gè)范圍可训，還接受一個(gè)值作為第三個(gè)參數(shù)昌妹，fill將給定的這個(gè)值賦予輸入序列中的每個(gè)元素
fill(vec.begin(),vec.end(),0); //將每個(gè)元素重置為0
- 算法不檢查寫(xiě)操作
- 向目的位置迭代器寫(xiě)入數(shù)據(jù)的算法假定目的位置足夠大捶枢，能容納要寫(xiě)入的元素
- copy算法
- [x] 此算法接受三個(gè)迭代器，前兩個(gè)表示一個(gè)輸入范圍飞崖，第三個(gè)表示目的序列的起始位置
int a1[] = {0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1)/sizeof(*a1)]; //a1和a2大小一樣
auto ret = copy(begin(a1),end(a1),a2); //把a(bǔ)1的內(nèi)容拷貝給a2
- [x] 讀入一個(gè)序列烂叔，并將其中所有等于給定值的元素都改為另一個(gè)值
- [x] 此算法接受四個(gè)參數(shù):前兩個(gè)是迭代器，表示輸入序列固歪，后兩個(gè)一個(gè)是要搜索的值蒜鸡，另一個(gè)是新值
- [x] 它將所有等于第一個(gè)值的元素替代為第二個(gè)值
replace(list.begin(),list.end(),0,42);
- 如果需要真正的刪除無(wú)用元素，必須使用容器操作牢裳，例如erase
定制操作
lambda表達(dá)式
- 一個(gè)lambda表達(dá)式表示一個(gè)可調(diào)用的代碼單元逢防，我們可以將其裂解為一個(gè)未命名的內(nèi)聯(lián)函數(shù)
[capture](parameter list)->return type {function body}
- lambda表達(dá)式必須使用尾置返回
- lambda表達(dá)式可以忽略參數(shù)列表(parameter list)和返回類(lèi)型(return type)，但必須永遠(yuǎn)包含捕獲列表(capture)和函數(shù)體(function body)
- 如果lambda的函數(shù)體包含任何單一return語(yǔ)句之外的內(nèi)容蒲讯，且未指定返回類(lèi)型忘朝，則返回void
- 一共lambda只有在其捕獲列表中捕獲一共它所在函數(shù)中的局部變量，才能在函數(shù)體中使用該變量
- 捕獲列表只用于局部非static變量判帮，lambda可以直接使用局部static變量和它所在函數(shù)之外聲明的名字
- 盡量保持lambda的變量捕獲簡(jiǎn)單化
迭代器
- 除了為每個(gè)容器定義的迭代器之外局嘁，標(biāo)準(zhǔn)庫(kù)在頭文件iterator中還定義了額外幾種迭代器
- [x] **插入迭代器**：這些迭代器被綁定到一個(gè)容器上，可以用來(lái)向容器插入元素
- **back_inserter**
- **front_inserter**
- inserter
- 只有在容器支持push_front的情況下晦墙，我們才可以使用front_inserter,類(lèi)似悦昵，只有在容器支持push_back的情況下，才能使用back_inserter
- [x] **流迭代器**：這些迭代器被綁定到輸入或輸出流上偎痛，可用來(lái)遍歷所關(guān)聯(lián)的IO流
- **istream_iterator**讀取輸入流
- **ostream_iterator**向一個(gè)輸出流寫(xiě)數(shù)據(jù)
- [x] **反向迭代器**：這些迭代器向后而不是向前移動(dòng)(在容器中從尾元素向首元素反向移動(dòng))旱捧，除了forward_list之外的標(biāo)準(zhǔn)庫(kù)容器都有反向迭代器
- 對(duì)于反向迭代器独郎，遞增或遞減操作的含義會(huì)反過(guò)來(lái)
- **rbegin\rend\crbegin\crend**
- [x] **移動(dòng)迭代器**：這些專(zhuān)用的迭代器不是拷貝其中的元素踩麦，而是移動(dòng)它們
泛型算法結(jié)構(gòu)
算法形參模式
alg(beg,end,other args);
alg(beg,end,dest,other args);
alg(beg,end,beg2,other args);
alg(beg,end,beg2,end2,other args);
- 接受單個(gè)目標(biāo)迭代器的算法家棟目標(biāo)空間足夠容納寫(xiě)入的數(shù)據(jù)
- 接受第二個(gè)輸入序列的算法假定從beg2開(kāi)始的序列與beg和end所表示的范圍至少一樣大
特定容器算法(鏈表類(lèi)型算法)
- 對(duì)于list和forward_list，應(yīng)該優(yōu)先使用成員函數(shù)版本的算法而不是通用算法
- 多數(shù)鏈表特有的算法都與其通用版本相似氓癌，但不完全相同谓谦，鏈表特有版本與通用版本間的一個(gè)至關(guān)重要的區(qū)別是鏈表版本會(huì)改變底層的容器
