C++回顾(二十六)—— 算法
创始人
2024-06-02 07:01:26
0

26.1 算法概述

  • 算法部分主要由头文件组成。

  • 是所有STL头文件中最大的一个,其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、反转、排序、合并等等。

  • 体积很小,只包括几个在序列上面进行简单数学运算的模板函数,包括加法和乘法在序列上的一些操作。

  • 中则定义了一些模板类,用以声明函数对象。

STL提供了大量实现算法的模版函数,只要我们熟悉了STL之后,许多代码可以被大大的化简,只需要通过调用一两个算法模板,就可以完成所需要的功能,从而大大地提升效率。

需要添加头文件:

#include 
#include 
#include 

26.2 算法中函数对象和谓词

26.2.1 函数对象和谓词定义

(1)函数对象

重载函数调用操作符的类,其对象常称为函数对象(function object),即它们是行为类似函数的对象。一个类对象,表现出一个函数的特征,就是通过“对象名+(参数列表)”的方式使用一个类对象,如果没有上下文,完全可以把它看作一个函数对待。
这是通过重载类的operator()来实现的。
标准库中的很多算法都可以使用函数对象或者函数来作为自定的回调行为

(2)谓词

  • 一元函数对象:函数参数1个;二元函数对象:函数参数2个。

  • 一元谓词函数参数1个,函数返回值是bool类型,可以作为一个判断式

  • 谓词可以是一个仿函数,也可以是一个回调函数。

  • 二元谓词 函数参数2个,函数返回值是bool类型

  • 一元谓词函数举例如下
    判断给出的string对象的长度是否小于6

bool GT6(const string &s)
{return s.size() >= 6;
}
  • 二元谓词举例如下
    比较两个string对象,返回一个bool值,指出第一个string是否比第二个短
bool isShorter(const string &s1, const string &s2)
{return s1.size() < s2.size();
}

26.2.2 预定义函数对象和函数适配器

标准模板库STL提前定义了很多预定义函数对象,头文件 必须包含。

(1)算术函数对象

  • 预定义的函数对象支持加、减、乘、除、求余和取反。调用的操作符是与type相关联的实例
  • 加法:plus
  • 减法:minus
  • 乘法:multiplies
  • 除法:divides
  • 求余:modulus
  • 取反:negate

(2)关系函数对象

  • 等于equal_to
equal_to stringEqual;
sres = stringEqual(sval1,sval2);
  • 不等于not_equal_to
  • 大于 greater
  • 大于等于greater_equal
  • 小于 less
  • 小于等于less_equal

(3)逻辑函数对象

  • 逻辑与 logical_and
  • 逻辑或 logical_or
  • 逻辑非 logical_not

26.2.3 函数适配器

(1)概念

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

(2)常用函数函数适配器

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

  • 常用函数适配器列表如下:
    bind1st(op, value)
    bind2nd(op, value)
    not1(op)
    not2(op)
    mem_fun_ref(op)
    mem_fun(op)
    ptr_fun(op)

示例代碼:

#include 
#include 
#include using namespace std;bool Equal(string str)
{return str == "bb";
}int main()
{vector v;v.push_back("aa");v.push_back("bb");v.push_back("cc");v.push_back("dd");//vector::iterator it = find_if(v.begin(), v.end(), Equal);vector::iterator it = find_if(v.begin(), v.end(),  bind1st(equal_to(), "bb"));if (it == v.end()){cout << "不存在" << endl;}else{cout << *it << endl;}return 0;
}

運行結果:
在这里插入图片描述

26.3 常用算法

26.3.1 遍历算法

(1)for_each

for_each: 用指定函数依次对指定范围内所有元素进行迭代访问。该函数不得修改序列中的元素
在这里插入图片描述

(2)transform

transform: 与for_each类似,遍历所有元素,但可对容器的元素进行修改

在这里插入图片描述

完整示例代码:

