[C++ 面試基礎知識總結] 泛型算法

基礎泛型算法

泛型算法本身運行於迭代器之上，不會執行容器的操作，可以改變容器中保存元素的值，也可以在容器內移動元素，但永遠不會直接添加或刪除元素。插入迭代器是一種特殊的迭代器，當算法操作插入迭代器時，迭代器可以向容器添加元素，但算法本身永遠不會做這樣的事。

只讀算法

只讀算法只會讀取其輸入范圍內的元素，而從不改變元素。

    vector v = {1,2,3,4,5,4,3,2,1};
    string s1 = "Summer love C++";
    string s2 = "Summer love Swift";

    auto f = find(v.begin(), v.end(), 2);  //find函數是查找給定值在給定范圍內的位置
    cout << (f != v.end()) << endl;  //如果查找到，返回第一個等於給定值元素的迭代器，否則返回尾後迭代器
    auto c = count(v.begin(), v.end(), 2);  //count函數返回的是給定值在給定范圍內的出現次數
    auto sum = accumulate(v.begin(), v.end(), 0);  //accumulate函數是將給定范圍內的所有元素相加，最後一個參數為初始值
    auto sSum = accumulate(s1.begin(), s1.end(), string("Hello:")); // 字符串字面值不能執行+運算，所以最後一個參數不能寫成"Hello:"
    auto isEuqal = equal(s1.begin(),s1.end() - 3,s2.begin());//isEqual函數是比較兩個序列是否相等，前兩個參數表示第一個序列的范圍，最後一個參數表示第二個序列的起始位置（兩個序列長度相等）

寫容器算法

    vector v = {1,2,3,4,5};
    vector v2;

    fill(v.begin(), v.end(), 0);  //將給定范圍內的元素全部替換為0
    fill_n(v.begin(), 3, -1);  //將給定位置開始的3個元素全部替換為-1
    fill_n(back_inserter(v), 5, 1);  //使用插入迭代器在容器尾部添加5個值為1的元素
    replace(v.begin(), v.end(), 0, 1);  //將給定范圍內所有值為0的元素替換為1
    replace_copy(v.begin(), v.end(), back_inserter(v2), -1, 1);  //將給定范圍內的所有元素拷貝出來，再將所有為-1的元素替換為1後有插入迭代器添加在v2尾部，v1中的元素沒有變化

重排容器元素算法

    vector v = {1,2,3,4,5,4,3,2,1};

    sort(v.begin(), v.end());  //按大小重排v中的元素 {1，1，2，2，3，3，4，4，5}
    auto end_unique = unique(v.begin(), v.end()); //將不重復的元素覆蓋到容器前部，後部不動 {1，2，3，4，5，3，4，4，5}，並返回不重復區域之後第一個位置的迭代器
    v.erase(end_unique,v.end()); // 可利用上面返回的迭代器刪除重復元素

定制操作

向算法傳遞函數

可以使用自定義的條件來給容器中的元素排序。下面以給幾個兩位數排序為例。

//自定義排序規則為按照各位數字的大小來排序
bool isSmaller(const int &i1, const int &i2){
    return i1%10 < i2%10;
}

    vector v = {15,24,33,42,51,41,32,23,14};
    //在sort函數後增加第三個參數，自定義的謂詞，排序結果：51 41 42 32 33 23 24 14 15
    sort(v.begin(), v.end(),isSmaller);

如果希望個位數字大小相同的數字，再按十位數字大小來排序，可以用穩定排序

    vector v = {15,24,33,42,51,41,32,23,14};

    //先按照兩位數大小進行排序，順便按十位數字大小排序
    sort(v.begin(), v.end());
    //采用穩定排序的函數按照個位數字大小，再對容器進行排序，由於是穩定排序，不會改變相同個位數字大小的元素之間的原有順序。排序結果：41 51 32 42 23 33 14 24 15 
    stable_sort(v.begin(), v.end(), isSmaller);

lambda表達式

調用普通函數：

int func(){
    return 1;
}

auto f = func();

調用lambda表達式可以得到同樣結果

// 中括號內為捕獲列表，小括號內為參數列表，->後為返回類型，花括號內為函數體
auto f = []() -> int{return 1;};

