C++ 算法包和源码简析

作者: zcwfeng | 来源:发表于2021-04-04 22:10 被阅读0次

C++ 函数适配器

STL中定义了大量的函数对象，但是有时候需要对函数返回值进行进一步的简单计算，或者填上多余的参数，不能直接代入算法，函数适配器实现了这一功能，将一种函数对象转化为另一种符合要求的函数对象，函数适配器可以分为4大类，绑定适配器，组合适配器，指针函数适配器和成员函数适配器

标准适配器.png

直接构造STL中的函数适配器通常会导致冗长的类型声明。为简化适配器的构造，STL还提供了函数适配器辅助函数，借助于泛型自动推断技术，无须显式的类型声明便可实现函数适配器的构造

辅助函数.png

常用函数适配器

bind1st(op,value)
bind2nd(op,value)
not1(op)
not2(op)
mem_fun_ref(op)
mem_fun(op) ptr_fun(op)

1 绑定器（binder）:binder 通过把二元函数对象的一个实参绑定到一个特殊的值上，将其转换成一元函数对象。C＋＋标准库提供两种预定义的 binder 适配器：bind1st 和 bind2nd，前者把值绑定到二元函数对象的第一个实参上，后者绑定在第二个实参上。
2 取反器(negator):negator 是一个将函数对象的值翻转的函数适配器。标准库提供两个预定义的 ngeator 适配器：not1 翻转一元预定义函数对象的真值,而 not2 翻转二元谓词函数的真值。

bind2nd
bind2nd 会调用 binder2nd

所以我们这两句是等价的

bind2nd(equal_to<string>(),"CCC")); 
binder2nd<equal_to<string>>(equal_to<string>(),"CCC"));

equal_to 需要两个参数，比较内容没有, 所以我们采用函数适配器传入

equals_to.jpg

现在的问题是：没有办法把 CCC 传递给 const _Tp& __y，就没法去比较
find_if(setVar.begin(), setVar.end(), equal_to<string>("CCC"), "CCC");

使用函数适配器后，就能够 CCCC 传递给了 const _Tp& __y，
setVar.begin(), setVar.end() 会把这些元素取出来 const _Tp& __x
x == y 的比较

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

int main() {
    set<string, less<string>> setVal;
    setVal.insert("AAA");
    setVal.insert("BBB");
    setVal.insert("CCC");

    for (auto it = setVal.begin(); it != setVal.end();it++) {
        cout << *it << endl;
    }
    // find_if 查看源码
    // equal_to 需要两个参数，比较内容没有，使用函数适配器解决
    set<string, less<string>>::iterator iteratorResult
            = find_if(setVal.begin(), setVal.end(),
//                    bind2nd(equal_to<string>(),"CCC"));
    binder2nd<equal_to<string>>(equal_to<string>(),"CCC"));
    if(iteratorResult != setVal.end()){
        cout << "success" << endl;
    } else {
        cout << "fail" << endl;

    }

    return 0;
}

取反适配器

一元取反适配器 not1
继承unary_fuction<类型1，返回值类型>

#include <iostream>
#include<algorithm>
#include <vector>

using namespace std;
class MyPrint:public binary_function<int,int,void>{
public:
    void operator()(int v,int start) const{
        cout << "v=" << v << "start=" << start << "v+start=" << v + start << endl;

    }
};

// 取反适配器
class CreateThenFive:public unary_function<int,bool>{
public:
    bool operator()(int v)const{
        return v > 5;
    }
};

int main() {
    //一元取反
    vector<int>v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }

    //查找大于5的数字
    //需求改为找小于5的数字

    vector<int>::iterator  pos1 = find_if(v.begin(),v.end(),CreateThenFive());

    auto  pos2 = find_if(v.begin(),v.end(),not1(CreateThenFive()));
    auto  pos = find_if(v.begin(),v.end(),not1(bind2nd(less<int>(),5)));


    if (pos != v.end())
    {
        cout << "找到大于5的数字为：" <<*pos<< endl;
    }
    else
    {
        cout << "未找到" << endl;
    }

    return 0;
}

