从零开始学C++之STL（六）：变动性算法源代码分析与使用示例（copy_backward、 transform、 replace_copy_if 等）

aspnetwinform

浏览: 85074 次
性别:
来自: 武汉

最近访客更多访客>>

380071587

zc690739629

standalone

wuyue

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

首先回顾前面的文章，我们把for_each 归类为非变动性算法，实际上它也可以算是变动性算法，取决于传入的第三个参数，即函数

指针。如果在函数内对容器元素做了修改，那么就属于变动性算法。

变动性算法源代码分析与使用示例：

一、copy、copy_backward

C++ Code

//TEMPLATEFUNCTIONcopy
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,...),arbitraryiterators
_DEBUG_RANGE(_First,_Last);
for(;_First!=_Last;++_Dest,++_First)
*_Dest=*_First;
return(_Dest);
}

template<class_InIt,class_OutIt>
inline
_IF_CHK(_OutIt)__CLRCALL_OR_CDECLcopy(_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()));
}

//TEMPLATEFUNCTIONcopy_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)backwardsto[...,_Dest),arbitraryiterators
_DEBUG_RANGE(_First,_Last);
while(_First!=_Last)
*--_Dest=*--_Last;
return(_Dest);
}

template<class_BidIt1,
class_BidIt2>inline
_IF_CHK(_BidIt2)__CLRCALL_OR_CDECLcopy_backward(_BidIt1_First,_BidIt1_Last,_BidIt2_Dest)
{
//copy[_First,_Last)backwardsto[...,_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());
}

copy 调用了_Copy_opt，在此函数内递增迭代器，从前两个参数指定的区间内取出元素并拷贝到对应_Dest位置上。

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

*_Dest=*_First;

copy_backward 调用了_Copy_backward_opt，与copy 不同的是实现反向拷贝，即从尾端开始拷贝，所以是递减迭代器。

while(_First!=_Last)

*--_Dest=*--_Last;

示例代码1：

C++ Code

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
usingnamespacestd;

voidprint_element(intn)
{
cout<<n<<'';
}

voidadd_3(int&n)
{
n+=3;
}

intmain(void)
{
inta[]={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;

return0;
}

二、transfrom

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 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

//TEMPLATEFUNCTIONtransformWITHUNARYOP
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());
}

//TEMPLATEFUNCTIONtransformWITHBINARYOP
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
//forrangecheckediterators,thiswillmakesurethereisenoughspace
_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：

C++ Code

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
usingnamespacestd;

voidprint_element(intn)
{
cout<<n<<'';
}

intfun(inta)
{
return2*a;
}

intfun2(inta,intb)
{
returna+b;
}

intmain(void)
{
inta[]={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;

return0;
}

输出为：

2 4 6 8 10

5 7

三、replace、replace_copy、replace_copy_if

C++ Code

//TEMPLATEFUNCTIONreplace
template<class_FwdIt,
class_Ty>inline
void_Replace(_FwdIt_First,_FwdIt_Last,
const_Ty&_Oldval,const_Ty&_Newval)
{
//replaceeachmatching_Oldvalwith_Newval
_DEBUG_RANGE(_First,_Last);
for(;_First!=_Last;++_First)
if(*_First==_Oldval)
*_First=_Newval;
}

template<class_FwdIt,
class_Ty>inline
voidreplace(_FwdIt_First,_FwdIt_Last,
const_Ty&_Oldval,const_Ty&_Newval)
{
//replaceeachmatching_Oldvalwith_Newval
_Replace(_CHECKED_BASE(_First),_CHECKED_BASE(_Last),_Oldval,_Newval);
}

//TEMPLATEFUNCTIONreplace_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)
{
//copyreplacingeachmatching_Oldvalwith_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)
{
//copyreplacingeachmatching_Oldvalwith_Newval
return_Replace_copy(_CHECKED_BASE(_First),_CHECKED_BASE(_Last),_Dest,_Oldval,_Newval,
_Iter_random(_First,_Dest),_STD_Range_checked_iterator_tag());
}

//TEMPLATEFUNCTIONreplace_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)
{
//copyreplacingeachsatisfying_Predwith_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)
{
//copyreplacingeachsatisfying_Predwith_Val
return_Replace_copy_if(_CHECKED_BASE(_First),_CHECKED_BASE(_Last),_Dest,_Pred,_Val,
_Iter_random(_First,_Dest),_STD_Range_checked_iterator_tag());
}

replace 带4个参数，将前两个参数指示的区间元素值为_Oldval 的替换成_Newval。

if(*_First==_Oldval)

*_First=_Newval;

replace_copy 带5个参数，先将前两个参数指示区间的元素都拷贝到第三个参数指示的区间上，再判断是否执行replace。

*_Dest=*_First==_Oldval?_Newval:*_First; 每个元素拷贝后，判断是_Oldval 则替换，否则还是原值。

replace_copy_if 带5个参数，在每个元素拷贝时先判断是否满足条件（函数返回为真），满足则替换成_Val，否则保持不变。

*_Dest=_Pred(*_First)?_Val:*_First;

示例代码3：

C++ Code

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
usingnamespacestd;

voidprint_element(intn)
{
cout<<n<<'';
}

boolfun(inta)
{
returna<10;
}

intmain(void)
{
inta[]={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;

return0;
}

输出为：

1 2 13 4 13

1 2 3 4 3

0 0 13 0 13

参考：

C++ primer 第四版
Effective C++ 3rd
C++编程规范

分享到：

Hibernate从入门到精通（九）一对多双向关 ... | 31天重构学习笔记重新整理下载

2013-07-25 16:55
浏览 569
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论