从零开始学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 条评论
登录 后参与评论

相关文章

来自专栏葡萄城控件技术团队

如何在保留装箱对象的前提下修改值

有人问如何在保留装箱对象的前提下修改值? 场景: object obj = 100; Console.WriteLine("original object va...

1897
来自专栏Windows Community

Extensions in UWP Community Toolkit - ListViewExtensions

概述 UWP Community Toolkit Extensions 中有一个为 ListView 提供的扩展 - ListViewExtensions,本篇...

3176
来自专栏张善友的专栏

ASP.NET SignalR HubPipelineModule

ASP.NET SignalR 1.0 实现的一个特性HubPipeline -实现任何消息incoming和outgoing的拦截。SignalR HubPi...

1797
来自专栏大内老A

WCF后续之旅(10): 通过WCF Extension实现以对象池的方式创建Service Instance

我们知道WCF有3种典型的对service instance进行实例化的方式,他们分别与WCF的三种InstanceContextMode相匹配,他们分别是Pe...

1768
来自专栏函数式编程语言及工具

泛函编程(10)-异常处理-Either

     上节我们介绍了新的数据类型Option:一个专门对付异常情况出现时可以有一致反应所使用的数据类型。Option可以使编程人员不必理会出现异常后应该如何...

1815
来自专栏程序员的SOD蜜

.net访问PostgreSQL数据库发生“找不到函数名”的问题追踪

    PostgreSQL是一个使用广泛的免费开源的数据库,与MySQL比较,它更适合复杂的企业计算任务,而MySQL在互联网领域应用更为广泛,究其原因,可能...

2727
来自专栏陈仁松博客

UWP基础教程 - XAML开篇

XAML是英文Extensible Application Markup Language的缩写,中文可以称为“可扩展应用程序标记语言”,是基于Extensiv...

3628
来自专栏nummy

IPython简要入门

IPython增强了python自带的Console的功能,下面的语法只在IPython中有效。

562
来自专栏LEo的网络日志

python技巧分享(十三)

1313
来自专栏睿哥杂货铺

动态追踪技术(四):基于 Linux bcc/BPF 实现 Go 程序动态追踪

在这篇文章中,我将迅速调研一种跟踪的 Go 程序的新方法:基于 Linux 4.x eBPF 实现动态跟踪。如果你去搜索 Go 和 BPF,你会发现使用 BPF...

4935

扫码关注云+社区