函数指针适配器ptr_fun

#include <iostream>
#include<algorithm>
#include <vector>

using namespace std;

void myprint(int v, int start) {
    cout << v + start << endl;

}


int main() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    //将函数指针 适配为函数对象
    //ptr_fun

    for_each(v.begin(), v.end(), bind2nd(ptr_fun(myprint), 100));

    return 0;
}

成员函数适配器mem_fun_ref


//成员函数适配器
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class Person {
public:
    Person(string name, int age) {
        this->m_Name = name;
        this->m_Age = age;
    }



    void showPerson() {
        cout << "成员函数中姓名：" << m_Name << "年龄：" << m_Age << endl;
    }

    void plusAge() {
        this->m_Age += 100;
    }

    string m_Name;
    int m_Age;
};
void MyPrintPerson(Person &p) {
    cout << "姓名：" << p.m_Name << "年龄：" << p.m_Age << endl;
}
int main() {
    vector <Person> v;
    Person p1("aaa", 10);
    Person p2("bbb", 15);
    Person p3("ccc", 18);
    Person p4("ddd", 40);

    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);

    //成员函数适配器
    //mem_fun_ref
    for_each(v.begin(),v.end(),mem_fun_ref(&Person::showPerson));
    for_each(v.begin(),v.end(),mem_fun_ref(&Person::plusAge));
    for_each(v.begin(),v.end(),mem_fun_ref(&Person::showPerson));
    for_each(v.begin(),v.end(),ptr_fun(MyPrintPerson));


    return 0;
}

C++ 算法包内置源码

2.jpg

前几篇使用过for_each 并简单分析了源码，再看一个例子
STL 算法之 for_each
查看源码，根据源码自定义仿函数__F

for_eqch.jpg

#include <iostream>
#include <set>
#include<algorithm>
#include <vector>

using namespace std;

class __F{
public:
    void operator()(int __first){
        cout << "自定义一元谓词" << __first << endl;
    }
};

int main() {
    vector<int> vectorVar;
    vectorVar.insert(vectorVar.begin(),1000);
    vectorVar.insert(vectorVar.begin(),2000);
    vectorVar.insert(vectorVar.begin(),3000);
    //for_each 源码 __f 自定义反函数
    for_each(vectorVar.begin(),vectorVar.end(),__F());

    return 0;
}

STL 算法之 transform

先写demo，使用的时候点进transform看一眼源码，写仿函数__UnaryOperation

transform.jpg

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

class __UnaryOperation{
public:
    int operator()(const int __first){
        cout << "自定义一元谓词" << __first << endl;
        return __first + 9;
    }
};


int main(){

    vector<int> vectorVar;
    vectorVar.insert(vectorVar.begin(),1000);
    vectorVar.insert(vectorVar.begin(),2000);
    vectorVar.insert(vectorVar.begin(),3000);
    //for_each 源码 __f 自定义反函数
    // 第三个参数接收值
    transform(vectorVar.begin(),vectorVar.end(),vectorVar.begin(),__UnaryOperation());

    for(auto it = vectorVar.begin();it != vectorVar.end();it++){
        cout << *it << endl;
    }

    // 标准外部写法
    vector<int> vr;
    vr.resize(vectorVar.size());
    transform(vectorVar.begin(),vectorVar.end(),vr.begin(),__UnaryOperation());
    for(auto it = vr.begin();it != vr.end();it++){
        cout << *it << endl;
    }

    return 0;
}

STL 算法之 find 与 find_if:查找容器内容
find 没有自定义仿函数

