从零开始学C++之STL（七）：剩下5种算法代码分析与使用示例（remove 、rotate 、sort、lower_bound、accumulate）...
一、移除性算法 （remove）
?
C++ Code?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | ? | //?TEMPLATE?FUNCTION?remove_copy template?<? class?_InIt, ????????? class?_OutIt, ????????? class?_Ty?>? inline _OutIt?_Remove_copy(_InIt?_First,?_InIt?_Last, ????????????????????_OutIt?_Dest,? const?_Ty?&_Val,?_Range_checked_iterator_tag) { ???? //?copy?omitting?each?matching?_Val ????_DEBUG_RANGE(_First,?_Last); ????_DEBUG_POINTER(_Dest); ???? for?(;?_First?!=?_Last;?++_First) ???????? if?(!(*_First?==?_Val)) ????????????*_Dest++?=?*_First; ???? return?(_Dest); } template?<? class?_InIt, ????????? class?_OutIt, ????????? class?_Ty?>? inline _OutIt?unchecked_remove_copy(_InIt?_First,?_InIt?_Last, ?????????????????????????????_OutIt?_Dest,? const?_Ty?&_Val) { ???? //?copy?omitting?each?matching?_Val ???? return?_STD?_Remove_copy(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Dest,?_Val, ?????????????????????????????_STD?_Range_checked_iterator_tag()); } //?TEMPLATE?FUNCTION?remove template?<? class?_FwdIt, ????????? class?_Ty?>? inline _FwdIt?remove(_FwdIt?_First,?_FwdIt?_Last,? const?_Ty?&_Val) { ???? //?remove?each?matching?_Val ????_First?=?find(_First,?_Last,?_Val); ???? if?(_First?==?_Last) ???????? return?(_First);???? //?empty?sequence,?all?done ???? else ????{ ???????? //?nonempty?sequence,?worth?doing ????????_FwdIt?_First1?=?_First; ???????? return?(_STDEXT?unchecked_remove_copy(++_First1,?_Last,?_First,?_Val)); ????} } |
?
?
如下圖所示：
假設(shè)現(xiàn)在想要remove 的元素是3，則傳入到?_Remove_copy 函數(shù)的3個(gè)參數(shù)如上圖第一行所示，Val 即3。
接著遍歷First ~ Last 區(qū)間的元素，將非移除元素拷貝到前面，覆蓋前面的元素，最后的指向如圖，函數(shù)返回的是Dest 位置，如下代
碼所示：
for?(;?_First?!=?_Last;?++_First)
?if?(!(*_First?==?_Val))
????????????*_Dest++?=?*_First;
由上圖可看出移除性算法并沒(méi)有改變?cè)氐膫€(gè)數(shù)，如果要真正刪除，可以將remove 的返回值傳入erase 進(jìn)行刪除，如：
v.erase(remove(v.begin(), v.end(), 3), v.end()); 即會(huì)將后面兩個(gè)元素4 和 5 刪除掉。
示例代碼1：
?
C++ Code?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | ? | #include?<iostream> #include?<vector> #include?<list> #include?<algorithm> using? namespace?std; void?print_element( int?n) { ????cout?<<?n?<<? '?'; } int?main( void) { ???? int?a[]?=?{? 1,? 3,? 2,? 3,? 4,? 5?}; ????vector< int>?v(a,?a?+? 6); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ???? /*remove(v.begin(),?v.end(),?3); ????for_each(v.begin(),?v.end(),?print_element); ????cout<<endl;*/ ????v.erase(remove(v.begin(),?v.end(),? 3),?v.end()); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ???? return? 0; } |
?
?
二、變序性算法（?rotate）
?
C++ Code?| 1 2 3 4 5 6 7 | ? | template< class?_FwdIt>? inline void?rotate(_FwdIt?_First,?_FwdIt?_Mid,?_FwdIt?_Last) { ???? //?rotate?[_First,?_Last) ???? if?(_First?!=?_Mid?&&?_Mid?!=?_Last) ????????_Rotate(_CHECKED_BASE(_First),?_CHECKED_BASE(_Mid),?_CHECKED_BASE(_Last),?_Iter_cat(_First)); } |
?
rotate 調(diào)用了_Rotate，實(shí)際上_Rotate 繼續(xù)調(diào)用了某個(gè)函數(shù)，內(nèi)部實(shí)現(xiàn)代碼比較長(zhǎng)，而且不容易看懂，這邊可以看一下簡(jiǎn)易的等價(jià)
版本實(shí)現(xiàn)，來(lái)自這里，如下：
?
C++ Code?| 1 2 3 4 5 6 7 8 9 10 11 12 | ? | template?< class?ForwardIterator> void?rotate?(ForwardIterator?first,?ForwardIterator?middle, ?????????????ForwardIterator?last) { ????ForwardIterator?next?=?middle; ???? while?(first?!=?next) ????{ ????????swap?(*first++,?*next++); ???????? if?(next?==?last)?next?=?middle; ???????? else? if?(first?==?middle)?middle?=?next; ????} } |
?
?
假設(shè)一個(gè)容器有 1 2 3 4 5 6 六個(gè)元素，現(xiàn)在想把 1 2 放到后面去，可以這樣寫?rotate(v.begin(), v.begin()+2, v.end()); ?如下圖所示：
即將first 與 next 對(duì)應(yīng)的元素互換且不斷向前推進(jìn)，直到first == next 為止。
三、排序算法 （sort）
?
C++ Code?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | ? | template< class?_RanIt>? inline void?sort(_RanIt?_First,?_RanIt?_Last) { ???? //?order?[_First,?_Last),?using?operator< ????_DEBUG_RANGE(_First,?_Last); ????std::_Sort(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Last?-?_First); } template?<? class?_RanIt, ????????? class?_Pr?>? inline void?sort(_RanIt?_First,?_RanIt?_Last,?_Pr?_Pred) { ???? //?order?[_First,?_Last),?using?_Pred ????_DEBUG_RANGE(_First,?_Last); ????_DEBUG_POINTER(_Pred); ????std::_Sort(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Last?-?_First,?_Pred); } |
?
?
sort 重載了兩個(gè)版本，第一個(gè)版本只有2個(gè)參數(shù)，默認(rèn)按從小到大排序（using?operator<)；第二個(gè)版本有三個(gè)參數(shù)，即可以自定義比較邏輯
（_Pred）。它們都調(diào)用了標(biāo)準(zhǔn)庫(kù)的std::_Sort， 跟蹤進(jìn)去發(fā)現(xiàn)比較復(fù)雜，在_Sort 內(nèi)會(huì)根據(jù)一些條件選擇不同的排序方式，如標(biāo)準(zhǔn)庫(kù)的堆排序，合并
排序，插入排序等等。站在使用的角度看，沒(méi)必要去深究，但如果是想學(xué)習(xí)相關(guān)的排序，那是很好的資源。
示例代碼2：
?
C++ Code?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | ? | #include?<iostream> #include?<vector> #include?<list> #include?<algorithm> using? namespace?std; void?print_element( int?n) { ????cout?<<?n?<<? '?'; } bool?my_greater( int?a,? int?b) { ???? return?a?>?b; } int?main( void) { ???? int?a[]?=?{? 1,? 2,? 3,? 4,? 5,? 6?}; ????vector< int>?v(a,?a?+? 6); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ????rotate(v.begin(),?v.begin()?+? 2,?v.end()); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ????sort(v.begin(),?v.end()); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ????sort(v.begin(),?v.end(),?my_greater); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ???? return? 0; } |
?
?
四、已序區(qū)間算法 （lower_bound 、upper_bound）
使用這些算法的前提是區(qū)間已經(jīng)是有序的。
?
C++ Code?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | ? | //?TEMPLATE?FUNCTION?lower_bound template?<? class?_FwdIt, ????????? class?_Ty, ????????? class?_Diff?>? inline _FwdIt?_Lower_bound(_FwdIt?_First,?_FwdIt?_Last,? const?_Ty?&_Val,?_Diff?*) { ???? //?find?first?element?not?before?_Val,?using?operator< ????_DEBUG_ORDER_SINGLE(_First,?_Last,? true); ????_Diff?_Count?=? 0; ????_Distance(_First,?_Last,?_Count); ???? for?(;? 0?<?_Count;?) ????{ ???????? //?divide?and?conquer,?find?half?that?contains?answer ????????_Diff?_Count2?=?_Count?/? 2; ????????_FwdIt?_Mid?=?_First; ????????std::advance(_Mid,?_Count2); ????????_DEBUG_ORDER_SINGLE(_Mid,?_Last,? false); ???????? if?(_DEBUG_LT(*_Mid,?_Val)) ????????????_First?=?++_Mid,?_Count?-=?_Count2?+? 1; ???????? else ????????????_Count?=?_Count2; ????} ???? return?(_First); } template?<? class?_FwdIt, ????????? class?_Ty?>? inline _FwdIt?lower_bound(_FwdIt?_First,?_FwdIt?_Last,? const?_Ty?&_Val) { ???? //?find?first?element?not?before?_Val,?using?operator< ????_ASSIGN_FROM_BASE(_First, ??????????????????????_Lower_bound(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Val,?_Dist_type(_First))); ???? return?_First; } |
?
?
lower_bound() 返回第一個(gè)“大于等于給定值" 的元素位置，其實(shí)還重載了另一個(gè)low_bound 版本，如下：
?
C++ Code?| 1 2 3 4 5 6 7 | ? | //?TEMPLATE?FUNCTION?lower_bound?WITH?PRED template?<? class?_FwdIt, ????????? class?_Ty, ????????? class?_Diff, ????????? class?_Pr?>? inline _FwdIt?_Lower_bound(_FwdIt?_First,?_FwdIt?_Last, ???????????????????? const?_Ty?&_Val,?_Pr?_Pred,?_Diff?*) |
?
?
也就是可以自定義比較邏輯，需要注意的是如果使用這個(gè)版本，那么區(qū)間應(yīng)該本來(lái)就是按comp 方法排序的，如下面這句話：
The elements are compared using?operator<?for the first version, and?comp?for the second. The elements in the range shall already
?be?sorted?according to this same criterion (operator<?or?comp), or at least?partitioned?with respect to?val.
由于是已序區(qū)間，所以函數(shù)內(nèi)用的是二分查找，而兩個(gè)版本主要的代碼不同在于：
_DEBUG_LT(*_Mid,?_Val)
_DEBUG_LT_PRED(_Pred, *_Mid, _Val)
upper_bound 與 lower_bound 類似，不過(guò)返回的是第一個(gè)”大于給定值“ 的元素位置。
示例代碼3：
?
C++ Code?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | ? | #include?<iostream> #include?<vector> #include?<list> #include?<algorithm> using? namespace?std; void?print_element( int?n) { ????cout?<<?n?<<? '?'; } int?main( void) { ???? int?a[]?=?{? 1,? 10,? 10,? 14,? 15,? 16?}; ????vector< int>?v(a,?a?+? 6); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ????vector< int>::iterator?it; ????it?=?lower_bound(v.begin(),?v.end(),? 10); ???? if?(it?!=?v.end()) ????{ ????????cout?<<?it?-?v.begin()?<<?endl; ????} ????it?=?upper_bound(v.begin(),?v.end(),? 10); ???? if?(it?!=?v.end()) ????{ ????????cout?<<?it?-?v.begin()?<<?endl; ????} ???? return? 0; } |
?
?
五、數(shù)值算法（accumulate）
?
C++ Code?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | ? | //?TEMPLATE?FUNCTION?accumulate template?<? class?_InIt, ????????? class?_Ty?>? inline _Ty?_Accumulate(_InIt?_First,?_InIt?_Last,?_Ty?_Val) { ???? //?return?sum?of?_Val?and?all?in?[_First,?_Last) ????_DEBUG_RANGE(_First,?_Last); ???? for?(;?_First?!=?_Last;?++_First) ????????_Val?=?_Val?+?*_First; ???? return?(_Val); } template?<? class?_InIt, ????????? class?_Ty?>? inline _Ty?accumulate(_InIt?_First,?_InIt?_Last,?_Ty?_Val) { ???? //?return?sum?of?_Val?and?all?in?[_First,?_Last) ???? return?_Accumulate(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Val); } //?TEMPLATE?FUNCTION?accumulate?WITH?BINOP template?<? class?_InIt, ????????? class?_Ty, ????????? class?_Fn2?>? inline _Ty?_Accumulate(_InIt?_First,?_InIt?_Last,?_Ty?_Val,?_Fn2?_Func) { ???? //?return?sum?of?_Val?and?all?in?[_First,?_Last),?using?_Func ????_DEBUG_RANGE(_First,?_Last); ????_DEBUG_POINTER(_Func); ???? for?(;?_First?!=?_Last;?++_First) ????????_Val?=?_Func(_Val,?*_First); ???? return?(_Val); } template?<? class?_InIt, ????????? class?_Ty, ????????? class?_Fn2?>? inline _Ty?accumulate(_InIt?_First,?_InIt?_Last,?_Ty?_Val,?_Fn2?_Func) { ???? //?return?sum?of?_Val?and?all?in?[_First,?_Last),?using?_Func ???? return?_Accumulate(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Val,?_Func); } |
?
accumulate 重載了兩個(gè)版本，第一個(gè)版本實(shí)現(xiàn)的是累加，第二個(gè)版本帶_Func 參數(shù)，可以自定義計(jì)算，比如累乘等。代碼都比較好理解，就不贅述
了。看下面的示例代碼4：
?
C++ Code?| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | ? | #include?<iostream> #include?<vector> #include?<list> #include?<algorithm> #include?<numeric> using? namespace?std; void?print_element( int?n) { ????cout?<<?n?<<? '?'; } int?mult( int?a,? int?b) { ???? return?a?*?b; } int?main( void) { ???? int?a[]?=?{? 1,? 2,? 3,? 4,? 5?}; ????vector< int>?v(a,?a?+? 5); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ???? //?累加 ????cout?<<?accumulate(v.begin(),?v.end(),? 0)?<<?endl; ???? //?累乘 ????cout?<<?accumulate(v.begin(),?v.end(),? 1,?mult)?<<?endl; ???? return? 0; } |
?
?
?
參考：
C++ primer 第四版
Effective C++ 3rd
C++編程規(guī)范
?
總結(jié)
以上是生活随笔為你收集整理的从零开始学C++之STL（七）：剩下5种算法代码分析与使用示例（remove 、rotate 、sort、lower_bound、accumulate）...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 放弃winform的窗体吧，改用html
- 下一篇： 飘逸的python - hack输出流便