#include 
#include 
#include using namespace std;void show(int x)
{cout << x << endl;
}class print
{
public:void operator()(int x){cout << x << endl;}
};int main()
{int array[5] = {1, 2, 3, 4, 5};vector v(array, array + 5);//for_each遍历过程中 不能修改数据for_each(v.begin(), v.end(), show);    //回调函数形式遍历for_each(v.begin(), v.end(), print()); //函数对象形式遍历 //transform遍历过程中 可以修改数据string s("helloworld");// 从s.begin()开始,到s.eng()结束。把修改的元素从s.begin()开始放,这里是把元素变成大写transform(s.begin(), s.end(), s.begin(), ::toupper);cout << s << endl;return 0;
}

运行结果:
在这里插入图片描述

26.3.2 查找算法

(1)adjacent_find

在iterator对标识元素范围内,查找一对相邻重复元素,找到则返回指向这对元素的第一个元素的迭代器。否则返回past-the-end。
在这里插入图片描述

(2)binary_search

有序序列中查找value,找到则返回true。注意:在无序序列中,不可使用。
在这里插入图片描述

(3)count/count_if

  • count:利用等于操作符,把标志范围内的元素与输入值比较,返回相等的个数。
    在这里插入图片描述

  • count_if:利用自定义操作符,把标志范围内的元素与输入值比较,返回满足条件的元素个数
    在这里插入图片描述
    在这里插入图片描述

例:
序列1 3 5 7 9 11 13
统计等于3的元素的个数,使用count
统计大于3的元素的个数,使用count_if

(4)find/find_if

  • find: 利用底层元素的等于操作符,对指定范围内的元素与输入值进行比较。当匹配时,结束搜索,返回该元素的迭代器。
    在这里插入图片描述

  • find_if:利用自定义条件,对指定范围内的元素与输入值进行比较,当匹配时,结束搜索,返回该元素的迭代器。
    在这里插入图片描述
    在这里插入图片描述

例:
序列:1 3 5 7 9 11 13
查找元素3,找到返回该元素的迭代器,用find
查找大于3的元素,找到返回该元素的迭代器,用find_if

完整示例代码:

#include 
#include 
#include using namespace std;bool GreaterTwo(int x)
{return x > 2;
}class GreaterThree
{
public:bool operator()(int x){return x > 3;}
};int main()
{int array[6] = {1, 2, 2, 3, 4, 4};vector v(array, array + 6);vector::iterator it = adjacent_find(v.begin(), v.end());if (it == v.end()){cout << "不存在重复且相邻的" << endl;}else{cout << *it << endl;}bool ret = binary_search(v.begin(), v.end(), 4);      //在有序的序列里面查找if (ret){cout << "元素存在" << endl;}else{cout << "元素不存在" << endl;}int num = count(v.begin(), v.end(), 2);cout << num << endl;num = count_if(v.begin(), v.end(), GreaterTwo);    //一元谓词   回调函数cout << num << endl;it = find(v.begin(), v.end(), 3);if (it == v.end()){cout << "元素不存在" << endl;}else{cout << *it << endl;}it = find_if(v.begin(), v.end(), GreaterThree());      //函数对象if (it == v.end()){cout << "元素不存在" << endl;}else{cout << *it << endl;}return 0;
}

运行结果:
在这里插入图片描述

26.3.3 排序算法

(1)merge

merge: 合并两个有序序列,存放到另一个序列。

在这里插入图片描述

(2)sort

sort: 以默认升序的方式重新排列指定范围内的元素。若要改排序规则,可以输入比较函数。
在这里插入图片描述

(3)random_shuffle

random_shuffle: 对指定范围内的元素随机调整次序
在这里插入图片描述

(4)reverse

在这里插入图片描述
完整示例代码:

