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

相关内容

热门资讯

安卓系统写脚本软件下载,基于安... 你有没有想过,你的安卓手机或者平板电脑,除了用来刷剧、玩游戏,还能变成一个强大的工作助手呢?没错,就...
安卓系统有哪些机型好,探索顶级... 你有没有想过,安卓系统里的手机型号那么多,哪一款才是最适合你的呢?别急,今天我就来给你好好盘点看看安...
安卓系统之间如何互传,安卓设备... 你是不是也和我一样,手机里存了那么多好东西,却苦于不能和好友分享呢?别急,今天就来教你怎么用安卓系统...
安卓系统启动修改工具,安卓系统... 你有没有想过,你的安卓手机启动速度竟然可以像火箭一样快?没错,这就是今天我要跟你分享的神秘工具——安...
安卓系统版本号历史,从初生到繁... 你有没有发现,每次打开手机,那系统版本号总是一闪而过,好像在悄悄告诉你:“我可是有故事的哦!”今天,...
小米改安卓系统软件,安卓系统软... 你知道吗?最近小米手机界可是掀起了一阵小小的风波呢!那就是小米对安卓系统软件的一次大改版。这可不是什...
安卓系统控制流量app,安卓系... 你有没有发现,手机里的流量就像小河里的水,不知不觉就流光了?别急,今天就来给你揭秘一款神奇的安卓系统...
hl2240安卓系统,功能解析... 你有没有发现,最近你的手机系统更新换代的速度简直就像坐上了火箭呢?今天,就让我带你来一探究竟,看看这...
iqoo刷原生安卓系统,还原纯... 最近手机圈里可是热闹非凡呢!一款名为iqoo的新品手机,凭借其强大的性能和独特的刷机功能,吸引了无数...
安卓系统我的读书入口,我的读书... 亲爱的手机控们,你是否也有这样的体验:每天手机不离手,却总是找不到心仪的读书应用?别急,今天我要给你...
搭载安卓9系统的手机,新一代智... 你有没有发现,最近市面上新出的手机,好像都开始搭载安卓9系统了呢?这可真是让人眼前一亮啊!今天,就让...
电脑模拟安卓系统win7系统,... 你有没有想过,如果电脑也能像手机一样,随时随地都能玩各种游戏、看视频呢?想象你坐在电脑前,屏幕上突然...
华为系统如何退回安卓,轻松实现... 你有没有想过,手机系统就像是我们生活中的衣服,有时候穿久了,就想换一件新的。比如,你之前用了华为的系...
安卓系统定制防沉迷手机,安卓手... 你有没有发现,现在的手机越来越智能,但随之而来的是沉迷于手机的问题也越来越严重,尤其是对青少年来说。...
安卓系统手机顶部符号,功能解析... 你有没有注意到,每次拿起安卓系统手机,顶部那一排小小的符号总是默默守护着你的屏幕?它们就像是一群小精...
美团餐饮系统安卓版,尽享美食新... 你有没有发现,最近点外卖的时候,手机上那个美团餐饮系统安卓版真是越来越方便了!今天,就让我带你来好好...
新生活cms安卓系统进货系统,... 你知道吗?最近市面上出现了一个超级酷的新玩意儿——新生活CMS安卓系统进货系统!这可是个让商家们眼睛...
安卓系统ai文章生成,探索安卓... 你知道吗?现在手机界的风云变幻,安卓系统可是当之无愧的王者!而且,最近听说安卓系统里还悄悄加入了AI...
推荐安卓车载导航系统,安卓平台... 你有没有想过,开车的时候,如果没有导航系统,那可真是像在茫茫大海中航行,没有指南针的感觉呢?别急,今...
安卓系统的地图怎样下载,下载与... 你有没有发现,现在不管去哪里,手机地图都成了我们的好帮手?尤其是安卓系统的地图,功能强大,用起来超级...