順序容器中只定義了添加刪除訪問等簡單操作逆航，用戶更多的需求，只能通過泛型算法實(shí)現(xiàn)帅刊。此類算法稱之為"泛型"是因?yàn)樗鼈兛梢杂糜诓煌愋偷脑睾投喾N容器類型纸泡。

泛型算法分類

大多數(shù)泛型算法都定義在algorithm中，標(biāo)準(zhǔn)庫還在numeric中定義了一組數(shù)值泛型算法赖瞒。常見的泛型算法可以分為：只讀算法女揭、寫容器算法、重排容器算法栏饮、定制操作等四個(gè)類別吧兔。下面將分別進(jìn)行簡單介紹。

1 只讀算法

以下大部分算法都有自己的重載版本袍嬉，感興趣的同學(xué)可以查找相關(guān)資料境蔼，進(jìn)行深入學(xué)習(xí)。下面用代碼的方式對(duì)常見只讀算法進(jìn)行介紹伺通。

1.1 find查找

//查找目標(biāo)元素在容器中的位置
void find_element_pos(vector<int> & v, int val){
    cout << find(v.begin(), v.end(), val) - v.begin() << endl;
}

1.2 accumulate求和

void accumulate_display(){
    vector<int> vi = { 1, 2, 3, 4 };
    vector<string>vs = { "accu", "disp" };
    //整數(shù)累加初值設(shè)為0
    cout << accumulate(vi.begin(), vi.end(), 0) << endl;
    //字符累加初值設(shè)為"";
    cout << accumulate(vs.begin(), vs.end(), string("")) << endl;
}

1.3 count計(jì)算目標(biāo)元素的個(gè)數(shù)

void count_element(vector<int> & v, int val){
    cout << count(v.begin(), v.end(), val) << endl;
}

1.4 equal判斷兩容器是否相等

void equal_display(){
    list <char*>a = { "a", "b" };
    vector<const char *> b = { "a", "b" };
    cout << equal(a.begin(), a.end(), b.begin())<<endl;
}
//兩點(diǎn)說明：
//1. equal假設(shè)箍土，第二序列b至少與a一樣長，程序員有責(zé)任對(duì)此作出保證罐监。
//2. 兩序列中的元素類型不必完全相同吴藻，只要能夠使用==進(jìn)行比較即可。

2 寫容器算法

當(dāng)我們將新值賦予序列中元素時(shí)弓柱，必須保證序列原大小足夠大沟堡。算法保持泛型，不會(huì)進(jìn)行具體的容器操作（容器接口可能不同）矢空，因此算法自身不能改變?nèi)萜鞯拇笮『铰蕖３Ｒ娪梅ㄈ缦拢?/p>

2.1 填充fill/fill_n

void fill_container(){
    //fill_n/fill無法改變?nèi)萜鞔笮?    vector<int> vi;
    fill_n(vi.begin(), 10, 0);//錯(cuò)誤，試圖在空的vi中填入10個(gè)元素
    vi.push_back(1);
    vi.push_back(2);
    fill_n(vi.begin(), vi.size(), 0);//正確屁药，將所有元素置為0
    fill(vi.begin(), vi.end(), 1);//正確粥血，將所有元素置為1
}

2.2 拷貝copy

void copy_display(){
    int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    int b[sizeof(a) / sizeof(*a)];
    auto pos = copy(begin(a), end(a), b);
    //三點(diǎn)說明：
    //1. sizeof在編譯時(shí)計(jì)算，所以支持用來定義數(shù)組b的大小
    //2. begin(a),end(a)指向a的第一個(gè)元素，以及尾后位置
    //3. 返回值pos指向目標(biāo)迭代器遞增后的值立莉，此例中pos恰好指向b的尾后迭代器
}

2.3 替代replace

void replace_display(){
    vector<int> vi = { 1, 2, 1, 4, 1, 6, 1, 8, 1 };
    int nOld = 1, nNew = 10;
    replace(vi.begin(), vi.end(), nOld, nNew);
}
//將vi中所有1替換為10

3 重排算法

某些算法會(huì)重排容器中元素的順序绢彤，例如sort和unique，前者對(duì)元素進(jìn)行排序蜓耻，后者將唯一的元素移至前段，重復(fù)的元素移至后端械巡。常見的用法如下：

3.1 sort/stable_sort

bool compare_int(int& a, int& b){
    return a > b;
}
void sort_display(){
    vector<int> vi = { 3, 1, 4, 2, 4, 2, 1, 3, 5, 6, 8, 4, -5 };
    sort(vi.begin(), vi.end());//升序重排
    sort(vi.rbegin(), vi.rend());//降序重排
    sort(vi.begin(), vi.end(), compare_int);//支持二元謂詞
}
//三點(diǎn)說明：
//1. `sort`用快速排序?qū)崿F(xiàn)刹淌，是不穩(wěn)定的排序算法，`stable_sort`用歸并排序?qū)崿F(xiàn)讥耗，是穩(wěn)定的排序算法
//2. `sort`和`stable_sort`都支持二元謂詞有勾，來重新定義元素間的比較
//3. 基本數(shù)據(jù)類型的降序重排，可以直接使用`rbegin()`和`rend()`實(shí)現(xiàn)

