[C++ Primer Note9] 泛型演算法和lambda

摘要： 標準庫容器定義的操作集合驚人的小。標準庫並未給每個容器新增大量功能，而是提供了一組演算法，這些演算法中的大多數都獨立於任何特定的容器。這些演算法是通用的（generic ，或稱泛型的）：它們可用於不同型別的容器和不同型別的元素。它們實現了一些經典演算法的公共介面，比如排序和搜...

標準庫容器定義的操作集合驚人的小。標準庫並未給每個容器新增大量功能，而是提供了一組演算法，這些演算法中的大多數都獨立於任何特定的容器。這些演算法是通用的（generic ，或稱泛型的）：它們可用於不同型別的容器和不同型別的元素。它們實現了一些經典演算法的公共介面，比如排序和搜尋。

1. 大多數演算法都定義在標頭檔案algorithm 中，標準庫還在標頭檔案numeric 定義了一組數值泛型演算法。一般情況下，這些演算法並不直接操作容器，而是遍歷 由兩個迭代器指定的一個元素範圍來進行操作。例如，我們有一個int的vector，希望知道vector中是否包含一個特定值，我們可以呼叫標準庫演算法find ：

int val=42;
auto result=find(vec.cbegin(),vec.cend(),val);

該函式返回指向第一個等於給定值的元素的迭代器 ，否則返回第二個引數表示搜尋失敗。

由於find 操作的是迭代器，因此我們可以用同樣的find函式在任何容器中查詢值。

同時，由於指標就像內建陣列上的迭代器 一樣，我們可以用find在陣列中查詢值。

int arr[]={1,2,3,4,5,6,7,8,9,10};
auto result=find(begin(arr),end(arr),10);

