从零开始学C++之STL(七):剩下5种算法代码分析与使用示例(remove 、rotate 、sort、lower_bound、accumulate)

一、移除性算法 (remove)

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

如下图所示:

假设现在想要remove 的元素是3,则传入到 _Remove_copy 函数的3个参数如上图第一行所示,Val 即3。

接着遍历First ~ Last 区间的元素,将非移除元素拷贝到前面,覆盖前面的元素,最后的指向如图,函数返回的是Dest 位置,如下代

码所示:

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

if (!(*_First == _Val))

            *_Dest++ = *_First;

由上图可看出移除性算法并没有改变元素的个数,如果要真正删除,可以将remove 的返回值传入erase 进行删除,如:

v.erase(remove(v.begin(), v.end(), 3), v.end()); 即会将后面两个元素4 和 5 删除掉。

在这里顺便提一下,erase 会使当前迭代器失效,但可以返回下一个迭代器,故如果需要在遍历中删除,下面的做法才是正确的:

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    int a[] = {3, 1, 2, 3, 4};
    vector<int> v(a, a + 5);

    //for (vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
    //{
    //  if (*it == 3)
    //      v.erase(it);          ERROR!
    //  else
    //      cout<<*it<<' ';
    //}

    for (vector<int>::iterator it = v.begin(); it != v.end();)
    {
        if (*it == 3)
            it = v.erase(it);
        else
        {
            cout << *it << ' ';
            ++it;
        }
    }

    cout << endl;
    return 0;
}

示例代码1:

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

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 调用了_Rotate,实际上_Rotate 继续调用了某个函数,内部实现代码比较长,而且不容易看懂,这边可以看一下简易的等价

版本实现,来自这里,如下:

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

假设一个容器有 1 2 3 4 5 6 六个元素,现在想把 1 2 放到后面去,可以这样写 rotate(v.begin(), v.begin()+2, v.end());  如下图所示:

即将first 与 next 对应的元素互换且不断向前推进,直到first == next 为止。

三、排序算法 (sort)

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 重载了两个版本,第一个版本只有2个参数,默认按从小到大排序(using operator<);第二个版本有三个参数,即可以自定义比较逻辑

(_Pred)。它们都调用了标准库的std::_Sort, 跟踪进去发现比较复杂,在_Sort 内会根据一些条件选择不同的排序方式,如标准库的堆排序,合并

排序,插入排序等等。站在使用的角度看,没必要去深究,但如果是想学习相关的排序,那是很好的资源。

示例代码2:

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

此外,sort 有个坑,如果你自己传递比较逻辑,需要注意,如下:

四、已序区间算法 (lower_bound 、upper_bound)

使用这些算法的前提是区间已经是有序的。

// 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() 返回第一个“大于等于给定值" 的元素位置,其实还重载了另一个low_bound 版本,如下:

// 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 *)

也就是可以自定义比较逻辑,需要注意的是如果使用这个版本,那么区间应该本来就是按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.

由于是已序区间,所以函数内用的是二分查找,而两个版本主要的代码不同在于:

_DEBUG_LT(*_Mid, _Val)

_DEBUG_LT_PRED(_Pred, *_Mid, _Val)

upper_bound 与 lower_bound 类似,不过返回的是第一个”大于给定值“ 的元素位置。

示例代码3:

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

五、数值算法(accumulate)

// 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 重载了两个版本,第一个版本实现的是累加,第二个版本带_Func 参数,可以自定义计算,比如累乘等。代码都比较好理解,就不赘述

了。看下面的示例代码4:

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开源FPGA

基于basys2驱动LCDQC12864B的verilog设计图片显示

  话不多说先上图 ? 前言        在做这个实验的时候在网上找了许多资料,都是关于使用单片机驱动LCD显示,确实用单片机驱动是要简单不少,记得在FPGA...

2065
来自专栏积累沉淀

分享一个flash播放音乐的类

//定义数组 var myXML = new XML(); var mp3total = new Array(); var mp3name = new Arra...

1789
来自专栏何俊林

如何进行网络视频截图/获取视频的缩略图

小编导读:获取视频的缩略图,截图正在播放的视频某一帧,是在音视频开发中,常遇到的问题。本文是主要用于点播中截图视频,同时还可以获取点播视频的缩略图进行显示,留下...

5977
来自专栏生信技能树

GATK4的gvcf流程

得到了它们的bam文件,也是走的GATK流程,这里就不多说了。本教程首发于生信技能树VIP论坛:https://vip.biotrainee.com/d/423...

1673
来自专栏HT

玩转 HTML5 下 WebGL 的 3D 模型交并补

建设性的立体几何具有许多实际用途,它用于需要简单几何对象的情况下,或者数学精度很重要的地方,几乎所有的工程 CAD 软件包都使用 CSG(可以用于表示刀具切削,...

19210
来自专栏用户2442861的专栏

Python-OpenCV 处理图像(二):滤镜和图像运算

喜欢自拍的人肯定都知道滤镜了,下面代码尝试使用一些简单的滤镜,包括图片的平滑处理、灰度化、二值化等:

551
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[05-1]:进入 3D 世界,从正方体开始

a. 渲染管线的基础知识 《OpenGL ES 2.0 (iOS)[01]: 一步从一个小三角开始》

1143
来自专栏PPV课数据科学社区

R包之tm:文本挖掘包

简介 安装 数据输入—文集(corpus) 数据输出 查看语料库(corpora) 查看某几条信息 查看单个文档元数据 查看单个文档内容 查看多个文档内容 变换...

3718
来自专栏Android 开发者

ViewModel 和 LiveData:为设计模式打 Call 还是唱反调?

2403
来自专栏Pulsar-V

OpenCV-Mat与Base64之间的相互转换

PS:不得不吐槽一句这年头WebSocket转MAT这么复杂,C++后端都隐藏实力去了吗?

1052

扫码关注云+社区