从零开始学C++之STL(五):非变动性算法源代码分析与使用示例( for_each、min_element 、find_if、search 等)

非变动性算法代码分析与示例:

一、for_each

// TEMPLATE FUNCTION for_each
template < class _InIt,
         class _Fn1 > inline
_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
{
    // perform function for each element
    _DEBUG_RANGE(_First, _Last);
    _DEBUG_POINTER(_Func);
    _CHECKED_BASE_TYPE(_InIt) _ChkFirst(_CHECKED_BASE(_First));
    _CHECKED_BASE_TYPE(_InIt) _ChkLast(_CHECKED_BASE(_Last));
    for (; _ChkFirst != _ChkLast; ++_ChkFirst)
        _Func(*_ChkFirst);
    return (_Func);
}

函数以模板实现,_Inlt 即 iterator 类型,_Fn1 是函数指针,函数体内首先判断迭代器是否在范围内以及传递的第三个参数是否是函

数指针,接下去两行实际上就是定义两个临时的迭代器,相当于 _Inlt  ChkFirst(_First); 在遍历的过程中将每个容器元素取出并当作参

数传递给函数指针,即 _Func(*ChkFirst);  for_each 函数返回值是函数指针

二、max_element、min_element

两个函数实现差不多,只看min_element:

// TEMPLATE FUNCTION min_element
template<class _FwdIt> inline
_FwdIt _Min_element(_FwdIt _First, _FwdIt _Last)
{
    // find smallest element, using operator<
    _DEBUG_RANGE(_First, _Last);
    _FwdIt _Found = _First;
    if (_First != _Last)
        for (; ++_First != _Last; )
            if (_DEBUG_LT(*_First, *_Found))
                _Found = _First;
    return (_Found);
}

template<class _FwdIt> inline
_FwdIt min_element(_FwdIt _First, _FwdIt _Last)
{
    // find smallest element, using operator<
    _ASSIGN_FROM_BASE(_First,
                      _Min_element(_CHECKED_BASE(_First), _CHECKED_BASE(_Last)));
    return (_First);
}

首先  #define _ASSIGN_FROM_BASE(_Dest, _Src)  _Dest = (_Src) 即将_Min_element 函数的返回值复制给_First,而在

_Min_element 函数内就是遍历容器,不断保存最小元素的位置,其中 #define _DEBUG_LT(x, y) ((x) < (y))   故

_DEBUG_LT(*_First, *_Found) 也就是取出元素比较大小,返回最后保存的最小元素位置。

实际上min_element 还重载了另一个函数模板:

template < class _FwdIt,
         class _Pr > inline
_FwdIt _Min_element(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
{
    // find smallest element, using _Pred
    _DEBUG_RANGE(_First, _Last);
    _DEBUG_POINTER(_Pred);
    _FwdIt _Found = _First;
    if (_First != _Last)
        for (; ++_First != _Last; )
            if (_DEBUG_LT_PRED(_Pred, *_First, *_Found))
                _Found = _First;
    return (_Found);
}

template < class _FwdIt,
         class _Pr > inline
_FwdIt min_element(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
{
    // find smallest element, using _Pred
    _ASSIGN_FROM_BASE(_First,
                      _Min_element(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred));
    return (_First);
}

主要的区别只是在于这个版本可以自定义进行比较,比如如果容器内不是装着数值元素,而是string 或者其他类型,也许它们没有重

载 operator<,可以自定义一个函数对它们进行比较大小,如 #define _DEBUG_LT_PRED(pred, x, y) pred(x, y) 就是这个意思。

三、find、find_if

// TEMPLATE FUNCTION find
template<class _InIt, class _Ty>
inline
_InIt _Find(_InIt _First, _InIt _Last, const _Ty &_Val)
{
    // find first matching _Val
    _DEBUG_RANGE(_First, _Last);
    for (; _First != _Last; ++_First)
        if (*_First == _Val)
            break;
    return (_First);
}

template<class _InIt, class _Ty>
inline
_InIt find(_InIt _First, _InIt _Last, const _Ty &_Val)
{
    // find first matching _Val
    _ASSIGN_FROM_BASE(_First,
                      _Find(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Val));
    return (_First);
}

// TEMPLATE FUNCTION find_if
template < class _InIt,
         class _Pr > inline
_InIt _Find_if(_InIt _First, _InIt _Last, _Pr _Pred)
{
    // find first satisfying _Pred
    _DEBUG_RANGE(_First, _Last);
    _DEBUG_POINTER(_Pred);
    for (; _First != _Last; ++_First)
        if (_Pred(*_First))
            break;
    return (_First);
}

template < class _InIt,
         class _Pr > inline
_InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)
{
    // find first satisfying _Pred
    _ASSIGN_FROM_BASE(_First,
                      _Find_if(_CHECKED_BASE(_First), _CHECKED_BASE(_Last), _Pred));
    return (_First);
}

里面很多宏跟前面函数出现的是一样的,find 就是遍历容器,找出与Val 相等的第一个元素位置,函数返回迭代器 。

find_if 则可以自定义查找,不一定是与某值相等,也可以其他比较如大于小于等,如 if (_Pred(*_First))  如果_Pred 函数返回为真

则break,至于_Pred 怎样实现就不关find_if 的事了。

示例代码1:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void print_element(int n)
{
    cout << n << ' ';
}

bool greater_than_3(int n)
{
    return n > 3;
}

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

    vector<int>::const_iterator it;
    for (it = v.begin(); it != v.end(); ++it)
        cout << *it << ' ';
    cout << endl;

    for_each(v.begin(), v.end(), print_element);
    cout << endl;

    for (it = v.begin(); it != v.end(); ++it)
        cout << *it << ' ';
    cout << endl;

    it = min_element(v.begin(), v.end());
    if (it != v.end())
    {
        cout << *it << endl;
    }

    it = max_element(v.begin(), v.end());
    if (it != v.end())
    {
        cout << *it << endl;
    }

    it = find(v.begin(), v.end(), 3);
    if (it != v.end())
    {
        cout << it - v.begin() << endl;
    }
    else
        cout << "not found" << endl;

    it = find_if(v.begin(), v.end(), greater_than_3);
    if (it != v.end())
    {
        cout << it - v.begin() << endl;
    }
    else
        cout << "not found" << endl;

    return 0;
}