2. 迭代器令演算法不依賴於容器，但多數演算法都使用了一個或多個元素型別上的操作，例如在find函式中使用了元素型別的== 運算子完成了比較。不過，大多數演算法提供了一種演算法，允許我們使用自定義的操作代替預設的運算子。
3. 除了少數例外，標準庫演算法都對一個範圍內的元素進行操作。我們將此元素範圍稱為“輸入範圍 ”。接受輸入範圍的演算法總是使用前兩個引數來表示此範圍，兩個引數分別是指向第一個元素和尾元素之後位置的迭代器。雖然大多數演算法遍歷輸入範圍的方式相似，但它們使用範圍中元素的方式不同。理解演算法的最基本方法就是了解它們是否讀取元素，改變元素或是重排元素順序 。
4. count 演算法(返回給定值在序列中出現的次數）

vector<int> v1={1,2,3,4,1};
int cnt=count(v1.cbegin(),v1.cend(),1);

5. accumulate 演算法（求和）,第三個引數是和的初值

vector<int> v1={1,2,3};
cout<<count(v1.cbegin(),v1.cend(),2}<<endl; //結果為8

6. equal 演算法,比較兩個序列是否相等。第三個引數是第二個序列的首元素迭代器。第二個序列長度要大於等於第一個
7. fill 演算法，給序列中元素賦值
8. fill_n 演算法，接受一個單迭代器，一個計數值和一個值，將給定值賦予迭代器指向的元素開始的指定個元素。

vector<int> vec(20);
fill_n(vec.begin(),10,10);

一定不能向空vector寫入數值

9. 向目的位置迭代器寫入資料的演算法假定目的位置足夠大。
10. 泛型演算法本身不會執行 容器的操作，它們只會運行於迭代器之上，執行迭代器的操作：演算法永遠不會改變底層容器的大小
11. 一種保證演算法有足夠元素空間容納輸出資料的方法是使用插入迭代器（insert iterator） 。插入迭代器是一種向容器新增元素 的迭代器。
12. back_inserter（定義在iterator） 接受一個指向容器的引用，返回一個與容器繫結的插入迭代器 。當我們通過此迭代器賦值時，賦值運算子會呼叫push_back新增元素。

vector<int> vec; //空向量
auto it=back_inserter(vec);
*it=42;//vec現在有了一個元素

我們常常使用back_inserter來建立一個迭代器並作為演算法的目的位置 來使用：

vector<int> vec;
fill_n(back_inserter(vec),10,0);//新增10個元素到vec

13. copy演算法 能夠實現容器及內建陣列的拷貝 ：

int a1[]={1,2,3,4,5};
int a2[sizeof(a1)/sizeof(*a1)];
auto ret=copy(begin(a1),end(a1),a2);

copy返回的是目的位置迭代器（遞增後）的值，此處指向a2的尾後元素 。

14. 多個演算法都提供所謂的拷貝 版本，這些版本計算新元素的值，但不會讓它們印象原輸入序列，而是新建一個序列儲存這些結果。

replace(ilst.begin(),ilst.end(),0,42);//將0替換為42
replace_copy(ilst.begin,ilst.end(),back_inserter(vec),0,42); //按需要增長目標序列

15. 某些演算法會重排容器中元素的順序，比如sort ，它是利用元素型別的< 運算子來實現排序的。
16. 消除重複單詞 ：

sort(words.begin(),words.end());
//unique返回指向不重複區域之後一個位置的迭代器
auto end_unique = unique(words.begin(),words.end());
words.erase(end_unique,words.end());

此處的unique 並不能通過迭代器來真正實現刪除元素，還是要依賴於容器操作。

17. 很多演算法都會比較輸入序列的元素，預設情況下，這些演算法使用元素型別的<或==運算子完成比較。標準庫還為這些演算法定義了額外的版本，允許我們提供自定義的操作來代替預設運算子。
18. 比如sort 演算法，我們希望優先按照單詞長度排序，長度相等再按字典序排列。我們將使用sort的第二個版本，它接受第三個引數，此引數是一個謂詞（predicate）
19. 謂詞 是一個可呼叫的表示式，其返回結果是一個能用作條件的值。標準庫演算法所使用的謂詞分為兩類：一元謂詞 和二元謂詞 ，接受謂詞引數的演算法對輸入序列中的元素呼叫謂詞。因此，元素型別必須能轉換成謂詞的引數型別。

bool isShorter(const string &s1,const string &s2){
return s1.size()<s2.size();
}
sort(words.begin(),words.end(),isShorter);

20. 根據演算法接受一元謂詞還是二元謂詞，我們傳遞給演算法的謂詞必須嚴格接受一個或兩個引數。但是，有時我們希望進行的操作需要更多引數 ，超出了演算法對謂詞的限制。
21. 我們可以向一個演算法傳遞任何類別的可呼叫物件 ，目前為止，我們使用過的僅有的兩種可呼叫物件是函式 和函式指標 。還有兩種可呼叫物件：過載了函式呼叫運算子的類，以及lambda表示式
22. 一個lambda表示式表示一個可呼叫的程式碼單元。我們可以將其理解為一個未命名的行內函數 。與任何函式型別，一個lambda具有一個返回型別，一個引數列表和一個函式體。但與函式不同，lambda可能定義在函式內部 。一個lambda表示式具有如下形式：

[capture list] (parameter list) -> return type {function body}

其中，capture list（捕獲列表）是一個lambda所在函式 中定義的區域性變數 的列表（通常為空）；return type，paramter list，function body則與普通函式 一樣。但是，lambda必須使用尾置返回 來指定返回型別。

我們可以忽略引數列表和返回型別，但必須永遠包含捕獲列表和函式體 。

auto f=[]{return 42};

我們定義了一個可呼叫物件 f，它不接受引數，返回42。

如果忽略返回型別，lambda根據函式體程式碼推斷 出返回型別

我們可以通過lambda來改寫上文提到的isShorter函式：

sort(words.begin(),words.end(),
[](const string &s1,const string &s2)
{return s1.size()<s2.size();});

23.示例：列印長度大於等於某個值的字串

void printBig(vector<string> vec,string::size_type sz){
sort(vec.begin(),vec.end(),[](const string &s1,const string &s2)
{return s1.size()<s2.size();});
//find_if接受一個謂詞，篩選出第一個返回非0的迭代器
auto it=find_if(vec.begin(),vec.end(),[sz](const string& s)
{return s.size()>=sz;});
while(it!=vec.end()){
cout<<*it++<<" ";
}
cout<<endl;
}

此處我們使用捕獲列表捕獲了局部變數sz ，使得演算法不再受制於謂詞的引數個數。

24. for_each 演算法，接受一個可呼叫物件，並對輸入序列每個元素呼叫此物件。我們可以利用它改寫上述程式碼過程：

for_each(it,vec.end(),[](const string &s){cout<<s<<endl;});

25. 當定義一個lambda時，編譯器生成一個與lambda對應的新的（未命名）類型別 。目前，可以這樣理解，當向一個函式傳遞一個lambda時，同時定義了一個新型別和該型別的一個物件 。預設情況下，從lambda生成的類都包含一個對應該lamdda所捕獲的變數的資料成員 ，類似任何普通類的資料成員，lambda的資料成員也在lambda物件建立時被初始化。
26. 變數的捕獲可以是值或引用。與傳值引數類似，採用值捕獲的前提是物件可以拷貝 。與引數不同，捕獲的變數的值是在lambda建立 時拷貝，而不是呼叫時拷貝。因此隨後對被捕獲變數的修改不會影響到lambda內對應的值 。
27. 引用捕獲 ：

void fun2(){
size_t v1=42;
auto f2=[&v1]{return v1;};
 }

當採用引用捕獲時，同樣要保證在lambda執行時變數存在 。

28. 我們也可以從一個函式返回lambda
29. 我們還可以隱式捕獲 ，在捕獲列表中寫一個& 或= ，告訴編譯器採用引用捕獲還是值捕獲方式。具體規則此處不贅述。
30. 當一個lambda體包含return以外的任何語句，則編譯器假定此lambda返回void，我們需要顯式指明 。
31. 除了使用lambda 以外，我們還可以使用定義在functional 的bind 函式，這個函式可以實現對可呼叫物件引數的動態繫結 ，利用它同樣可以實現謂詞的引數擴充套件，此處也不贅述，該函式的設計理念已經隱隱進入函數語言程式設計的範疇。
32. 除了為每個容器定義的迭代器之外，標準庫在標頭檔案iterator 中還定義了額外集中迭代器：

• 插入迭代器 ：這些迭代器被繫結到一個容器上，可用來向容器插入元素
• 流迭代器 ：被繫結到輸入或輸出流，可用來遍歷關聯IO流
• 反向迭代器 ：向後而不是向前移動
• 移動迭代器 ：這些專用的迭代器不是拷貝其中元素，而是移動它們

33. 插入迭代器是一種迭代器介面卡 ，它接受一個容器，生成一個迭代器，能實現向給定容器新增元素。當我們通過一個插入迭代器進行賦值時，該迭代器呼叫容器操作來向給定容器的指定位置插入一個元素。

    插入器有三種類型，差異在於元素插入的位置 ：

• back_inserter ：總是插入到最後一個元素之後
• front_inserter :總是插入到第一個元素之前，僅用於容器支援push_front
• inserter：接受第二個引數，這個引數必須是一個迭代器，元素將被插入到給定迭代器所表示的元素之前，指向不變

34. 雖然iostream型別不是容器，但標準庫定義了可用於這些IO型別物件的迭代器。istream_iterator 讀取輸入流，ostream_iterator 向一個輸出流寫資料。這些迭代器將它們對應的流當做一個特定型別的元素序列 來處理，我們可以用泛型演算法從流物件讀取資料以及向其寫入資料。
35. 當建立一個流迭代器時，必須指定迭代器將要讀寫的物件型別。一個istream_iterator 使用>> 來讀取流。當建立一個istream_iterator，我們將其繫結到一個流，我們還可以預設初始化流迭代器，這樣就建立了一個可以作為尾後值使用的迭代器：

istream_iterator<int> int_it(cin);
istream_iterator<int> int_eof;
ifstream in("filename");
istream_iterator<string> str_it(in);

下面是一個用istream_iterator從標準輸入讀取資料，存入vector的例子：

vector<int> vec;
istream_iterator<int> it(cin);
istream_iterator<int> eof;
while(it!=eof){
vec.push_back(*it++);
}

或者

istream_iterator<int> it(cin);
istream_iterator<int> eof;
vector<int> vec(it,eof);

36. 當我們將一個istream_iterator繫結到一個流時，標準庫並不保證 迭代器立即從流讀取資料。標準庫中的實現保證的是在我們第一次解引用之前，讀取操作已經完成了。
37. 我們可以對任何具有輸出操作符<< 的型別定義ostream_iterator。我們可以提供第二引數，它是一個字串，在輸出每個元素後都會列印此字串。

vector<int> vec={1,2,3};
ostream_iterator<int> out(cout," ");
for(auto num:vec){
*out++=num;
}

或者

vector<int> vec={1,2,3};
ostream_iterator<int> out(cout," ");
copy(vec.begin(),vec.end(),out);

38. 我們可以為任何定義了輸入運算子的型別建立istream_iterator和ostream_iterator物件
39. 任何演算法的最基本的特徵是它要求其迭代器提供哪些操作 ，某些演算法，比如find，只要求通過迭代器訪問元素，遞增迭代器以及比較迭代器是否相等這些能力。演算法所要求的迭代器操作可以分為5個迭代器類別 ，每個演算法都會對它的每個迭代器引數指名需要提供哪些迭代器：

• 輸入迭代器：只讀不寫，只能遞增
• 輸出迭代器：只寫不讀，只能遞增
• 前向迭代器：可讀寫；多遍掃描，只能遞增
• 雙向迭代器：可讀寫；多遍掃描，可遞增遞減
• 隨機訪問迭代器：可讀寫；多遍掃描，支援全部迭代器運算

40. 一些演算法使用過載形式傳遞一個謂詞 ，比如sort
41. 接受一個元素值的演算法通常有另一個不同名的版本 ，該版本接受一個謂詞代替元素值，接受謂詞的演算法都有附加的_if 字尾，比如find和find_if
42. 區分拷貝元素的版本和不拷貝的版本 ，預設情況下，重排元素的演算法將重排後的元素寫回給定的輸入序列中。寫到額外目的空間的演算法都在名字後面附加一個_copy 。
43. 與其他容器不同，連結串列型別list 和forward_list 定義了幾個成員函式 形式的演算法，特別是它們定義了獨有的sort，merge，remove，reverse和unique。通用版本的sort要求隨機訪問迭代器 ，而它們分別提供雙向迭代器和前向迭代器。對於list和forward_list，應該優先使用成員函式版本 的演算法。