天天看點

從零開始學C++之STL(七):剩下5種算法代碼分析與使用示例(remove 、rotate 、sort、lower_bound、accumulate)

一、移除性算法 (remove)

如下圖所示:

從零開始學C++之STL(七):剩下5種算法代碼分析與使用示例(remove 、rotate 、sort、lower_bound、accumulate)

假設現在想要remove 的元素是3,則傳入到 _Remove_copy 函數的3個參數如上圖第一行所示,Val 即3。

接着周遊First ~ Last 區間的元素,将非移除元素拷貝到前面,覆寫前面的元素,最後的指向如圖,函數傳回的是Dest 位置,如下代

碼所示:

for (; _First != _Last; ++_First)

if (!(*_First == _Val))

            *_Dest++ = *_First;

由上圖可看出移除性算法并沒有改變元素的個數,如果要真正删除,可以将remove 的傳回值傳入erase 進行删除,如:

v.erase(remove(v.begin(), v.end(), 3), v.end()); 即會将後面兩個元素4 和 5 删除掉。

在這裡順便提一下,erase 會使目前疊代器失效,但可以傳回下一個疊代器,故如果需要在周遊中删除,下面的做法才是正确的:

示例代碼1:

二、變序性算法( rotate)

rotate 調用了_Rotate,實際上_Rotate 繼續調用了某個函數,内部實作代碼比較長,而且不容易看懂,這邊可以看一下簡易的等價

版本實作,來自這裡,如下:

假設一個容器有 1 2 3 4 5 6 六個元素,現在想把 1 2 放到後面去,可以這樣寫 rotate(v.begin(), v.begin()+2, v.end());  如下圖所示:

從零開始學C++之STL(七):剩下5種算法代碼分析與使用示例(remove 、rotate 、sort、lower_bound、accumulate)

即将first 與 next 對應的元素互換且不斷向前推進,直到first == next 為止。

三、排序算法 (sort)

sort 重載了兩個版本,第一個版本隻有2個參數,預設按從小到大排序(using <code>operator&lt;)</code>;第二個版本有三個參數,即可以自定義比較邏輯

(_Pred)。它們都調用了标準庫的std::_Sort, 跟蹤進去發現比較複雜,在_Sort 内會根據一些條件選擇不同的排序方式,如标準庫的堆排序,合并

排序,插入排序等等。站在使用的角度看,沒必要去深究,但如果是想學習相關的排序,那是很好的資源。

示例代碼2:

此外,sort 有個坑,如果你自己傳遞比較邏輯,需要注意,如下:

從零開始學C++之STL(七):剩下5種算法代碼分析與使用示例(remove 、rotate 、sort、lower_bound、accumulate)

四、已序區間算法 (lower_bound 、upper_bound)

使用這些算法的前提是區間已經是有序的。

lower_bound() 傳回第一個“大于等于給定值" 的元素位置,其實還重載了另一個low_bound 版本,如下:

也就是可以自定義比較邏輯,需要注意的是如果使用這個版本,那麼區間應該本來就是按comp 方法排序的,如下面這句話:

The elements are compared using <code>operator&lt;</code> for the first version, and comp for the second. The elements in the range shall already

 be sorted according to this same criterion (<code>operator&lt;</code> or comp), or at least partitioned with respect to val.

由于是已序區間,是以函數内用的是二分查找,而兩個版本主要的代碼不同在于:

_DEBUG_LT(*_Mid, _Val)

_DEBUG_LT_PRED(_Pred, *_Mid, _Val)

upper_bound 與 lower_bound 類似,不過傳回的是第一個”大于給定值“ 的元素位置。

示例代碼3:

五、數值算法(accumulate)

accumulate 重載了兩個版本,第一個版本實作的是累加,第二個版本帶_Func 參數,可以自定義計算,比如累乘等。代碼都比較好了解,就不贅述

了。看下面的示例代碼4:

參考:

C++ primer 第四版

Effective C++ 3rd

C++程式設計規範