int main() {
   vector<int> vectorVar;
   vectorVar.insert(vectorVar.begin(), 10000);
   vectorVar.insert(vectorVar.begin(), 20000);
   vectorVar.insert(vectorVar.begin(), 30000);
   vectorVar.insert(vectorVar.begin(), 40000);

   // find 没有自定义仿函数
   auto iteratorVar = find(vectorVar.begin(), vectorVar.end(), 40000);
   if (iteratorVar != vectorVar.end()) {
       cout << "查找到了" << endl;
   } else {
       cout << "没有找到" << endl;
   }
   return 0;
}

find_if 有自定义仿函数
查看源码，find和find_if. 区别在于源码的__pred 访函数

// find_if 有自定义仿函数
class __pred {
public:
    int number;
    __pred(int number) : number(number) {}
    bool operator() (const int value) {
        return number == value;
    }
};

int main() {
    vector<int> vectorVar;
    vectorVar.insert(vectorVar.begin(), 10000);
    vectorVar.insert(vectorVar.begin(), 20000);
    vectorVar.insert(vectorVar.begin(), 30000);
    vectorVar.insert(vectorVar.begin(), 40000);

    auto it = find_if(vectorVar.begin(), vectorVar.end(), __pred(30000));

    if (it != vectorVar.end()) {
        cout << "查找到了" << endl;
    } else {
        cout << "没有找到" << endl;
    }
    return 0;

STL 算法之 count 与 count_if:统一该值在容器中出现的个数

看源码也是很简单

template <class _InputIterator, class _Predicate>
_LIBCPP_NODISCARD_EXT inline
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
typename iterator_traits<_InputIterator>::difference_type
count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
{
    typename iterator_traits<_InputIterator>::difference_type __r(0);
    for (; __first != __last; ++__first)
        if (__pred(*__first))
            ++__r;
    return __r;
}

示例demo:

#include <iostream>
#include <vector> // stl包
#include <algorithm> // 算法包

using namespace std;

// count 没有自定义仿函数
int main() {
    vector<int> vectorVar;
    vectorVar.push_back(1);
    vectorVar.push_back(2);
    vectorVar.push_back(3);
    vectorVar.push_back(2);
    vectorVar.push_back(4);
    vectorVar.push_back(6);
    vectorVar.push_back(8);
    vectorVar.push_back(1);

    int number = count(vectorVar.begin(), vectorVar.end(), 2);
    cout << "等于2的个数是:" << number << endl;

    // C++ 源码 函数适配器
    number = count_if(vectorVar.begin(), vectorVar.end(), bind2nd(less<int>(), 2)); // 函数适配器 配合 less   <
    cout << "等于2的个数是:" << number << endl;

    number = count_if(vectorVar.begin(), vectorVar.end(), bind2nd(greater<int>(), 2)); // 函数适配器 配合 less >
    cout << "等于2的个数是:" << number << endl;

    number = count_if(vectorVar.begin(), vectorVar.end(), bind2nd(equal_to<int>(), 2)); // 函数适配器 配合 less =
    cout << "等于2的个数是:" << number << endl;

    return 0;
}

STL 算法之 merge:把两个有序数组进行合并

#include <iostream>
#include <set>
#include<algorithm>
#include <vector>

using namespace std;


int main() {
    vector<int> vectorVar;
    vectorVar.insert(vectorVar.begin(), 1000);
    vectorVar.insert(vectorVar.begin(), 2000);
    vectorVar.insert(vectorVar.begin(), 3000);
    vector<int> vectorVar2;
    vectorVar2.insert(vectorVar2.begin(), 1000);
    vectorVar2.insert(vectorVar2.begin(), 2000);
    vectorVar2.insert(vectorVar2.begin(), 3000);
    vector<int> result;
    result.resize(vectorVar.size() + vectorVar2.size());
    merge(vectorVar.begin(), vectorVar.end(), vectorVar2.begin(), vectorVar2.end(), result.begin());
    for (auto it = result.begin(); it != result.end(); it++) {
        cout << "it = " << *it << endl;
    }

    return 0;
}

源码简单看一眼：

template <class _InputIterator1, class _InputIterator2, class _OutputIterator>
inline _LIBCPP_INLINE_VISIBILITY
_OutputIterator
merge(_InputIterator1 __first1, _InputIterator1 __last1,
      _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result)
{
    typedef typename iterator_traits<_InputIterator1>::value_type __v1;
    typedef typename iterator_traits<_InputIterator2>::value_type __v2;
    return _VSTD::merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());
}
---------------------------
merge 方法

