STL之算法

函数对象

重载函数调用操作符的类,其对象常称为函数对象(function object) ,即它们是行为类似函数的对象,也叫仿函数(functor),其实就是重载"()"操作符，使得类对象可以像函数那样调用。

注意：

​ 1.函数对象(仿函数)是一个类，不是一个函数。

​ 2.函数对象(仿函数)重载了"()"操作符使得它可以像函数一样调用。

分类：

​ 如果函数对象 有一个参数 叫：一元函数对象

​ 如果函数对象 有二个参数 叫：二元函数对象

​ 如果函数对象 有三个参数 叫： 多元函数对象

#include <iostream>

using namespace std;

//函数对象(仿函数)
class Print
{
public:
    void operator()(char *str)
    {
        cout << str << endl;
    }
};

int main()
{
    Print p;
    p("hello world");
    return 0;
}

谓词

返回值为bool类型的普通函数或仿函数 都叫谓词。

如果谓词 有一个参数 叫：一元谓词

如果谓词 有二个参数 叫：二元谓词

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

using namespace std;

class GreaterThan30
{
public:
    bool operator()(int value)
    {
        return value>20;
    }
};

int main()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    //find_if条件查找
    vector<int>::iterator ret;
    ret = find_if(v.begin(), v.end(), GreaterThan30());
    if(ret != v.end())
    {
        cout << "查找结果: " << *ret << endl;
    }
    return 0;
}

二元谓词

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

using namespace std;

class MyGreaterInt
{
public:
    bool operator()(int v1, int v2)
    {
        return v1>v2;
    }
};

int main()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    
    sort(v.begin(), v.end(), MyGreaterInt());
    return 0;
}

内建函数对象

STL内建了一些函数对象。分为:算数类函数对象,关系运算类函数对象,逻辑运算类仿函数。这些仿函数所产生的对象,用法和一般函数完全相同，当然我们还可以产生无名的临时对象来履行函数功能。

6 个算数类函数对象,除了 negate 是一元运算，其他都是二元运算。

template<class T> T plus<T>//加法仿函数
template<class T> T minus<T>//减法仿函数
template<class T> T multiplies<T>//乘法仿函数
template<class T> T divides<T>//除法仿函数
template<class T> T modulus<T>//取模仿函数
template<class T> T negate<T>//取反仿函数

6个关系运算类函数对象，每一种都是二元运算。

template<class T> bool equal_to<T>//等于
template<class T> bool not_equal_to<T>//不等于
template<class T> bool greater<T>//大于
template<class T> bool greater_equal<T>//大于等于
template<class T> bool less<T>//小于
template<class T> bool less_equa <T>//小于等于

逻辑运算类运算函数 not为一元运算，其余为二元运算。

template<class T> bool logical_and<T>//逻辑与
template<class T> bool logical_or<T>//逻辑或
template<class T> bool logical_not<T>//逻辑非

案例:

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

using namespace std;

void printVectorInt(vector<int>& v)
{
    vector<int>::iterator it = v.begin();
    for(;it!=v.end();it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

int main()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    vector<int>::iterator ret;
    //内建函数对象
    ret = find_if(v.begin(), v.end(), bind2nd(greater<int>(), 10)); //bind2nd()将后面两个参数绑定成一个
    if(ret != v.end())
    {
        while(ret != v.end())
        {
            cout << *ret++ << endl;
        }
    }
    return 0;
}

适配器

适配器 为算法 提供接口

函数对象适配器

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

using namespace std;

//第二步: 公共继承binary_function 参数萃取
class PrintInt: public binary_function<int, int, void>
{
public:
    //第三步: const修饰operator()
    void operator()(int val, int tmp) const
    {
//        cout << val+tmp << " ";
        cout << "val = " << val << ", " << "tmp = " << tmp << endl;
    }
};

int main()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    //第一步: bind2nd或bind1st绑定参数
    for_each(v.begin(), v.end(), bind2nd(PrintInt(), 200)); //bind2nd将200绑定到第二个参数
    for_each(v.begin(), v.end(), bind1st(PrintInt(), 200)); //bind1st将200绑定到第一个参数
    cout << endl;
    return 0;
}

函数指针适配器 ptr_fun

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

using namespace std;

void myPrintInt(int value, int tmp)
{
    cout << "value = " << value << ", tmp = " << tmp << endl;
}

int main()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(50);
    v1.push_back(70);
    v1.push_back(90);
    //myPrintInt是函数名在C++中不能作为函数入口地址, 需要ptr_fun转换
    for_each(v1.begin(), v1.end(), bind2nd(ptr_fun(myPrintInt), 100));
    cout << endl;
    return 0;
}

