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

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

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

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

一、copy、copy_backward

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

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

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

        *_Dest = *_First;

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

while (_First != _Last)

        *--_Dest = *--_Last;

示例代码1:

#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

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

#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

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

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

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;

示例代码3:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张俊红

泰坦尼克号幸存率研究

总第53篇 代码区域 import pandas as pd import numpy as np import matplotlib import matpl...

2529
来自专栏汪毅雄的专栏

Android 7.0 中 Service bind 流程详解

我们知道,Android 启动 Service 有两种方式,startService 和 bindService。本文主要讲述Service bind 过程的最...

9801
来自专栏流媒体

App进程启动流程

在上一节Activity的启动流程中,当app进程不存在(第一次启动)时,会先去创建进程。这里我们通过源码来解读app进程的启动流程。

1014
来自专栏Jed的技术阶梯

图解 JVM GC 过程

假设现在Heap内存大小为20M,其中年轻代为10M,老年代为10M,年轻代中Eden区6M,From区2M,To区2M,新创建的对象首先往Eden区分配,当再...

553
来自专栏java闲聊

Jstat命令详解-1.8

https://blog.csdn.net/u011202334/article/details/51498108

1322
来自专栏前端那些事

递归函数-汉诺塔经典递归

前言 最近在读《JavaScript语言精粹》,对递归函数有了进一步的认识,希望总结下来: 递归是一种强大的编程技术,他把一个问题分解为一组相似的子问题,每一问...

2007
来自专栏无题

GC优化案例1:Major GC和Minor GC频繁

对GC优化的案例进行的系列总结(一): GC优化案例1:Major GC和Minor GC频繁 确定目标 服务情况:Minor GC每分钟100次 ,Majo...

3266
来自专栏编程心路

Java虚拟机内存管理(五)-垃圾收集器

不同版本的 JDK 选择的垃圾收集器也可能不同,我们在命令行查看安装的 JDK 的默认垃圾收集器,我这里是在 Windows 的 cmd 中输入 java -X...

482
来自专栏ImportSource

读懂一行Full GC日志(回复JVM内存分配担保机制一文中 Mr/Mrs Xxx 在留言区提出的问题)

回复JVM内存分配担保机制一文中 Mr/Mrs Xxx 在留言区提出的问题: “请问分配3M的时候,怎么还发生了full gc?” 回复如下: 发生Full ...

5697
来自专栏企鹅号快讯

掌握这8步快速进阶java编程

Java作为一种通用的编程语言可以做很多事情,但怎么学Java就看怎么用了,很多初学者想通过埋头苦学、马不停蹄的敲着代码记住Java基本原理,但一遇到困难便会让...

1915

扫码关注云+社区