lambda表達式還可以省略參數列表和返回類型

auto f = []{return 1;};

用lambda表達式可以簡化之前的排序的代碼：

    vector v = {15,24,33,42,51,41,32,23,14};

    sort(v.begin(), v.end());
    //第三個參數傳入一個與isSmaller函數等價的lambda表達式
    stable_sort(v.begin(), v.end(), [](const int &i1, const int &i2){return i1%10 < i2%10;});

在上述vector的基礎上，輸出所有兩位數四捨五入後的值

    int n = 5;
    //采用find_if函數找到第一個復合條件的位置，這裡lambda表達式需要使用局部變量n，需要在捕獲列表中加入n，函數體才能使用n
    auto pos = find_if(v.begin(), v.end(), [n](const int &i){return i%10 >= n;});
    //for_each函數是對所有序列中的元素分別調用一次lambda表達式
    for_each(v.begin(), pos, [](const int &i){cout << (i/10)*10 <<" ";});
    for_each(pos, v.end(), [](const int &i){cout << (i/10+1)*10<<" ";});

lambda表達式可以采取值捕獲和引用捕獲兩種方式。

    auto v1 = 1, v2 = 2;
    auto f1 = [v1] { return v1;};  //值捕獲，之後改變v1的值不會影響f1()的值
    auto f2 = [&v2] { return v2;};  //引用捕獲，之後改變v2的值會改變f2()的值
    auto f3 = [=]{return v1 + v2;};  //對所有變量采用值捕獲
    auto f4 = [&]{return v1 + v2;};  //對所有變量采用引用捕獲
    auto f5 = [=,&v2]{return v1 + v2;};  //對除v2外的所有變量采用值捕獲
    auto f6 = [&,v1]{return v1 + v2;};  //對除v1外的所有變量采用引用捕獲
    auto f7 = [v1] () mutable {return ++v1;};  //加上mutable關鍵字可以在函數體內改變捕獲變量的值

如果lambda函數體包含了除return以外的任何語句，則編譯器會假定lambda返回void，如果要返回其他類型，需要顯示指定出來。

auto f = [v1] ()  mutable ->int{ ++v1 ; return v1;};

參數綁定

bool checkNumber(const int &i, int n){
    return i%10 >= n;
}

由於函數有兩個參數，而find_if只接受一元謂詞，不能寫成如下形式：

auto pos = find_if(v.begin(), v.end(), checkNumber);

這個時候就需要用到bind函數

// _1表示第一個生成的可調用對象中參數的位置，依次類推_2表示第二個，使用這些占位符時需要聲明使用命名空間 using namespace std::placeholders;
auto pos = find_if(v.begin(), v.end(), bind(checkNumber, _1,n));

等價於

auto pos = find_if(v.begin(), v.end(), [n](const int &i){return i%10 >= n;});

占位符的順序是傳遞參數的順序，例如之前的

sort(v.begin(), v.end(),isSmaller);

如果改寫為

sort(v.begin(), v.end(),bind(isSmaller, _2, _1));

則相當於顛倒了兩個參數的順序，最終得到的序列將會是從大到小的。

在bind函數中，非占位符參數是引用的時候，需要用ref函數或cref函數（常量）保護起來，寫成以下形式

    int x =5;
    int &n = x;
    auto pos = find_if(v.begin(), v.end(), bind(checkNumber, _1,ref(n)));


    const int &m = 5;
    auto pos = find_if(v.begin(), v.end(), bind(checkNumber, _1,cref(m)));

特殊迭代器

插入迭代器

插入迭代器是一種迭代器適配器，它接收一個容器，生成一個迭代器，能實現給定容器添加元素。該迭代器調用容器操作來向給定容器的指定位置插入一個元素。插入迭代器有3種類型，只是插入位置存在差異。

    list l = {1,2,3,4,5};
    list l1,l2,l3;

    copy(l.begin(), l.end(), front_inserter(l1));  //在頭部插入，copy函數執行完成後結果為5 4 3 2 1 
    copy(l.begin(), l.end(), back_inserter(l2));  //在尾部插入，copy函數執行完成後結果為1 2 3 4 5 
    copy(l.begin(), l.end(), inserter(l3, l3.begin()));  //在指定位置插入，copy函數執行完成後結果為1 2 3 4 5 