成员函数 作为适配器 mem_fun_ref

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

using namespace std;

class Data
{
public:
    int data;
public:
    Data(){}
    Data(int d)
    {
        data = d;
    }
    void printInt(int tmp)
    {
        cout << "value = " << data+tmp << endl;
    }
};

int main()
{
    vector<Data> v1;
    v1.push_back (Data(10));
    v1.push_back (Data(30));
    v1.push_back (Data(50));
    v1.push_back (Data(70));
    v1.push_back (Data(90));
    //mem_fun_ref 成员函数指针 &Data::printInt 成员函数入口地址
    for_each(v1.begin(), v1.end(), bind2nd(mem_fun_ref(&Data::printInt), 100));
    return 0;
}

取反适配器

not1 一元取反

not2 二元取反

算法概述

算法的头文件#include。是所有 STL头文件中最大的一个其中常用的功能涉及到比较，交换，查找，遍历，复制，修改，反转,排序,合并等…..体积很小,只包括在几个序列容器上进行的简单运算的模板函数.定义了一些模板类,用以声明函数对象。

常用遍历算法

for_each 遍历算法

/*
遍历算法 遍历容器元素
@param beg 开始迭代器
@param end 结束迭代器
@param _callback函数回调或者函数对象
@return 函数对象
*/
for_each(iterator beg, iterator end, _callback);

transform 算法

/*
transform 算法 将指定容器区间元素搬运到另一容器中
注意: transform 不会给目标容器分配内存，所以需要我们提前分配好内存@param beg1源容器开始迭代器
@param end1 源容器结束迭代器
@param beg2 目标容器开始迭代器
@param _callback回调函数或者函数对象
@return 返回目标容器迭代器
*/
transform(iterator beg1, iterator end1, iterator beg2, _callback);

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

using namespace std;

int myTransform(int value)
{
    return value;
}

int main()
{
    vector<int> v1;
    v1.push_back (10);
    v1.push_back (30);
    v1.push_back (50);
    v1.push_back (70);
    v1.push_back (90);

    vector<int> v2;
    v2.resize(v1.size());

    transform(v1.begin(), v1.end(), v2.begin(), myTransform);

    for_each(v2.begin(), v2.end(), [=](int value){
        cout << value << endl;
    });
    return 0;
}

常用查找算法

find 算法

/*
find 算法 查找元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@return 返回查找元素的位置
*/
find(iterator beg, iterator end, value);

find_if 算法

/*
find_if 算法 条件查找
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param callback回调函数或者谓词(返回bool类型的函数对象)
@return bool 查找返回true 否则 false
*/
find_if(iterator beg, iterator end, _callback);

adjacent_find 算法

/*
adjacent_find 算法 查找相邻重复元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param -callback回调函数或者谓词(返回bool类型的函数对象)
@return 返回相邻元素的第一个位置的迭代器
*/
adjacent_find(iterator beg, iterator end, _callback);

binary_search 算法

/*
binary_search 算法 二分查找法
注意：在无序序列中不可用
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@return bool 查找返回 true 否则 false
*/
bool binary_search(iterator beg, iterator end, value);

count 算法

/*
统计元素出现次数
@param beg 容器开始迭代器
@param end容器结束迭代器
@param value回调函数或者谓词(返回boo1类型的函数对象)
@return int 返回元素个数
*/
count(iterator beg, iterator end, value);

count_if 算法

/*
count_if 算法 统计元素出现次数
@param beg容器开始迭代器
@param end 容器结束迭代器
@param callback回调函数或者谓词(返回 bool类型的函数对象)
@return int 返回元素个数
*/
count_if(iterator beg, iterator end, _callback);

常用排序算法

merge算法

/*
merge 算法 容器元素合并，并存储到另一容器中
注意：两个容器必须是有序的
@param beg1 容器 1 开始迭代器
@param end1 容器 1 结束迭代器
@param beg2 容器 2 开始迭代器
@param end2 容器 2 结束迭代器
@param beg3 目标容器开始迭代器
*/
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator beg3);

sort 算法

/*
sort 算法 容器元素排序
@param beg 容器 1 开始迭代器
@param end 容器 1 结束迭代器
@param -callback回调函数或者谓词(返回bool类型的函数对象)
*/
sort(iterator beg, iterator end, _callback)

random_shuffle 算法