template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
_OutputIterator
__merge(_InputIterator1 __first1, _InputIterator1 __last1,
        _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
{
    for (; __first1 != __last1; ++__result)
    {
        if (__first2 == __last2)
            return _VSTD::copy(__first1, __last1, __result);
        if (__comp(*__first2, *__first1))
        {
            *__result = *__first2;
            ++__first2;
        }
        else
        {
            *__result = *__first1;
            ++__first1;
        }
    }
    return _VSTD::copy(__first2, __last2, __result);
}

最终是经过算法后，调用了copy到_result

STL 算法之 sort:排序

#include <iostream>
#include <set>
#include<algorithm>
#include <vector>

using namespace std;


int main() {
    vector<int> vectorVar;
    vectorVar.push_back(1000);
    vectorVar.push_back(2000);
    vectorVar.push_back(3000);
    vectorVar.push_back(4000);
    vectorVar.push_back(3000);


    sort(vectorVar.begin(), vectorVar.end(), greater<int>());

    random_shuffle(vectorVar.begin(), vectorVar.end());
    for (auto it = vectorVar.begin(); it != vectorVar.end(); it++) {
        cout << "it = " << *it << endl;
    }
    return 0;
}

STL 算法之 random_shuffle:随机打乱元素的顺序

#include <iostream>
#include <vector> // stl包
#include <algorithm> // 算法包

using namespace std;

int main() {
    vector<int> vectorVar; // vector默认是没有排序功能的
    vectorVar.push_back(65);
    vectorVar.push_back(53);
    vectorVar.push_back(84);
    vectorVar.push_back(11);
    vectorVar.push_back(22);
    vectorVar.push_back(33);
    vectorVar.push_back(44);


    sort(vectorVar.begin(), vectorVar.end(), less<int>()); 
    random_shuffle(vectorVar.begin(), vectorVar.end());

    // 直接打印 vectorVar容器  此时 是不是就已经排序了
    for (auto itVar = vectorVar.begin(); itVar != vectorVar.end() ; itVar++) {
        cout << *itVar << "\t";
    }
    return 0;
}

STL 算法之 copy:copy 容器 1 的元素到容器 2


#include <iostream>
#include <set>
#include<algorithm>
#include <vector>

using namespace std;


int main() {
    vector<int> vectorVar;
    vectorVar.push_back(1000);
    vectorVar.push_back(2000);
    vectorVar.push_back(3000);
    vectorVar.push_back(4000);
    vectorVar.push_back(5000);

    vector<int> result;
    result.resize(vectorVar.size());
    copy(vectorVar.begin(), vectorVar.end(), result.begin());

    for (auto it = vectorVar.begin(); it != vectorVar.end(); it++) {
        cout << "it = " << *it << endl;
    }
    return 0;
}

STL 算法之 replace，替换元素内容

#include <iostream>
#include <set>
#include<algorithm>
#include <vector>

using namespace std;


int main() {
    vector<int> vectorVar;
    vectorVar.push_back(1000);
    vectorVar.push_back(2000);
    vectorVar.push_back(3000);
    vectorVar.push_back(4000);
    vectorVar.push_back(5000);


    replace(vectorVar.begin(), vectorVar.end(), 1000,1111);

    for (auto it = vectorVar.begin(); it != vectorVar.end(); it++) {
        cout << "it = " << *it << endl;
    }
    return 0;
}

C++ 算法包和源码简析

C++ 函数适配器

C++ 算法包内置源码

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

C语言

C/C++ 专题知识

移动前端 Python Android Java

百年工匠

简书文选

编程语言爱好者

知识图谱

简友广场