需要注意的是，front_inserter會將插入元素序列顛倒過來，類似數據結果中鏈表的頭插法。

iostream迭代器

通過流迭代器，可以用泛型算法從流對象讀取數據以及向其寫入數據。

    // 定義兩個輸入流迭代器in，eof，in與cin綁定，eof為空，相當於尾後迭代器
    istream_iterator in(cin), eof;
    // 用accumulate函數對輸入的整數求和
    cout << accumulate(in, eof, 0) << endl;

    vector v = {1,2,3,4,5};
    // 定義一個輸出流迭代器out,與cout綁定，每個值後面都輸出一個" "
    ostream_iterator out(cout," ");
    // 將vector拷貝到輸出流迭代器
    copy(v.begin(), v.end(), out);
    cout << endl;

反向迭代器

反向迭代器是在容器中從尾元素向首元素反向移動的迭代器，rbegin函數返回的指向容器尾元素的迭代器，rend函數返回指向容器首元素之前位置的迭代器。crbegin和crend為相應的const型反向迭代器。

    string s = "C++,Objective-C,Swift";
    // 反向查找最後一個單詞，找到逗號為止
    auto last = find(s.crbegin(), s.crend(), ',');

    // 輸出結果為 tfiwS ，因為構造string的兩個迭代器為反向迭代器
    cout << string(s.crbegin(),last) << endl;
    // 輸出結果為 Swift，調用base函數可以將反向迭代器轉換為普通迭代器
    cout << string(last.base(),s.cend()) << endl;

5類迭代器

算法所要求的迭代器操作可以分為5個類別，每個算法都會對它的每個迭代器參數指明須提供哪類迭代器。

輸入迭代器：只讀不寫，單遍掃描，只能遞增，find和accumulate要求輸入迭代器，istream_iterator是輸入迭代器
輸出迭代器：只寫不讀，單遍掃描，只能遞增，copy的第三個參數和ostream_iterator就是輸出迭代器
前向迭代器：可讀寫，多遍掃描，只能遞增，replace要求前向迭代器，forward_list上的迭代器也是前向迭代器
雙向迭代器：可讀寫，多遍掃描，可遞增遞減，reverse要求雙向迭代器，list上的迭代器也支持雙向迭代器
隨機訪問迭代器：可讀寫，多遍掃描，支持全部迭代器運算，sort要求隨機訪問迭代器，array，deque，string，vector的迭代器和內置數組的指針都是隨機訪問迭代器。

鏈表的特定容器算法

由於鏈表類型不支持要求隨機訪問迭代器的通用算法，所以定義了一些類似的算法。

//  用於提供比較個位數字大小謂詞的函數
bool isSmaller(const int &i1, const int &i2){
    return i1%10 < i2%10;
}

//  用於提供判定各位數字是否相等謂詞的函數
bool isEuqal(const int &i1, const int &i2){
    return i1%10 == i2%10;
}


int main(int argc, const char * argv[]) {

    listl {15,24,33,42,51};
    listl2 {41,32,23,14};

    // 將l2的元素全部合並到l中，合並後l2為空。l和l2都必須有序，合並後會自動排序。合並後的l： 14 15 23 24 32 33 41 42 51 
    l.merge(l2);  

    // 根據個位數字大小排序  排序後的l：41 51 32 42 23 33 14 24 15 
    l.sort(isSmaller);

    // 刪除個位數字重復的元素  刪除後的l：41 32 23 14 15 
    l.unique(isEuqal);
    return 0;
}

鏈表還定義了splice算法，以下2種寫法等價，都是將l2所有元素移動到l尾部，並從l2中刪除

    l.splice(l.end(), l2);
    l.splice(l.end(), l2, l2.begin(),l2.end());

如果只移動一個元素可以寫成如下形式

    l.splice(l.end(), l2, l2.begin());

注意：多數鏈表特有算法與其通用版本很相似，但不完全相同，鏈表特有版本的一個至關重要的區別是會改變底層的容器。例如merge算法將l2合並到l中後，會將l2的全部元素從l2列表中刪除。但這些刪除的元素依舊存在，只是存在於l中了。