#include 
#include 
#include 
#include 
#include using namespace std;void show(int x)
{cout << x << " ";
}int main()
{vector v1;vector v2;srand(time(NULL));for (int i = 0; i < 5; i++){v1.push_back(rand() % 10);v2.push_back(rand() % 10);}sort(v1.begin(), v1.end(), less());sort(v2.begin(), v2.end(), less());cout << "v1:" << endl;for_each(v1.begin(), v1.end(), show);cout << endl;cout << "v2:" << endl;for_each(v2.begin(), v2.end(), show);cout << endl;vector v3;v3.resize(10); // 对v3进行扩容merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());for_each(v3.begin(), v3.end(), show);cout << endl;random_shuffle(v1.begin(), v1.end());cout << "v1:" << endl;for_each(v1.begin(), v1.end(), show);cout << endl;reverse(v3.begin(), v3.end());for_each(v3.begin(), v3.end(), show);cout << endl;return 0;
}

运行结果:
在这里插入图片描述

26.3.4 拷贝和替换算法

(1)copy

例子:

vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);vector vecIntB;
vecIntB.resize(5);          //扩大空间
//vecIntB: {1,3,5,7,9}
copy(vecIntA.begin(), vecIntA.end(), vecIntB.begin()); 

(2)replace

  • replace(beg,end,oldValue,newValue): 将指定范围内的所有等于oldValue的元素替换成newValue。

例子:

vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(3);
vecIntA.push_back(9);replace(vecIntA.begin(), vecIntA.end(), 3, 8);  //{1,8,5,8,9}

(3)replace_if

  • replace_if : 将指定范围内所有操作结果为true的元素用新值替换。
    用法举例:replace_if(vecIntA.begin(),vecIntA.end(),GreaterThree,newVal)
    其中 vecIntA是用vector声明的容器
    GreaterThree 函数的原型是 bool GreaterThree(int iNum)

//把大于等于3的元素替换成8

vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(3);
vecIntA.push_back(9);replace_if(vecIntA.begin(), vecIntA.end(), GreaterThree, 8);

(4)swap

swap: 交换两个容器的元素

完整示例代码:

#include 
#include 
#include using namespace std;void show(int x)
{cout << x << " ";
}int main()
{vector v1(5, 1);vector v2(5, 2);v2.resize(6);copy(v1.begin(), v1.end(), ++(v2.begin()));for_each(v2.begin(), v2.end(), show);cout << endl;swap(v1, v2);for_each(v2.begin(), v2.end(), show);cout << endl;return 0;
}

运行结果:
在这里插入图片描述

26.3.5 算数和生成算法

(1)accumulate

  • accumulate: 对指定范围内的元素求和,然后结果再加上一个由val指定的初始值。
  • 包含头文件
vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);
int iSum = accumulate(vecIntA.begin(), vecIntA.end(), 100);     //iSum==125

(2)fill

  • fill: 将输入值赋给标志范围内的所有元素。
vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);fill(vecIntA.begin(), vecIntA.end(), 8);   //8, 8, 8, 8, 8

26.3.6 集合算法

  • set_union: 构造一个有序序列,包含两个有序序列的并集
  • set_intersection: 构造一个有序序列,包含两个有序序列的交集
  • set_difference: 构造一个有序序列,该序列保留第一个有序序列中存在而第二个有序序列中不存在的元素。
vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);vector vecIntB;
vecIntB.push_back(1);
vecIntB.push_back(3);
vecIntB.push_back(5);
vecIntB.push_back(6);
vecIntB.push_back(8);vector vecIntC;
vecIntC.resize(10);// 并集
// vecIntC : {1,3,5,6,7,8,9,0,0,0}
set_union(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin()); // 交集
// vecIntC: {1,3,5,0,0,0,0,0,0,0}
fill(vecIntC.begin(), vecIntC.end(), 0);
set_intersection(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin()); // 差集
// vecIntC: {7,9,0,0,0,0,0,0,0,0}
fill(vecIntC.begin(), vecIntC.end(), 0);
set_difference(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin()); 

相关内容

热门资讯