3.2 unique/unique_copy

void unique_display(){
    vector<int> vi = { -5, 3, 1, 4, 2, 4, 2, 1, 3, 5, 6, 8, 4 };
    sort(vi.begin(), vi.end());//升序重排
    auto pos = unique(vi.begin(), vi.end());
    for (size_t i = 0; i < vi.size(); ++i){
        cout << vi[i] << " ";
    }
    cout << endl<<*pos << endl;
    //vi此時(shí)為{-5,1,2,3,4,5,6,8,4,4,5,6,8};
    //pos指向不重復(fù)區(qū)域的下一個(gè)迭代器古程，此處指向vi[4] = 4;
}
//unique_copy是unique的“_copy”版本蔼卡，返回的是生成的序列的最后一個(gè)元素的下一個(gè)位置

4 定制操作

4.1 謂詞

謂詞（predicate）是一個(gè)可調(diào)用的表達(dá)式，其返回結(jié)果是一個(gè)能用做條件的值挣磨，標(biāo)準(zhǔn)庫算法將謂詞分為一元謂詞和二元謂詞兩類雇逞。謂詞可以作為參數(shù)傳遞進(jìn)函數(shù)，如上例3.1所示茁裙。

4.2 lambda表達(dá)式

使用謂詞給算法傳遞參數(shù)時(shí)塘砸，受到嚴(yán)格的限制。當(dāng)需要傳遞更多參數(shù)給算法時(shí)晤锥，可以使用lambda表達(dá)式掉蔬。lambda 表達(dá)式是一個(gè)可調(diào)用的代碼單元，我們可以將它理解為一個(gè)匿名的內(nèi)聯(lián)函數(shù)矾瘾。

C++11 的 lambda 表達(dá)式規(guī)范如下女轿。其中，capture表示捕獲列表壕翩，它可以捕獲所在函數(shù)的定義的局部變量蛉迹。params，ret 戈泼，body和普通函數(shù)一樣婿禽，代表參數(shù)、返回類型和函數(shù)體大猛。

(1) [ capture ] ( params ) mutable exception attribute -> ret { body }   
(2)    [ capture ] ( params ) -> ret { body }        
(3) [ capture ] ( params ) { body }  
(4) [ capture ] { body }

下面通過幾個(gè)簡單的實(shí)例來了解其用法

• (1) 忽略參數(shù)列表和返回類型

void lambda_dispaly1(){
    auto f = [] {return 10; };
    cout << f() << endl;
}
//capture扭倾，返回類型為空，只定義了body

• (2) 向lambda傳參

void lambda_dispaly2(){
    auto f = [](const string a, const string b) {return a <b; };
    cout << f("1", "2") << endl;
}
//capture為空挽绩，定義了params和body

• (3) 使用捕獲列表

void lambda_dispaly3(size_t size){
    auto f = [size](const string a) {return a.size() >= size; };
    cout << f("123") << endl;
}
//從所定義的函數(shù)體中捕獲局部變量size

• (4) 引用捕獲

//與普通函數(shù)相同膛壹，lambda表達(dá)式傳遞參數(shù)時(shí)也有傳值和傳引用兩種，前述的都是傳值捕獲，下例為引用捕獲
void lambda_dispaly4(size_t &size){
    auto f = [&size](const string a) {return a.size() >= size; };
    cout << f("123") << endl;
}
//從所定義的函數(shù)體中捕獲局部變量size的引用

• (5) 隱式捕獲模聋、混合捕獲

void lambda_dispaly5(vector<string>&words, size_t size){
    stable_sort(words.begin(), words.end(),
        [](const string& a, const string & b)
            {return a.size() < b.size(); });
    //查找第一個(gè)滿足size()>size的元素
    auto pos = find_if(words.begin(), words.end(), 
        [&](string & a)
            {return a.size() > size; });
    int count = words.end() - pos;
    cout << count << endl;
}
//說明三點(diǎn)：
//1. 除顯示捕獲外肩民，我們還可以讓編譯器來推斷我們要捕獲的變量。
//2. 我們需要在capture捕獲列表中填寫 = 或 & 指示編譯器采用值捕獲還是引用捕獲
//3. 當(dāng)我們想混合使用隱式和顯示捕獲時(shí)链方，捕獲列表的一個(gè)元素必須是 = 或 &持痰，此符號(hào)指定了默認(rèn)捕獲方式為引用和值。

• (6) 可變lambda

void lambda_dispaly6(){
    size_t vi = 10;
    auto f = [vi]()mutable{return  ++vi; };
    cout << f() << endl;
}
//默認(rèn)情況下祟蚀，對(duì)于一個(gè)值被拷貝的對(duì)象工窍，lambda表達(dá)式不會(huì)改變其值，因此必須加上mutable來申請(qǐng)前酿，其捕獲的變量值可變患雏。

