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

相关文章

来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

471
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2349
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2762
来自专栏FD的专栏

Effective Testing with RSpec 3 (英文版)(序言)

Early praise for Effective Testing with RSpec 3

1864
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3749
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

6426
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1182
来自专栏linux驱动个人学习

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

8175
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1192
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

3081

扫码关注云+社区