苹果怎么倒进安卓系统,一键倒装... 你有没有想过,把苹果手机里的宝贝倒腾到安卓系统里去?听起来是不是有点像变魔术?别急,今天就来手把手教...
安卓系统都能双系统么吗,揭秘双... 你有没有想过,你的安卓手机是不是也能来个“双胞胎”呢?没错,就是那种一个手机里同时运行两个操作系统,...
长安汽车升级安卓系统,安卓系统... 你知道吗?最近长安汽车可是来了一次大变身呢!没错,就是那个我们熟悉的国产汽车品牌,这次他们竟然升级了...
mac电脑装安卓系统,轻松实现... 亲爱的电脑迷们,你是否曾幻想过在你的Mac电脑上运行安卓系统?想象那些你钟爱的安卓应用,在你的Mac...
安卓p系统流畅吗,畅享无忧 你有没有发现,最近安卓P系统成了大家热议的话题呢?不少朋友都在问,这个新系统到底流畅不流畅啊?今天,...
剑灵2安卓系统,畅游东方奇幻世... 你知道吗?最近在安卓系统上,有一款游戏可是火得一塌糊涂,那就是《剑灵2》!这款游戏不仅画面精美,操作...
安卓系统是否指定品牌,品牌定制... 你有没有想过,为什么你的安卓手机总是那么独特,而别人的安卓手机却看起来差不多呢?这背后,其实隐藏着一...
安卓系统和iso系统 照片共享... 你有没有发现,现在手机拍照功能越来越强大,拍出来的照片美得不要不要的!但是,当你想和朋友们分享这些精...
安卓系统领夹麦,便携式音频解决... 你有没有发现,现在手机通话越来越方便了,但是有时候,手机那点小小的麦克风,真的有点力不从心呢!尤其是...
安卓系统经常无法唤醒,探究系统... 你是不是也遇到过这种情况?手机屏幕黑了,手指在屏幕上疯狂地滑动,却怎么也唤醒不了安卓系统。这可真是让...
自己编译安卓系统源码,编译安卓... 你有没有想过,安卓系统其实就像一个巨大的宝藏,里面藏着无数的秘密和可能性?今天,就让我带你一起探索这...
鸿蒙系统属于安卓,基于安卓的全... 你知道吗?最近有个话题在科技圈里可是闹得沸沸扬扬的,那就是鸿蒙系统。没错,就是那个华为自主研发的操作...
lephone是安卓系统吗,深... 你有没有听说过lephone这个品牌呢?最近,身边的朋友都在讨论这个手机,说它性价比超高,但是,有人...
pc双系统安卓系统下载软件,P... 你有没有想过,在电脑上同时运行安卓系统,是不是就像在手机上玩电脑游戏一样酷炫呢?没错,这就是今天我要...
电量壁纸安卓系统设置,安卓系统... 手机电量告急,是不是又得赶紧找充电宝了?别急,今天就来和你聊聊如何通过设置电量壁纸来给安卓系统来个“...
ip是安卓系统吗,通过IP地址... 你有没有想过,那个陪伴你每天刷剧、玩游戏、办公的IP,它是不是安卓系统呢?别急,今天就来揭开这个谜底...
安卓系统谁负责升级,揭秘幕后负... 你有没有想过,你的安卓手机为什么有时候会突然收到系统更新的通知呢?是不是好奇,是谁在背后默默地为你的...
安卓系统需要降级吗,安卓系统升... 你有没有发现,你的安卓手机最近有点儿“老态龙钟”了呢?运行速度慢吞吞的,有时候还卡个不停。这时候,你...
性价比手机安卓系统,盘点安卓系... 你有没有想过,在这个手机更新换代如此迅速的时代,如何用最少的钱,买到最满意的手机呢?没错,我要说的是...
虚拟大师安卓2.0系统,安卓新... 你有没有听说最近虚拟大师安卓2.0系统火得一塌糊涂?这可不是空穴来风,而是真的让不少手机用户都跃跃欲...