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

參考書籍：《c++ primer》

<a href="#c-%e9%9d%a2%e8%af%95%e5%9f%ba%e7%a1%80%e7%9f%a5%e8%af%86%e6%80%bb%e7%bb%93-%e6%b3%9b%e5%9e%8b%e7%ae%97%e6%b3%95">c 面試基礎知識總結 泛型算法</a>

<a href="#%e7%9b%ae%e5%bd%95">目錄</a>

<a href="#%e5%9f%ba%e7%a1%80%e6%b3%9b%e5%9e%8b%e7%ae%97%e6%b3%95">基礎泛型算法</a>

<a href="#%e5%8f%aa%e8%af%bb%e7%ae%97%e6%b3%95">隻讀算法</a>

<a href="#%e5%86%99%e5%ae%b9%e5%99%a8%e7%ae%97%e6%b3%95">寫容器算法</a>

<a href="#%e9%87%8d%e6%8e%92%e5%ae%b9%e5%99%a8%e5%85%83%e7%b4%a0%e7%ae%97%e6%b3%95">重排容器元素算法</a>

<a href="#%e5%ae%9a%e5%88%b6%e6%93%8d%e4%bd%9c">定制操作</a>

<a href="#%e5%90%91%e7%ae%97%e6%b3%95%e4%bc%a0%e9%80%92%e5%87%bd%e6%95%b0">向算法傳遞函數</a>

<a href="#lambda%e8%a1%a8%e8%be%be%e5%bc%8f">lambda表達式</a>

<a href="#%e5%8f%82%e6%95%b0%e7%bb%91%e5%ae%9a">參數綁定</a>

<a href="#%e7%89%b9%e6%ae%8a%e8%bf%ad%e4%bb%a3%e5%99%a8">特殊疊代器</a>

<a href="#%e6%8f%92%e5%85%a5%e8%bf%ad%e4%bb%a3%e5%99%a8">插入疊代器</a>

<a href="#iostream%e8%bf%ad%e4%bb%a3%e5%99%a8">iostream疊代器</a>

<a href="#%e5%8f%8d%e5%90%91%e8%bf%ad%e4%bb%a3%e5%99%a8">反向疊代器</a>

<a href="#5%e7%b1%bb%e8%bf%ad%e4%bb%a3%e5%99%a8">5類疊代器</a>

<a href="#%e9%93%be%e8%a1%a8%e7%9a%84%e7%89%b9%e5%ae%9a%e5%ae%b9%e5%99%a8%e7%ae%97%e6%b3%95">連結清單的特定容器算法</a>

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

隻讀算法隻會讀取其輸入範圍内的元素，而從不改變元素。

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

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

調用普通函數：

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

lambda表達式還可以省略參數清單和傳回類型

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

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

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

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

由于函數有兩個參數，而find_if隻接受一進制謂詞，不能寫成如下形式：

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

等價于

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

如果改寫為

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

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

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

需要注意的是，front_inserter會将插入元素序列颠倒過來，類似資料結果中連結清單的頭插法。

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

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

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

輸入疊代器：隻讀不寫，單遍掃描，隻能遞增，find和accumulate要求輸入疊代器，istream_iterator是輸入疊代器

輸出疊代器：隻寫不讀，單遍掃描，隻能遞增，copy的第三個參數和ostream_iterator就是輸出疊代器

前向疊代器：可讀寫，多遍掃描，隻能遞增，replace要求前向疊代器，forward_list上的疊代器也是前向疊代器

雙向疊代器：可讀寫，多遍掃描，可遞增遞減，reverse要求雙向疊代器，list上的疊代器也支援雙向疊代器

随機通路疊代器：可讀寫，多遍掃描，支援全部疊代器運算，sort要求随機通路疊代器，array，deque，string，vector的疊代器和内置數組的指針都是随機通路疊代器。

由于連結清單類型不支援要求随機通路疊代器的通用算法，是以定義了一些類似的算法。

連結清單還定義了splice算法，以下2種寫法等價，都是将l2所有元素移動到l尾部，并從l2中删除

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

注意：多數連結清單特有算法與其通用版本很相似，但不完全相同，連結清單特有版本的一個至關重要的差別是會改變底層的容器。例如merge算法将l2合并到l中後，會将l2的全部元素從l2清單中删除。但這些删除的元素依舊存在，隻是存在于l中了。