【第九天】C++函数对象/仿函数、谓词、适配器及常见algorithm算法

目录一、函数对象二、谓词1、一元谓词2、二元谓词三、内建函数对象四、适配器1、函数对象 适配器2、函数指针适配器 ptr_fun3、成员函数 作为适配器 mem_fun_ref4、取反适配器五、 常见算法1、遍历算法1for_each遍历算法2transform算法2、查找算法1find算法2find_if算法 条件查找3adjacent_find算法 查找相邻重复元素​4binary_search算法 二分查找法​5count算法 统计元素出现次数​6count_if算法 按条件统计元素出现次数3、排序算法1merge算法 容器元素合并2sort算法 容器元素排序3random_shuffle算法 对指定范围内的元素随机调整次序​4reverse算法 反转指定范围的元素4、拷贝替换算法1copy算法2replace算法3replace_if算法4swap算法 互换两个容器的元素5、算数生成算法1accumulate算法 计算容器元素累计总和2fill算法 向容器中填满元素​6、 集合算法3set_intersection求两个set集合的交集2set_union算法 求两个set集合的并集​编辑3set_difference算法 求两个set集合的差集​编辑六、综合案例一、函数对象重载了函数调用运算符()的类实例化的对象叫函数对象也叫仿函数。如果函数对象 有一个参数 叫一元函数对象/仿函数如果函数对象 有二个参数 叫二元函数对象/仿函数如果函数对象 有三个及以上参数 叫多元函数对象/仿函数注意:1.函数对象(仿函数)是一个类不是一个函数。2.函数对象(仿函数)重裁了()操作符使得它可以像函数一样调用。仿函数概念由来二、谓词返回值为bool类型的普通函数或仿函数都叫谓词。如果谓词 有一个参数 叫一元谓词如果谓词 有二个参数 叫二元谓词一般没有多元谓词1、一元谓词用于查找头文件algorithm提供find_if算法策略2、二元谓词用于排序 头文件algorithm提供sort算法策略#include iostream #includevector #includealgorithm using namespace std; bool myGreater(int n1,int n2) { return n1n2; } class MyGreater { public: bool operator()(int n1,int n2) { return n1n2; } }; void printVectorInt(vectorint v) { vectorint::iterator it; for(itv.begin();it!v.end();it) { cout*it ; } coutendl; } void test() { //sort排序 vectorint v; v.push_back(3); v.push_back(1); v.push_back(5); v.push_back(2); v.push_back(4); printVectorInt(v); sort(v.begin(),v.end());//顺序 printVectorInt(v); //倒序 //sort(v.begin(),v.end(),myGreater); sort(v.begin(),v.end(),MyGreater()); printVectorInt(v); } int main(int argc, char *argv[]) { test(); return 0; }关键代码及运行结果三、内建函数对象定义系统提供好的 函数对象。实质是类模板6个算数类函数对象,除了negate是一元运算其他都是二元运算templateclass T T plusT//加法仿函数templateclass T T minusT//减法仿函数templateclass T T multipliesT//乘法仿函数templateclass T T dividesT//除法仿函数templateclass T T modulusT//取模仿函数templateclass T T negateT//取反仿函数6个关系运算类函数对象,每一种都是二元运算templateclass T bool equal_toT//等于templateclass T bool not_equal_toT//不等于templateclass T bool greaterT//大于templateclass T bool greater_equalT//大于等于templateclass T bool lessT//小于templateclass T bool less_equalT//小于等于逻辑运算类运算函数,not为一元运算其余为二元运算templateclass T bool logical_andT//逻辑与templateclass T bool logical_orT//逻辑或templateclass T bool logical_notT//逻辑非一元谓词查找用内建函数实现将二元谓词排序用内建函数对象实现四、适配器适配器 为算法 提供接口。1、函数对象 适配器2、函数指针适配器 ptr_fun3、成员函数 作为适配器 mem_fun_ref4、取反适配器not1函数一元取反not2函数 二元取反五、 常见算法头文件#includealgorithm适用于随机访问迭代器。1、遍历算法1for_each遍历算法遍历容器元素for_each(iterator beg, iterator end, _callback);param beg 开始迭代器param end 结束迭代器param _callback 函数回调或者函数对象return 函数对象2transform算法将指定容器区间元素搬运到另一容器中transform(iterator beg1, iterator end1, iterator beg2, _callbakc)注意 : transform 不会给目标容器分配内存所以需要我们提前分配好内存param beg1 源容器开始迭代器param end1 源容器结束迭代器param beg2 目标容器开始迭代器param _cakkback 回调函数或者函数对象return 返回目标容器迭代器2、查找算法1find算法查找元素find(iterator beg, iterator end, value)param beg 容器开始迭代器param end 容器结束迭代器param value 查找的元素return 返回查找元素的位置查找基本类型数据查找自定义类型数据#include iostream #includestring #includevector #includealgorithm using namespace std; class Person { friend void test(); private: int num; string name; public: Person(){} Person(int num,string name) { this-numnum; this-namename; } //重载提供比较策略 bool operator(const Person ob) { return ((ob.namethis-name)(ob.numthis-num)); } }; void test() { vectorPerson v; v.push_back(Person(3,tom)); v.push_back(Person(1,bob)); v.push_back(Person(5,张三)); v.push_back(Person(2,小明)); v.push_back(Person(1,小红)); vectorPerson::iterator ret; //find 查找自定义数据类型 需要重载 retfind(v.begin(),v.end(),Person(5,张三)); if(ret!v.end()) { cout找到元素:(*ret).num (*ret).nameendl; } } int main(int argc, char *argv[]) { test(); return 0; }主函数代码及运行结果2find_if算法 条件查找find_if(iterator beg, iterator end, _callback)param beg 容器开始迭代器param end 容器结束迭代器param callback 回调函数或者谓词(返回bool类型的函数对象)return bool 查找返回true 否则false3adjacent_find算法 查找相邻重复元素adjacent_find(iterator beg, iterator end, _callback);param beg 容器开始迭代器param end 容器结束迭代器param _callback 回调函数或者谓词(返回bool类型的函数对象)return 返回相邻元素的第一个位置的迭代器4binary_search算法 二分查找法bool binary_search(iterator beg, iterator end, value);注意: 必须在有序序列中使用在无序序列中不可用。param beg 容器开始迭代器param end 容器结束迭代器param value 查找的元素return bool 查找返回true 否则false5count算法 统计元素出现次数count(iterator beg, iterator end, value);param beg 容器开始迭代器param end 容器结束迭代器param value 要统计的元素return int返回元素个数6count_if算法 按条件统计元素出现次数param beg 容器开始迭代器param end 容器结束迭代器param callback 回调函数或者谓词(返回bool类型的函数对象)return int返回元素个数3、排序算法1merge算法 容器元素合并merge算法 容器元素合并并存储到另一容器中merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterat or dest)注意:两个容器必须是有序的合并后的容器仍然有序目标容器需预留空间。param beg1 容器1开始迭代器param end1 容器1结束迭代器param beg2 容器2开始迭代器param end2 容器2结束迭代器param dest 目标容器开始迭代器2sort算法 容器元素排序sort算法 容器元素排序 sort(iterator beg, iterator end, _callback)param beg 容器1开始迭代器param end 容器1结束迭代器param _callback 回调函数或者谓词(返回bool类型的函数对象)3random_shuffle算法 对指定范围内的元素随机调整次序random_shuffle(iterator beg, iterator end)param beg 容器开始迭代器param end 容器结束迭代器4reverse算法 反转指定范围的元素reverse(iterator beg, iterator end)param beg 容器开始迭代器param end 容器结束迭代器4、拷贝替换算法1copy算法copy算法 将容器内指定范围的元素拷贝到另一容器中copy(iterator beg, iterator end, iterator destparam beg 容器开始迭代器param end 容器结束迭代器param dest 目标起始迭代器copy提升2replace算法将容器内指定范围的旧元素修改为新元素replace(iterator beg, iterator end, oldvalue, newvalue)param beg 容器开始迭代器param end 容器结束迭代器param oldvalue 旧元素param oldvalue 新元素3replace_if算法replace_if算法 将容器内指定范围满足条件的元素替换为新元素replace_if(iterator beg, iterator end, _callback, newvalue)param beg 容器开始迭代器param end 容器结束迭代器param callback函数回调或者谓词(返回Bool类型的函数对象)param oldvalue 新元素4swap算法 互换两个容器的元素swap(container c1, container c2)param c1容器param c2容器25、算数生成算法1accumulate算法 计算容器元素累计总和accumulate(iterator beg, iterator end, value)param beg 容器开始迭代器param end 容器结束迭代器param value追加值 求和完后 value2fill算法 向容器中填满元素fill(iterator beg, iterator end, value)param beg 容器开始迭代器param end 容器结束迭代器param value 填充元素6、 集合算法3set_intersection求两个set集合的交集set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)注意:两个集合必须是有序序列param beg1 容器1开始迭代器param end1 容器1结束迭代器param beg2 容器2开始迭代器param end2 容器2结束迭代器param dest 目标容器开始迭代器return 目标容器的最后元素下一位置的迭代器地址2set_union算法 求两个set集合的并集set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)注意:两个集合必须是有序序列param beg1 容器1开始迭代器param end1 容器1结束迭代器param beg2 容器2开始迭代器param end2 容器2结束迭代器param dest 目标容器开始迭代器return 目标容器的最后元素下一位置的迭代器地址3set_difference算法 求两个set集合的差集set_difference(iterator beg1, iterator end1, iterator beg2, iterator end 2, iterator dest)注意:两个集合必须是有序序列param beg1 容器1开始迭代器param end1 容器1结束迭代器param beg2 容器2开始迭代器param end2 容器2结束迭代器param dest 目标容器开始迭代器return 目标容器的最后一个元素的迭代器地址六、综合案例某市举行一场演讲比赛共有24个人参加。比赛共三轮前两轮为淘汰赛第三轮为决 赛。比赛方式分组比赛每组6个人选手每次要随机分组进行比赛第一轮分为4个小组每组6个人。比如编号为: 100-123. 整体进行抽签 draw后顺序演讲。当小组演讲完后淘汰组内排名最后的三个选手然后 继续下一个小组的比赛。第二轮分为2个小组每组6人。比赛完毕淘汰组内排名最后的三个选手然后继续下一 个小组的比赛。第三轮只剩下1组6个人本轮为决赛选出前三名。比赛评分10个评委打分去除最 低、最高分求平均分每个选手演讲完由10个评委分别打分。该选手的最终得分是去掉一 个最高分和一个最低分求得剩下的8个成绩的平均分。选手的名次按得分降序排列。需求分析 1) 产生选手 ABCDEFGHIJKLMNOPQRSTUVWX 姓名、得分选手编 号实现思路:需要把选手信息、选手得分信息、选手比赛抽签信息、选手的晋级信息保存在容器中需要涉及到各个容器的选型。选手可以设计一个类Speaker姓名和得分所有选手的编号可以单独放在一个vector容器中做抽签用-所有选手编号和选手信息可以放在map容器内。#include iostream #includestring #includevector #includemap #includealgorithm #includestdlib.h #includetime.h #includedeque using namespace std; class player { friend void play(int index,vectorint v, mapint,player m, vectorint v1); private: int num; string name; float score[3]; public: player(){} player(int num,string name) { this-namename; this-numnum; } }; void createPlayer(vectorint v,mapint,player m) { string seednameABCDEFGHIJKLMNOPQRSTUVWX; for(int i0;i24;i) { string tmpname选手; tmpnameseedname[i]; int numi; v.push_back(num); m.insert(make_pair(num,player(num,tmpname))); } } void play(int index,vectorint v,mapint,player m,vectorint v1) { //选手编号随机分组 srand(time(NULL)); random_shuffle(v.begin(),v.end()); multimapfloat,int,greaterfloat mul;//存放每组的分数‐‐编号 vectorint::iterator itv.begin(); int count0; cout-------第index轮比赛-------endl; //每名选手比赛 for(;it!v.end();it) { count; //定义deque容器 存放评委打分 dequefloat d; int i0; for(;i10;i) { d.push_back((float)(rand()%4160)); } //排序 sort(d.begin(),d.end()); //去掉最高、最低分 d.pop_front(); d.pop_back(); //求平均分 float avgaccumulate(d.begin(),d.end(),0)/d.size(); //将平均分 赋值给m中选手 m[*it].score[index-1]avg; mul.insert(make_pair(avg, *it)); if(count%60)//刚好一组 { cout\t第count/6组的晋级名单:endl; int i0; multimapfloat,int,greaterfloat::iterator mitmul.begin(); for(;i3;i,mit) { v1.push_back( (*mit).second); cout\t\t(*mit).second (*mit).firstendl; } cout\t第count/6组的得分情况:endl; mitmul.begin(); for(int i0;i6;i,mit) { int num(*mit).second; cout\t\tnum m[num].name m[num].score[index-1]endl; } mul.clear(); } } } void test() { vectorint v; mapint,player m; //创建选手 createPlayer(v,m); vectorint v1;//存放晋级选手的编号 play(1,v,m,v1); vectorint v2;//存放晋级选手的编号 play(2,v1,m,v2); vectorint v3;//存放晋级选手的编号 play(3,v2,m,v3); } int main(int argc, char *argv[]) { test(); return 0; }运行结果