首先回顧前面的文章,我們把for_each 歸類為非變動性算法,實際上它也可以算是變動性算法,取決于傳入的第三個參數,即函數
指針。如果在函數內對容器元素做了修改,那么就屬于變動性算法。
變動性算法源代碼分析與使用示例:
一、copy、copy_backward
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 | ? | //?TEMPLATE?FUNCTION?copy template<class?_InIt,?class?_OutIt,?class?_InOutItCat> inline _OutIt?__CLRCALL_OR_CDECL?_Copy_opt(_InIt?_First,?_InIt?_Last,?_OutIt?_Dest, ????????????????????????????????????_InOutItCat,?_Nonscalar_ptr_iterator_tag,?_Range_checked_iterator_tag) { ????//?copy?[_First,?_Last)?to?[_Dest,?...),?arbitrary?iterators ????_DEBUG_RANGE(_First,?_Last); ????for?(;?_First?!=?_Last;?++_Dest,?++_First) ????????*_Dest?=?*_First; ????return?(_Dest); } template<class?_InIt,?class?_OutIt> inline _IF_CHK(_OutIt)?__CLRCALL_OR_CDECL?copy(_InIt?_First,?_InIt?_Last,?_OutIt?_Dest) { ????//?copy?[_First,?_Last)?to?[_Dest,?...) ????return?(_Copy_opt(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Dest, ??????????????????????_Iter_random(_First,?_Dest),?_Ptr_cat(_First,?_Dest),?_Range_checked_iterator_tag())); } //?TEMPLATE?FUNCTION?copy_backward template<class?_BidIt1,?class?_BidIt2,?class?_InOutItCat> inline _BidIt2?__CLRCALL_OR_CDECL?_Copy_backward_opt(_BidIt1?_First,?_BidIt1?_Last,?_BidIt2?_Dest, ????????_InOutItCat,?_Nonscalar_ptr_iterator_tag,?_Range_checked_iterator_tag) { ????//?copy?[_First,?_Last)?backwards?to?[...,?_Dest),?arbitrary?iterators ????_DEBUG_RANGE(_First,?_Last); ????while?(_First?!=?_Last) ????????*--_Dest?=?*--_Last; ????return?(_Dest); } template?<?class?_BidIt1, ?????????class?_BidIt2?>?inline _IF_CHK(_BidIt2)?__CLRCALL_OR_CDECL?copy_backward(_BidIt1?_First,?_BidIt1?_Last,?_BidIt2?_Dest) { ????//?copy?[_First,?_Last)?backwards?to?[...,?_Dest) ????return?_Copy_backward_opt(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Dest, ??????????????????????????????_Iter_random(_First,?_Dest),?_Ptr_cat(_First,?_Dest),?_STD?_Range_checked_iterator_tag()); } |
?
for?(;?_First?!=?_Last;?++_Dest,?++_First)
????????*_Dest?=?*_First;
copy_backward 調用了_Copy_backward_opt,與copy 不同的是實現反向拷貝,即從尾端開始拷貝,所以是遞減迭代器。
while?(_First?!=?_Last)
????????*--_Dest?=?*--_Last;
示例代碼1:
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 | ? | #include?<iostream> #include?<vector> #include?<list> #include?<algorithm> using?namespace?std; void?print_element(int?n) { ????cout?<<?n?<<?'?'; } void?add_3(int?&n) { ????n?+=?3; } int?main(void) { ????int?a[]?=?{?1,?2,?3,?4,?5?}; ????vector<int>?v(a,?a?+?5); ????list<int>?l(15); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ????for_each(v.begin(),?v.end(),?add_3); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ????for_each(l.begin(),?l.end(),?print_element); ????cout?<<?endl; ????copy(v.begin(),?v.end(),?l.begin()); ????for_each(l.begin(),?l.end(),?print_element); ????cout?<<?endl; ????copy_backward(v.begin(),?v.end(),?l.end()); ????for_each(l.begin(),?l.end(),?print_element); ????cout?<<?endl; ????return?0; } |
二、transfrom
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | ? | //?TEMPLATE?FUNCTION?transform?WITH?UNARY?OP template<class?_InIt,?class?_OutIt,?class?_Fn1,?class?_InOutItCat> inline _OutIt?_Transform(_InIt?_First,?_InIt?_Last,?_OutIt?_Dest,?_Fn1?_Func, ??????????????????_InOutItCat,?_Range_checked_iterator_tag) { ????//?transform?[_First,?_Last)?with?_Func ????_DEBUG_RANGE(_First,?_Last); ????_DEBUG_POINTER(_Dest); ????_DEBUG_POINTER(_Func); ????for?(;?_First?!=?_Last;?++_First,?++_Dest) ????????*_Dest?=?_Func(*_First); ????return?(_Dest); } template<class?_InIt,?class?_OutIt,?class?_Fn1> inline _IF_CHK(_OutIt)?transform(_InIt?_First,?_InIt?_Last,?_OutIt?_Dest,?_Fn1?_Func) { ????return?_Transform(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Dest,?_Func, ??????????????????????_Iter_random(_First,?_Dest),?_STD?_Range_checked_iterator_tag()); } //?TEMPLATE?FUNCTION?transform?WITH?BINARY?OP template<class?_InIt1,?class?_InIt2,?class?_OutIt,?class?_Fn2,?class?_InItCats,?class?_InOutItCat> inline _OutIt?_Transform(_InIt1?_First1,?_InIt1?_Last1,?_InIt2?_First2, ??????????????????_OutIt?_Dest,?_Fn2?_Func, ??????????????????_InItCats,?_InOutItCat, ??????????????????_Range_checked_iterator_tag,?_Range_checked_iterator_tag) { ????//?transform?[_First1,?_Last1)?and?[_First2,?_Last2)?with?_Func ????_DEBUG_RANGE(_First1,?_Last1); ????_DEBUG_POINTER(_Dest); ????_DEBUG_POINTER(_Func); ????for?(;?_First1?!=?_Last1;?++_First1,?++_First2,?++_Dest) ????????*_Dest?=?_Func(*_First1,?*_First2); ????return?(_Dest); } template<class?_InIt1,?class?_InIt2,?class?_OutIt,?class?_Fn2,?class?_InOutItCat> inline _OutIt?_Transform(_InIt1?_First1,?_InIt1?_Last1,?_InIt2?_First2, ??????????????????_OutIt?_Dest,?_Fn2?_Func, ??????????????????random_access_iterator_tag,?_InOutItCat, ??????????????????_Range_checked_iterator_tag,?_Range_checked_iterator_tag) { ????//?transform?[_First1,?_Last1)?and?[_First2,?_Last2)?with?_Func ????//?for?range?checked?iterators,?this?will?make?sure?there?is?enough?space ????_InIt2?_Last2?=?_First2?+?(_Last1?-?_First1); ????(_Last2); ????return?_Transform(_First1,?_Last1,?_CHECKED_BASE(_First2), ??????????????????????_Dest,?_Func, ??????????????????????forward_iterator_tag(),?forward_iterator_tag(), ??????????????????????_Range_checked_iterator_tag(),?_Range_checked_iterator_tag()); } template<class?_InIt1,?class?_InIt2,?class?_OutIt,?class?_Fn2> inline _IF_CHK2_(_InIt2,?_OutIt,?_OutIt)?transform(_InIt1?_First1,?_InIt1?_Last1,?_InIt2?_First2, ????????_OutIt?_Dest,?_Fn2?_Func) { ????return?_Transform(_CHECKED_BASE(_First1),?_CHECKED_BASE(_Last1),?_First2,?_Dest,?_Func, ??????????????????????_Iter_random(_First1,?_First2),?_Iter_random(_First1,?_Dest), ??????????????????????_STD?_Range_checked_iterator_tag(),?_STD?_Range_checked_iterator_tag()); } |
實際上transfrom 重載了兩個版本,一個是四個參數的,即將前兩個參數指定區間內的元素執行某種操作(函數內)后拷貝到第三個
參數指示的區間上。而另一個版本是五個參數的,即將兩個區間的對應元素進行某種操作后拷貝到第三個區間上去。核心的代碼區
別在于下面兩行:
*_Dest = _Func(*_First);
*_Dest = _Func(*_First1, *_First2);
示例代碼2:
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 | ? | #include?<iostream> #include?<vector> #include?<list> #include?<algorithm> using?namespace?std; void?print_element(int?n) { ????cout?<<?n?<<?'?'; } int?fun(int?a) { ????return?2?*?a; } int?fun2(int?a,?int?b) { ????return?a?+?b; } int?main(void) { ????int?a[]?=?{?1,?2,?3,?4,?5?}; ????vector<int>?v(a,?a?+?5); ????list<int>?l(5); ????list<int>?ll(2); ????transform(v.begin(),?v.end(),?l.begin(),?fun); ????for_each(l.begin(),?l.end(),?print_element); ????cout?<<?endl; ????transform(v.begin(),?v.begin()?+?2,?v.begin()?+?3,?ll.begin(),?fun2); ????for_each(ll.begin(),?ll.end(),?print_element); ????cout?<<?endl; ????return?0; } |
輸出為 :
2 4 6 8 10
5 7
三、replace、replace_copy、replace_copy_if
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | ? | //?TEMPLATE?FUNCTION?replace template?<?class?_FwdIt, ?????????class?_Ty?>?inline void?_Replace(_FwdIt?_First,?_FwdIt?_Last, ??????????????const?_Ty?&_Oldval,?const?_Ty?&_Newval) { ????//?replace?each?matching?_Oldval?with?_Newval ????_DEBUG_RANGE(_First,?_Last); ????for?(;?_First?!=?_Last;?++_First) ????????if?(*_First?==?_Oldval) ????????????*_First?=?_Newval; } template?<?class?_FwdIt, ?????????class?_Ty?>?inline void?replace(_FwdIt?_First,?_FwdIt?_Last, ?????????????const?_Ty?&_Oldval,?const?_Ty?&_Newval) { ????//?replace?each?matching?_Oldval?with?_Newval ????_Replace(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Oldval,?_Newval); } //?TEMPLATE?FUNCTION?replace_copy template<class?_InIt,?class?_OutIt,?class?_Ty,?class?_InOutItCat> inline _OutIt?_Replace_copy(_InIt?_First,?_InIt?_Last,?_OutIt?_Dest, ?????????????????????const?_Ty?&_Oldval,?const?_Ty?&_Newval, ?????????????????????_InOutItCat,?_Range_checked_iterator_tag) { ????//?copy?replacing?each?matching?_Oldval?with?_Newval ????_DEBUG_RANGE(_First,?_Last); ????_DEBUG_POINTER(_Dest); ????for?(;?_First?!=?_Last;?++_First,?++_Dest) ????????*_Dest?=?*_First?==?_Oldval???_Newval?:?*_First; ????return?(_Dest); } template?<?class?_InIt, ?????????class?_OutIt, ?????????class?_Ty?>?inline _IF_CHK(_OutIt)?replace_copy(_InIt?_First,?_InIt?_Last,?_OutIt?_Dest, ?????????????????????????????const?_Ty?&_Oldval,?const?_Ty?&_Newval) { ????//?copy?replacing?each?matching?_Oldval?with?_Newval ????return?_Replace_copy(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Dest,?_Oldval,?_Newval, ?????????????????????????_Iter_random(_First,?_Dest),?_STD?_Range_checked_iterator_tag()); } //?TEMPLATE?FUNCTION?replace_copy_if template<class?_InIt,?class?_OutIt,?class?_Pr,?class?_Ty,?class?_InOutItCat> inline _OutIt?_Replace_copy_if(_InIt?_First,?_InIt?_Last,?_OutIt?_Dest, ????????????????????????_Pr?_Pred,?const?_Ty?&_Val,?_InOutItCat,?_Range_checked_iterator_tag) { ????//?copy?replacing?each?satisfying?_Pred?with?_Val ????_DEBUG_RANGE(_First,?_Last); ????_DEBUG_POINTER(_Dest); ????_DEBUG_POINTER(_Pred); ????for?(;?_First?!=?_Last;?++_First,?++_Dest) ????????*_Dest?=?_Pred(*_First)???_Val?:?*_First; ????return?(_Dest); } template?<?class?_InIt, ?????????class?_OutIt, ?????????class?_Pr, ?????????class?_Ty?>?inline _IF_CHK(_OutIt)?replace_copy_if(_InIt?_First,?_InIt?_Last,?_OutIt?_Dest, ????????????????????????????????_Pr?_Pred,?const?_Ty?&_Val) { ????//?copy?replacing?each?satisfying?_Pred?with?_Val ????return?_Replace_copy_if(_CHECKED_BASE(_First),?_CHECKED_BASE(_Last),?_Dest,?_Pred,?_Val, ????????????????????????????_Iter_random(_First,?_Dest),?_STD?_Range_checked_iterator_tag()); } |
if?(*_First?==?_Oldval)
????????????*_First?=?_Newval;
replace_copy 帶5個參數,先判斷前兩個參數指示區間的元素是否是_Oldval,若是則替換成_Newval 賦值到第三個參數指示的區間上,否則直接賦值
*_Dest?=?*_First?==?_Oldval???_Newval?:?*_First; ?
replace_copy_if 帶5個參數,在每個元素拷貝時先判斷是否滿足條件(函數返回為真),滿足則替換成_Val,否則保持不變。
*_Dest?=?_Pred(*_First)???_Val?:?*_First;
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 | ? | #include?<iostream> #include?<vector> #include?<list> #include?<algorithm> using?namespace?std; void?print_element(int?n) { ????cout?<<?n?<<?'?'; } bool?fun(int?a) { ????return?a?<?10; } int?main(void) { ????int?a[]?=?{?1,?2,?3,?4,?3?}; ????vector<int>?v(a,?a?+?5); ????list<int>?l(5); ????replace(v.begin(),?v.end(),?3,?13); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ????replace_copy(v.begin(),?v.end(),?l.begin(),?13,?3); ????for_each(v.begin(),?v.end(),?print_element); ????cout?<<?endl; ????for_each(l.begin(),?l.end(),?print_element); ????cout?<<?endl; ????replace_copy_if(v.begin(),?v.end(),?l.begin(),?fun,?0); ????for_each(l.begin(),?l.end(),?print_element); ????cout?<<?endl; ????return?0; } |
輸出為:
1 2 13 4 13
1 2 13 4 13
1 2 ?3 ?4 ?3
0 0 13 0 13
參考:
C++ primer 第四版
Effective C++ 3rd
C++編程規范