• (7) 指定返回類型lambda

void lambda_dispaly7(){
    auto f = [](const string &a, const string &b)->bool 
    {if (a < b) return true; else return false; };
    cout << f("1", "2") << endl;
}
//默認(rèn)情況下，如果lambda函數(shù)體包含return之外的任何語句罢维，編譯器則返回void淹仑。
//此時(shí)，當(dāng)我們需要為lambda定義返回類型肺孵，必須使用尾置返回類型匀借。

4.3 參數(shù)綁定

對(duì)于只在一兩個(gè)地方使用的簡單操作，lambda表達(dá)式是最高效的悬槽，如果需要在多個(gè)地方使用相同的定制操作怀吻，我們可以使用標(biāo)準(zhǔn)庫bind函數(shù)。bind可以重排參數(shù)順序初婆。

bind函數(shù)定義在頭文件functional中蓬坡，使用格式如下：

auto newFun = bind(Fun, arg_list);

newFun本身是一個(gè)可調(diào)用對(duì)象，arg_list是一個(gè)用逗號(hào)分隔的參數(shù)列表磅叛，其中可能包含"_n"的名字（定義在std::placeholders中）屑咳，此為”占位符“，表示newFun中的參數(shù)弊琴。_1與newFun的第一個(gè)參數(shù)對(duì)應(yīng)兆龙，_2與newFun第二參數(shù)對(duì)應(yīng)，依次類推敲董。

• (1) 重排參數(shù)

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std::placeholders;
using namespace std;
auto bind_display1 = bind(lambda_dispaly5, _2, _1);//lambda_dispaly5定義參見4.2
int main(){
    vector<string> vecStr = { "abc", "bscd", "tsed" };
    bind_display1(4, vecStr);
    return 0;
}

• (2) 參數(shù)個(gè)數(shù)修改

auto bind_display2 = bind(lambda_dispaly5, _1, 4);
int main(){
    vector<string> vecStr = { "abc", "bscd", "tsed" };
    bind_display2(vecStr);
    return 0;
}
//將lambda_dispaly5中第二參數(shù)設(shè)置為4
//注意紫皇，bind中第2個(gè)到第n個(gè)函數(shù)與lambda_dispaly5相對(duì)應(yīng)。"_1","_2"與bind_display函數(shù)對(duì)應(yīng)腋寨。

5 迭代器

除了為每個(gè)容器定義的迭代器之外聪铺，標(biāo)準(zhǔn)庫在頭文件iterator中還定義了額外幾種迭代器。這些迭代器包括以下幾種：

• 1）插入迭代器：
  這些迭代器被綁定到一個(gè)容器上萄窜，可用來向容器插入元素
• 2）流迭代器：
  這些迭代器被綁定到輸入或輸出上铃剔，可用來遍歷所有關(guān)聯(lián)的IO流
• 3）反向迭代器：
  這些迭代器向后而不是向前移動(dòng)撒桨。除了forward_list之外的標(biāo)準(zhǔn)庫容器都有反向迭代器
• 4）移動(dòng)迭代器：
  這些專用的迭代器不是拷貝其中的元素，而是移動(dòng)它們键兜。

1）插入迭代器

插入迭代器接受一個(gè)容器凤类，生成一個(gè)迭代器，能夠?yàn)榻o定容器添加元素普气。其根據(jù)插入位置不同谜疤，分為以下三種類型：

• back_inserter創(chuàng)建一個(gè)使用push_back的迭代器
• front_inserter創(chuàng)建一個(gè)使用push_front的迭代器
• inserter創(chuàng)建一個(gè)使用insert的迭代器。

2）流迭代器

雖然iostream類型不是容器现诀，但標(biāo)準(zhǔn)庫定義了用于這些IO類型對(duì)象的迭代器茎截。istream_iterator讀取輸入流，ostream_iterator向一個(gè)輸出流寫數(shù)據(jù)赶盔。通過使用流迭代器，我們可以用泛型算法從流對(duì)象讀取數(shù)據(jù)以及向其寫入數(shù)據(jù)榆浓。

3）反向迭代器

反向迭代器就是在容器中從尾元素向首元素反向移動(dòng)的迭代器于未。對(duì)于反向迭代器，遞增（以及遞減）操作的含義會(huì)顛倒過來陡鹃。遞增一個(gè)反向迭代器（++it）會(huì)移動(dòng)到前一個(gè)元素烘浦；遞減一迭代器（--it）會(huì)移動(dòng)到下一個(gè)元素。

除了forward_list之外萍鲸，其他容器都支持反向迭代器闷叉。我們可以通過調(diào)用rbegin、rcend脊阴、crbegin和crend成員函數(shù)來獲得反向迭代器握侧。這些成員函數(shù)返回指向容器尾元素和首元素之前一個(gè)位置的迭代器。與普通迭代器一樣嘿期，反向迭代器也有const和非const版本品擎。