• 泛型算法：經(jīng)典算法的公共接口。
• 泛型的含義：用于不同類型的元素和多種容器類型，以及其他類型的序列。

初識(shí)

• 例子：
  泛型算法不直接操作容器，而是遍歷由兩個(gè)迭代器指定的一個(gè)元素范圍，如find:

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

可以看到，find內(nèi)部使用迭代器進(jìn)行，這使得迭代器令算法不依賴與容器。
但是算法依賴于元素類型的操作：比如find要求元素類型支持<云算符。
并且多數(shù)算法支持我們自定義的操作代替默認(rèn)的比較運(yùn)算符。

• 結(jié)論：算法運(yùn)行于迭代器上，執(zhí)行迭代器的操作，而不會(huì)執(zhí)行容器的操作；算法永遠(yuǎn)不會(huì)改變低層容器的大小。

只讀算法：只會(huì)讀取范圍內(nèi)的元素，不會(huì)改變?cè)兀?code>find、count。

• numeric里面的accumulate,第三個(gè)參數(shù)的類型決定了函數(shù)使用哪個(gè)加法運(yùn)算符和函數(shù)值返回類型：

對(duì)vec中的元素求和，和的初值是0 （第三個(gè)參數(shù)）
int sum = accumulate(vec.cbegin(),vec.cend(), 0);

編程假定：元素類型加到和的類型上的操作必須是可行的。

連接所有的string元素。
string sum = accumulate(v.cbegin(), v.cend(), string(""));

錯(cuò)誤的，因?yàn)閏onst char*上沒(méi)有定義+運(yùn)算符
string sum = accumulate(v.cbegin(), v.cend(), "");

• equal比較兩個(gè)序列是否保存了一樣的值。

roster2中的元素?cái)?shù)目應(yīng)該至少與roster1一樣多
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

上面的equal接受一個(gè)單一迭代器表示第二個(gè)序列，一般這樣的算法都假定了第二個(gè)序列至少與第一個(gè)序列一樣長(zhǎng)。

寫(xiě)容器算法：這類算法要求確保序列大小至少不小于我們要求算法寫(xiě)入的元素?cái)?shù)目。

• fill算法：接受一對(duì)迭代器、一個(gè)值：

將每個(gè)元素重置為0
fill(vec.begin(), vec.end(), 0); 

將容器的子序列設(shè)置為10
fill(vec.begin(), vec.begin() + vec.size() / 2, 10);

• fill_n 接受一個(gè)單迭代器、一個(gè)計(jì)數(shù)值、和一個(gè)值：

vector<int> vec;

將所有元素重置為0
fill_n(vec.begin(), vec.size(), 0); 

fill_n(dest, n, val);

上面的fill_n假設(shè)了dest開(kāi)始的序列至少有包含了n個(gè)元素，可能犯的錯(cuò)誤：

vector<int> vec; // 空容器
fill_n(vec, 10, 0);  // 錯(cuò)誤， 該10個(gè)位置都不存在

• 插入迭代器 back_inserter：一種可以向容器添加元素的迭代器。定義在頭文件iterator中。接受一個(gè)指向容器的引用， 返回一個(gè)與該容器綁定的插入迭代器：

vector<int> vec;
auto it = back_iterator(vec);
* it = 42; // vec中現(xiàn)在多了一個(gè)元素42

可以使用back_iterator作為算法的目的位置使用：

vector<int> vec; 
fill_n(back_inserter(vec), 10, 0); //現(xiàn)在添加了10個(gè)元素到vec

• copy算法：要求目的序列至少要與輸入序列一樣多的元素：

int a1[] = {0,1,2};
int a2[ sizeof(a1) / sizeof(*a1)]; // 與a1大小一樣
auto ret = copy(begin(a1), end(a1), a2);  //把a(bǔ)1的內(nèi)容復(fù)制給a2；

copy返回目的的位置迭代器，即ret恰好指向a2的尾元素之后的位置。

• replace算法：接受一對(duì)迭代器表示輸入序列，一個(gè)要搜索的值、一個(gè)新值。把搜索的值變?yōu)樾轮担?/li>

把所有0元素變?yōu)?2
replace(ilst.begin(), ilst.end(), 0, 42); 

• replace_copy算法：接受額外第三個(gè)迭代器參數(shù)，指出調(diào)整序列的保存位置：

