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()); 

相关内容

热门资讯

鸿蒙系统恢复安卓教程,一键操作... 你是不是也遇到了鸿蒙系统恢复安卓的难题?别急,今天就来给你详细讲解让你轻松搞定这个技术活儿!一、鸿蒙...
安卓怎么手机双系统,安卓手机轻... 你有没有想过,手机里装两个系统,一个用来工作,一个用来娱乐,那感觉是不是瞬间高大上了?没错,这就是今...
安卓系统提示已是最新,无需更新... 亲爱的手机用户,你有没有发现,你的安卓系统突然弹出一个提示:“已是最新”!是不是瞬间感觉自己的手机升...
安卓手机怎换系统,焕新体验 你有没有想过给你的安卓手机换换口味呢?是的,你没听错,就是那个一直陪伴你的安卓系统。有时候,用久了总...
配有安卓系统的吉他,解锁指尖艺... 你有没有想过,吉他这种乐器,竟然也能和安卓系统扯上关系?没错,就是那个我们日常使用的智能手机系统,竟...
安卓系统国际化,跨越语言与地域... 你知道吗?在这个科技飞速发展的时代,手机已经成为了我们生活中不可或缺的一部分。而说到手机,安卓系统绝...
无线显示安卓系统设计,无线显示... 你有没有想过,未来家里的电视、电脑、手机,甚至平板,都能无缝连接,随时随地共享屏幕内容?这可不是天方...
cf安卓系统怎么换苹果系统,轻... 你是不是也和我一样,对手机系统有着浓厚的兴趣呢?最近,我发现了一个超级有趣的话题:怎么把安卓系统的手...
安卓系统电量显示应用,安卓系统... 手机电量不足的时候,是不是感觉整个人都不好了?别急,今天就来给你安利几款安卓系统电量显示应用,让你的...
安卓系统谷歌赚钱吗,谷歌如何通... 你有没有想过,那个无处不在的安卓系统,它背后是不是也藏着赚钱的秘密呢?没错,今天咱们就来聊聊这个话题...
安卓系统使用恢复模式,轻松解决... 手机突然卡壳了,是不是让你心头一紧?别慌,今天就来给你详细说说安卓系统使用恢复模式的那点事儿。不管是...
安卓系统网卡驱动修复,轻松解决... 你有没有遇到过这种情况?手机里的安卓系统突然间网卡驱动出了问题,上网速度慢得像蜗牛爬,心情也跟着糟糕...
苏州安卓系统开发,引领智能科技... 你有没有想过,在这个科技飞速发展的时代,一款优秀的安卓系统开发能力,简直就像是拥有了魔法一样,能让你...
安卓系统下载电影推荐,精选热门... 亲爱的安卓用户们,你是不是在寻找一些新鲜的电影下载资源?别担心,今天我要给你带来一份特别详细的多角度...
怎么知道电视安卓系统,从生成到... 你有没有想过,家里的电视竟然也能装上安卓系统,就像手机一样方便呢?没错,现在很多智能电视都支持安卓系...
安卓系统是否怕断电,断电下的稳... 你有没有想过,你的安卓手机在电量告急的时候,是不是也会像你一样,慌慌张张地寻找充电宝呢?今天,我们就...
安卓哪个系统杀后台,后台应用被... 你有没有遇到过这种情况:手机里装了那么多应用,后台运行着各种程序,可是一不小心,手机突然卡顿了,或者...
麒麟系统开源吗安卓,基于安卓的... 你有没有听说最近安卓系统界的一个大新闻?那就是麒麟系统竟然开源了!没错,就是那个曾经只属于华为自家手...
安卓车机系统权限,全面了解车辆... 你有没有发现,现在越来越多的汽车都开始装上大屏幕,就像智能手机一样,可以导航、听歌、看视频,简直是个...
电视原生安卓系统下载,下载与体... 亲爱的读者们,你是否曾为家里的电视系统而烦恼?想要升级电视原生安卓系统,却又不知道从何下手?别急,今...