四、search

// TEMPLATE FUNCTION search
template < class _FwdIt1,
         class _FwdIt2,
         class _Diff1,
         class _Diff2 > inline
_FwdIt1 _Search(_FwdIt1 _First1, _FwdIt1 _Last1,
                _FwdIt2 _First2, _FwdIt2 _Last2, _Diff1 *, _Diff2 *)
{
    // find first [_First2, _Last2) match
    _DEBUG_RANGE(_First1, _Last1);
    _DEBUG_RANGE(_First2, _Last2);
    _Diff1 _Count1 = 0;
    _Distance(_First1, _Last1, _Count1);
    _Diff2 _Count2 = 0;
    _Distance(_First2, _Last2, _Count2);

    for (; _Count2 <= _Count1; ++_First1, --_Count1)
    {
        // room for match, try it
        _FwdIt1 _Mid1 = _First1;
        for (_FwdIt2 _Mid2 = _First2; ; ++_Mid1, ++_Mid2)
            if (_Mid2 == _Last2)
                return (_First1);
            else if (!(*_Mid1 == *_Mid2))
                break;
    }
    return (_Last1);
}

template < class _FwdIt1,
         class _FwdIt2 > inline
_FwdIt1 search(_FwdIt1 _First1, _FwdIt1 _Last1,
               _FwdIt2 _First2, _FwdIt2 _Last2)
{
    // find first [_First2, _Last2) match
    _ASSIGN_FROM_BASE(_First1,
                      _Search(_CHECKED_BASE(_First1), _CHECKED_BASE(_Last1),
                              _CHECKED_BASE(_First2), _CHECKED_BASE(_Last2),
                              _Dist_type(_First1), _Dist_type(_First2)));
    return _First1;
}

函数传入4个迭代器,假设前两个迭代器指示的位置有10个元素,后两个迭代器指示的位置有2个元素,如果在第一个区间能够找到

完全匹配第二个区间的元素,则返回起始位置,如果不能则返回Last1,即第一个区间末尾,注意必须顺序匹配2个元素,也可以看

成在第一个区间寻找第一次出现的第二个区间子段。

函数的实现也不难理解,双重循环,比如首先比较L1[0] 与 L2[0] , 如果相等再比较L1[1] 与 L2[1]; 如果不等则移动,从L1[1] 开始比

较,假设L1[4], L1[5] 与L2[0], L2[1] 完全匹配,则返回值是指向L1[4] 的 iterator。

此外seach 也重载了另一个版本,可以自定义比较,代码比较长且跟上面重复较多就不贴了,主要的变化就是将上面24行的代码

换成 else if (!_Pred(*_Mid1, *_Mid2)) 也就是自定义比较逻辑。

下面贴一个MSDN 的例子:

// alg_search.cpp
// compile with: /EHsc
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>

// Return whether second element is twice the first
bool twice (int elem1, int elem2 )
{
    return 2 * elem1 == elem2;
}