/*
random_shuffle 算法 对指定范围内的元素随机调整次序
@param beg 容器开始迭代器
@param end 容器结束迭代器
*/
random_shuffle(iteratorIbeg, iterator end);

reverse 算法

/*
reverse 算法 反转指定范围的元素
@param beg容器开始迭代器
@param end容器结束迭代器
*/
reverse(iterator beg, iterator end)

常用拷贝替换算法

copy算法

/*
copy算法将容器内指定范围的元素拷贝到另一容器中
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param dest 目标起始迭代器
*/
copy(iterator beg, iterator end, iterator dest)

终端迭代器输出:

replace算法

/*
replace 算法 将容器内指定范围的旧元素修改为新元素
@param beg 容器开始迭代器
@param end容器结束迭代器
@param oldvalue 旧元素
@param oldvalue新元素
*/
replace(iterator beg, iterator end, oldvalue, newval)

replace_if 算法

/*
replace_if 算法 将容器内指定范围满足条件的元素替换为新元素
@param beg 容器开始迭代器
@param end容器结束迭代器
@param callback函数回调或者谓词(返回Boo1类型的函数对象)
@param oldvalue 新元素
*/
replace_if(iterator beg, iterator end, _callback, newvalue)

swap 算法

/*
swap算法互换两个容器的元素
@param c1 容器 1
@param c2 容器 2
*/
swap(container c1,Tcontainer c2)

常用算法生成算法

accumulate 算法

/*
accumulate 算法 计算容器元素累计总和
@param beg 容器开始迭代器
@param end容器结束迭代器
@param value 累加值
*/
accumulate(iterator beg, iterator end, value)

fill 算法

/*
fill 算法 向容器中添加元素
@param beg容器开始迭代器
@param end 容器结束迭代器
@param value t 填充元素
*/
fill(iterator beg, iterator end, value)

常用集合算法

set_intersection 算法

/*
set_intersection算法求两个set集合的交集
注意：两个集合必须是有序序列
@param beg1容器1开始迭代器
@param end1容器1结束迭代器
@param beg2容器2开始迭代器
@param end2容器2结束迭代器
@param dest 目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
*/
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

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

using namespace std;

int main()
{
    vector<int> v1;
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(50);

    vector<int> v2;
    v2.push_back(20);
    v2.push_back(40);
    v2.push_back(60);

    vector<int> v3; //存交集
    v3.resize(min(v2.size(), v1.size()));
    vector<int>::iterator ret =  set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    copy(v3.begin(), ret, ostream_iterator<int>(cout, " "));
    return 0;
}

set_union 算法

/*
set_union 算法 求两个 set 集合的并集
注意：两个集合必须是有序序列
@param beg1 容器 1 开始迭代器
@param end1 容器 1 结束迭代器
@param beg2 容器 2 开始迭代器
@param end2 容器 2 结束迭代器
@param dest 目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
*/
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

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

using namespace std;

int main()
{
    vector<int> v1;
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(50);

    vector<int> v2;
    v2.push_back(20);
    v2.push_back(40);
    v2.push_back(60);

    vector<int> v3; //存并集
    v3.resize(v2.size()+v1.size());
    vector<int>::iterator ret =  set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    copy(v3.begin(), ret, ostream_iterator<int>(cout, " "));
    return 0;
}

set_difference 算法

/*
set_difference 算法 求两个 set 集合的差集
注意：两个集合必须是有序序列
@param beg1 容器1开始迭代器
@param end1 容器 1 结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest 目标容器开始迭代器
@return 目标容器的最后一个元素的迭代器地址
*/
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

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

using namespace std;

int main()
{
    vector<int> v1;
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(50);

    vector<int> v2;
    v2.push_back(20);
    v2.push_back(40);
    v2.push_back(60);

    vector<int> v3; //存差集
    v3.resize(v1.size());
    vector<int>::iterator ret =  set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
    copy(v3.begin(), ret, ostream_iterator<int>(cout, " "));
    return 0;
}

本栏目推荐文章
• 2024/1/13 算法笔记
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 算法练习题
• UDP通信 [补档-2023-07-22]
• 算法学习Day26组合总和、分割回文串
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• 【SPFA】最短路的一种算法
• 【ubantu22.10】安装部署timescaledbv2.13.0及postgresql v14.10
• 深拷贝和浅拷贝的问题 [补档-2022-10-22]

算法 STL 22算法stl 22 table hash stl 22 算法stl 拷贝 算法8.1 stl 算法7.1 stl 算法 常用 教程stl 算法 容器stl 算法day 22 算法ubuntu 22.04 host 逆序 序列 算法22