<Effective STL>筆記--算法

5 算法

~~~~~~~

5.1 確定目标區間足夠大或者在算法執行時可以增加大小

===================================================

   1. 在算法中,要往Container中插入新資料,需要使用插入疊代器（比如，從back_inserter、front_inserter或inserter傳回的疊代器之一）。

   2. reserve隻增加容器的容量:容器的大小仍然沒有改變。

      即使調用完reserve，當你想要讓容器把新元素加入到vector或string時，你也必須對算法使用插入疊代器.

   3. 但有時候你要覆寫現有容器的元素而不是插入新的。當這種情況時，你不需要插入疊代器，但你仍然需要按照本條款的建議來確定你的目的區間足夠大。

      可以使用resize來確定容器中有足夠的元素

      *注意:resize和reserve之間的差別*

5.2 選擇合适的排序算法

=======================

   1. partial_sort(itrBeg,itrSortEnd,itrEnd)

      對[itrBeg,itrEnd)之間的元素進行排序,但隻有[itrBeg,itrEnd]内的元素處于有序狀态.

      适用于從整個序列中抽取最好的前N個元素進行排序

   2. nth_element(itrBeg,itrNth,itrEnd)

      對區間[itrBeg,itrEnd)進行排序,保證itrNth之前的所有元素都小于itrNth,itrNth之後的元素都大于itrNth

      适用于從整個序列中抽取最好的前N個元素,但不用進行排序.

      也可用來找出排在第n位的元素

   3. stable_sort(itrBegin,itrEnd)

      排序時,相等元素的位置不變----此為穩定性

   4. stable_partition/partition(itrBegin,itrEnd,bool判别函數)

      傳回一個iterator,在這個itr之前所有判别函數傳回true,在itr之後所有的判别函數是false

   5. 唯一我們可能會但不能使用sort、stable_sort、partial_sort或nth_element的容器是list

      但list通過提供sort成員函數做了一些補償。

   6. 算法sort、stable_sort、partial_sort和nth_element需要随機通路疊代器

      而partition和stable_partition隻需要雙向疊代器

5.3 如果你真的想删除東西的話,就在類似remove的算法後接上erase

=============================================================

   1. remove不做什麼?

      remove接收指定它操作的元素區間的一對疊代器.它不接收一個容器.

      而唯一從容器中除去一個元素的方法是在那個容器上調用一個成員函數,而且因為remove無法知道它正在操作的容器,是以remove不可能從一個容器中除去元素.

      也就是說從一個容器中remove元素不會改變容器中元素的個數.

   2. remove做了什麼?

      remove移動指定區間中的元素直到所有"不删除的"元素在區間的開頭(相對位置和原來它們的一樣).

      它傳回一個指向最後一個"不删除的"元素的疊代器的下一個位置.傳回值是區間的"新邏輯終點".

   3. remove與partition的差別

      一般來說，調用完remove後，從區間中删除的值可能是也可能不在區間中繼續存在.(傳回的疊代器所指的元素及後面的元素無意義了)

      而partition則保留所有的值不丢失

5.4 堤防在指針的容器上使用類似remove的算法

===========================================

   1. 對指針的容器上使用remove算法,被删除的指針元素會被覆寫但是卻不被删除,這就造成資源洩漏.

   2. 對于計數引用的智能指針,可以安全地使用remove算法.

5.5 注意哪個算法需要有序區間

=============================

   1. 隻能操作有序資料的算法表:

      * binary_search

      * lower_bound

      * upper_bound

      * equal_range

      * set_union      

      * set_intersection

      * set_difference

      * set_symmetric_difference

      * merge

      * inplace_merge

      * includes

   2. 下面的算法一般用于有序區間，雖然它們不要求：

      * unique

      * unique_copy

   3. unique從一個區間除去元素的方式和remove一樣，也就是說它隻是區分出不除去的元素和要删除的資料,而并不能真正進行删除操作.

   4. 注意區間的排序方法和算法的排序方法要保持一緻.

      例如binary_search預設為升續排列,就不能用于降續排列的區間中.

5.6 通過mismatch或lexicographical比較實作簡單的忽略大小寫字元串比較

====================================================================

5.7 了解copy_if的正确實作

==========================

   1. 不正确的實作:

      然而

  not1不能直接應用于一個函數指針，函數指針必須先傳給ptr_fun。

  要調用這個copy_if實作，你必須傳遞的不僅是一個函數對象，而且是一個可适配的函數對象。

  這夠簡單了，但是想要成為STL算法使用者的人應該不必這樣。

  标準STL算法從來不要求它們的仿函數是可适配的，copy_if也不應該要求。

  上面的實作是好的，但不夠好。

   2. 正确的實作為

5.8 用accumulate或for_each來擷取自定義的區間統計資訊

=====================================================

   1. accumulate不存在于orithm>。取而代之的是，它和其他三個“數值算法”都在<numeric>中。（那三個其它的算法是inner_product、adjacent_difference和partial_sum。）

   2. accumulate存在兩種形式。

      * 帶有一對疊代器和初始值的形式可以傳回初始值加由疊代器劃分出的區間中值的和

      * accumulate的另一種形式，帶有一個初始值,疊代器區間與一個任意的統計函數，算法會把初值與一個元素作為統計函數的兩個參數,并将結果作為下一個元素的初值,重複調用統計元素直到疊代器結束

   3. accumulate直接傳回那些我們想要的統計值，而for_each傳回一個函數對象