int main( )
{
    using namespace std;
    vector <int> v1, v2;
    list <int> L1;
    vector <int>::iterator Iter1, Iter2;
    list <int>::iterator L1_Iter, L1_inIter;

    int i;
    for ( i = 0 ; i <= 5 ; i++ )
    {
        v1.push_back( 5 * i );
    }
    for ( i = 0 ; i <= 5 ; i++ )
    {
        v1.push_back( 5 * i );
    }

    int ii;
    for ( ii = 4 ; ii <= 5 ; ii++ )
    {
        L1.push_back( 5 * ii );
    }

    int iii;
    for ( iii = 2 ; iii <= 4 ; iii++ )
    {
        v2.push_back( 10 * iii );
    }

    cout << "Vector v1 = ( " ;
    for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
        cout << *Iter1 << " ";
    cout << ")" << endl;

    cout << "List L1 = ( " ;
    for ( L1_Iter = L1.begin( ) ; L1_Iter != L1.end( ) ; L1_Iter++ )
        cout << *L1_Iter << " ";
    cout << ")" << endl;

    cout << "Vector v2 = ( " ;
    for ( Iter2 = v2.begin( ) ; Iter2 != v2.end( ) ; Iter2++ )
        cout << *Iter2 << " ";
    cout << ")" << endl;

    // Searching v1 for first match to L1 under identity
    vector <int>::iterator result1;
    result1 = search (v1.begin( ), v1.end( ), L1.begin( ), L1.end( ) );

    if ( result1 == v1.end( ) )
        cout << "There is no match of L1 in v1."
             << endl;
    else
        cout << "There is at least one match of L1 in v1"
             << "\n and the first one begins at "
             << "position " << result1 - v1.begin( ) << "." << endl;

    // Searching v1 for a match to v2 under the binary predicate twice
    vector <int>::iterator result2;
    result2 = search  (v1.begin( ), v1.end( ), v2.begin( ), v2.end( ), twice );

    if ( result2 == v1.end( ) )
        cout << "There is no match of L1 in v1."
             << endl;
    else
        cout << "There is a sequence of elements in v1 that "
             << "are equivalent\n to those in v2 under the binary "
             << "predicate twice\n and the first one begins at position "
             << result2 - v1.begin( ) << "." << endl;
}

/*
Vector v1 = ( 0 5 10 15 20 25 0 5 10 15 20 25 )
List L1 = ( 20 25 )
Vector v2 = ( 20 30 40 )
There is at least one match of L1 in v1
and the first one begins at position 4.
There is a sequence of elements in v1 that are equivalent
to those in v2 under the binary predicate twice
and the first one begins at position 2.
*/

参考:

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python数据科学

使用Pandas&NumPy进行数据清洗的6大常用方法

数据科学家花了大量的时间清洗数据集,并将这些数据转换为他们可以处理的格式。事实上,很多数据科学家声称开始获取和清洗数据的工作量要占整个工作的80%。

1512
来自专栏Java架构沉思录

什么是一致性哈希算法

原文:http://www.cnblogs.com/hapjin/p/4737207.html

851
来自专栏WindCoder

最大流量和线性分配问题

这里有一个问题:你的业务分配给承包商来履行合同。您可以浏览您的名单,并决定哪些承包商可以参与一个月的合同,你可以查看你的合同,看看哪些合同是一个月的任务。鉴于你...

852
来自专栏飞雪无情的博客

Go语言性能优化- For Range 性能研究

如果我们要遍历某个数组,Map集合,Slice切片等,Go语言(Golang)为我们提供了比较好用的For Range方式。range是一个关键字,表示范围,和...

882
来自专栏WebDeveloper

sass的高级用法

进入到Koala 安装目录 D:\Koala\rubygems\gems\sass-3.4.9\lib\sass修改 engine.rb 文件 在requir...

602
来自专栏owent

HDU HDOJ 3398 String 解题报告

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3398

673
来自专栏ACM算法日常

确定比赛名次(拓扑排序) - HDU 1285

这次先讲理论,因为拓扑排序在日常工作中用的并不多,甚至于很多人可能忘了计算机中存在这样一种排序。我大概的整理一下拓扑排序的定义和应用,以便看了这...

712
来自专栏生信技能树

在R里面玩转vcf文件

其中meta存储着vcf的头文件,而fix存储在vcf的固定列,gt存储在样本基因型信息。

643
来自专栏zaking's

js算法初窥07(算法复杂度)

1023
来自专栏潇涧技术专栏

Python Algorithms - C2 The basics

本节主要介绍了三个内容:算法渐近运行时间的表示方法、六条算法性能评估的经验以及Python中树和图的实现方式。

852

扫码关注云+社区