使得原來(lái)的ilst序列不變，ivec保存了replace操作的序列
replace_copy(ilst.cbegin(), ilst.end(), back_inserter(ivec), 0, 42);

重排容器元素的算法

• unique算法：使得不重復(fù)的元素出現(xiàn)在輸入序列的開(kāi)始部分，但是并非刪除了重復(fù)的元素，只是覆蓋了相鄰的重復(fù)元素。unique返回的迭代器指向最后一個(gè)不重復(fù)元素之后的位置。

一個(gè)消除重復(fù)單詞的例子：

void elimDups(vector<string> &words)
{
  sort(words.begin(), words.end());
  // unique重拍輸入范圍,使得每一個(gè)單詞只出現(xiàn)一次
  auto end_unique = unique(words.begin(), words.end());
  words.erase(end_unique, words.end());
}
int main() {
  vector<string> words = {"the", "quick", "red", "fox", "jumps",
  "over", "the", "slow","red","turtle"};
  elimDups(words);
  for (auto i: words)
    cout << i << " ";
}

fox jumps over quick red slow the turtle

定制操作

比如sort算法默認(rèn)使用<運(yùn)算符，但我們希望排序順序與<所定義的順序不同，或者保存的序列元素未定義<運(yùn)算符，因此都需要重載sort的默認(rèn)行為，為此需要定制我們自己的操作。

傳遞函數(shù)給算法

• 謂詞（predicate）參數(shù)：謂詞是一個(gè)可調(diào)用的表達(dá)式，其返回結(jié)果是一個(gè)能用做條件的值。標(biāo)準(zhǔn)庫(kù)算法使用的兩類謂詞：
  1.一元謂詞：只接受單一參數(shù)。
  2. 二元謂詞：有兩個(gè)參數(shù)。

接受謂詞參數(shù)的算法對(duì)輸入序列中的元素調(diào)用謂詞。因此，元素類型必須能夠轉(zhuǎn)換為謂詞的參數(shù)類型。

• stable_sort：保持等長(zhǎng)元素間的字典序。
  一個(gè)新sort例子：

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

elimDups(words);

這使得短的單詞排在長(zhǎng)的單詞的前面；
stable_sort(words.begin(), words.end(), isShorter);
  for (const auto &s: words) //無(wú)須拷貝字符串
    cout << s << " ";


fox red the over slow jumps quick turtle

lambda表達(dá)式

• motivation：希望進(jìn)行的操作需要更多的參數(shù)怎么辦？
• lambda介紹：我們可以向一個(gè)算法傳遞任何類別的可調(diào)用對(duì)象（callable object）。
  對(duì)于一個(gè)對(duì)象或一個(gè)表達(dá)式，可以對(duì)其使用調(diào)用運(yùn)算符（圓括號(hào)()），則稱它為可調(diào)用的。
  比如e是可調(diào)用表達(dá)式，可以使用e(args).
• 幾種可調(diào)用對(duì)象：函數(shù)、函數(shù)指針、重載了函數(shù)調(diào)用運(yùn)算符的類、lambda表達(dá)式。

一個(gè)lambda表達(dá)式可理解為一個(gè)未命名的內(nèi)聯(lián)函數(shù)，其形式如下：

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

capture list是一個(gè)lambda所在函數(shù)中定義的局部變量的列表（通常為空），其他參數(shù)與普通函數(shù)類似。
與其他函數(shù)的不同，lambda必須使用尾置返回來(lái)指定返回類型。

• 復(fù)習(xí)尾置返回：尾置返回類型跟在形參列表后面用一個(gè)->符號(hào)開(kāi)頭，例子：

func接受一個(gè)int類型的實(shí)參，返回一個(gè)指針，該指針指向含有是個(gè)整數(shù)的數(shù)組。
auto func(int i) -> int(*)[10];
可以看到，函數(shù)的返回類型放在了形式參數(shù)列表的后面。

lambda表達(dá)式必須永遠(yuǎn)包含捕獲列表和函數(shù)體：

auto f= [] {return 42;};

調(diào)用lambda表達(dá)式：
cout << f() << endl;

注：如果lambda函數(shù)體包含任何單一return語(yǔ)句之外的內(nèi)容，且未指定返回類型，則返回void。

• 向lambda傳遞參數(shù)：不能有默認(rèn)參數(shù)，因此調(diào)用lambda的實(shí)參數(shù)目永遠(yuǎn)與形參數(shù)目相等。
  與isShorter同樣功能的lambda表達(dá)式：

 [](const string &a, const string &b){return a.size() < b.size();}

