变动性算法源代码分析与使用示例（copy_backward、 transform、 replace_copy_if 等）

SimonSsAlgo

2018-02-26

关注关注

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

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

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

一、copy、copy_backward

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

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

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

*_Dest=*_First;

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

while(_First!=_Last)

*--_Dest=*--_Last;

示例代码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
31
32
33
34
35
36
37
38
39
40
41
42
43

#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;
}

变动性算法源代码分析与使用示例（copy_backward、 transform、 replace_copy_if 等）

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

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

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

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

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;

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

#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++编程规范

transform

安科网

变动性算法源代码分析与使用示例（copy_backward、 transform、 replace_copy_if 等）

SimonSsAlgo

SimonSsAlgo

相关推荐

怎么让Chrome支持小于12px 的文字？

CSS通过text-transform实现大写、小写和首字母大写转换

CSS变形、动画实现的旋转魔方

bootstrap div垂直居中+水平居中保持响应式

css 变形（transform）

2D and 3D

CSS3动画属性有哪些

css3的动画属性

5.5 CSS3 transform变换

CSS3 制作立方体（个人疑惑点解读）

不使用字体图标和图片，只使用css如何做出展开收起的效果

css 纯css轮播图示例

有关css编写文字动态下划线

CSS3(3)---2D变形(transform)

CSS3(3)---2D变形(transform)

好吧，CSS3 3D transform变换，不过如此！

css样式书写顺序

css应用视觉设计

研究一个动画相册送给女朋友吧

css学习4

SimonSsAlgo