• 使用捕獲列表：
  Note：一個(gè)lambda只有在其捕獲列表中捕獲一個(gè)它所在函數(shù)中的局部變量時(shí)，才能在函數(shù)體中使用該變量。

lambda表達(dá)式通過(guò)將局部變量包含在捕獲列表中來(lái)指出將會(huì)使用這些變量。

一個(gè)例子，上述的sort單詞，要求出大于等于一個(gè)給定長(zhǎng)度的單詞有多少，修改輸出，打印這些單詞；

定義一個(gè)給定長(zhǎng)度`sz`，然后把`sz`加入捕獲列表,在函數(shù)體內(nèi)使用。
[sz](const string &a){return a.size() >= sz;};

錯(cuò)誤，sz未捕獲
[](const string &a){return a.size() >= sz;};

• find_if算法：接受一對(duì)迭代器，第三個(gè)參數(shù)是一個(gè)謂詞。對(duì)輸入序列中的每個(gè)元素調(diào)用這個(gè)謂詞。返回第一個(gè)使得謂詞返回非0值的元素，不存在這樣的元素則返回尾迭代器。

• for_each算法：接受一個(gè)可調(diào)用對(duì)象，并對(duì)輸入序列中每個(gè)元素調(diào)用此對(duì)象。

for_each(wc, words.end(), [](const string &s){cout << s << " ";});

上面的lambda空捕獲列表,但是函數(shù)體使用了s、cout，因?yàn)椋?br> Note: 捕獲列表只用于局部非static變量，lambda可以之間直接使用局部static變量還有它所在函數(shù)之外聲明的名字。

代碼：

string make_plural(size_t ctr, const string &word, const string &ending)
{
  return (ctr > 1) ? word + ending: word;
}

  //vector<string> words = {"the", "quick", "red", "fox", "jumps","over", "the", "slow", "red", "turtle"};

void biggies(vector<string> &words, vector<string>::size_type sz) {
  elimDups(words);
  stable_sort(words.begin(), words.end(), 
  [](const string &a, const string &b){return a.size() < b.size();});
  for (const auto &s: words) //無(wú)須拷貝字符串
    cout << s << " ";
  cout << endl;
  auto wc = find_if(words.begin(),words.end(),
 
 //sz不在函數(shù)體內(nèi)
  [sz](const string &a){return a.size() >= sz;});
  // wc指向words中第一個(gè)string長(zhǎng)度大于等于5的位置，用end減去便是剩下都大于等于5的string數(shù)目
  auto count = words.end() - wc;
  cout << count << " " << make_plural(count, "word", "s")
    << " of length " << sz << " or longer " << endl;
  for_each(wc, words.end(), [](const string &s){cout << s << " ";});
}

fox red the over slow jumps quick turtle
3 words of length 5 or longer
jumps quick turtle

• lambda的捕獲和返回

參數(shù)綁定

再探迭代器

• 插入迭代器
  插入器是一種迭代器適配器：接受一個(gè)容器，生成一個(gè)迭代器。

• 插入迭代器操作：

  • it=t：在it指定的當(dāng)前位置插入值t.
  • *it, ++it, it++：不會(huì)對(duì)it做任何事情，都返回it.

• 插入迭代器有三種：

  • back_inserter：創(chuàng)建一個(gè)使用push_back的迭代器。
  • front_inserter: 創(chuàng)建一個(gè)使用push_front的迭代器。
  • inserter: 創(chuàng)建一個(gè)使用inserter的迭代器，接受第二個(gè)參數(shù)，該參數(shù)指定一個(gè)給定容器的迭代器。元素被插入到給定迭代器所表示的元素之前。（inserter(c, iter)）

1. inserter的例子：設(shè)it是由inserter生成的迭代器，則：

*it = val;

等價(jià)于：
it = c.insert(it, val); //it指向新加入的元素
++it; // 遞增it使它指向原來(lái)的元素 

2. front_inserter的例子：

list<int> lst = {1, 2, 3, 4, 5};
list<int> lst2, lst3; 

// 拷貝完成后， lst2包含4，3，2，1
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
// lst3包含1，2，3，4
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

• 流迭代器（iostream迭代器）

• 反向迭代器

• 移動(dòng)迭代器

泛型算法結(jié)構(gòu)

特定容器算法