STL Day03常用算法

xiaoxiao2023-03-24 5

1.1 函数对象

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

注意: 1.函数对象(仿函数)是一个类，不是一个函数。 2.函数对象(仿函数)重载了”() ”操作符使得它可以像函数一样调用。分类:假定某个类有一个重载的operator()，而且重载的operator()要求获取一个参数，我们就将这个类称为“一元仿函数”（unary functor）；相反，如果重载的operator()要求获取两个参数，就将这个类称为“二元仿函数”（binary functor）。函数对象的作用主要是什么？STL提供的算法往往都有两个版本，其中一个版本表现出最常用的某种运算，另一版本则允许用户通过template参数的形式来指定所要采取的策略。

函数对象.cpp

//函数对象是重载了函数调用符号的类 class MyPrint { public: MyPrint() { m_Num = 0; } int m_Num; public: void operator() (int num) { cout << num << endl; m_Num++; } }; //函数对象 //重载了()操作符的类实例化的对象，可以像普通函数那样调用,可以有参数，可以有返回值 void test01() { MyPrint myPrint; myPrint(20); } // 函数对象超出了普通函数的概念，可以保存函数的调用状态 void test02() { MyPrint myPrint; myPrint(20); myPrint(20); myPrint(20); cout << myPrint.m_Num << endl; } void doBusiness(MyPrint print,int num) { print(num); } //函数对象作为参数 void test03() { //参数1：匿名函数对象 doBusiness(MyPrint(),30); } 总结： 1、函数对象通常不定义构造函数和析构函数，所以在构造和析构时不会发生任何问题，避免了函数调用的运行时问题。 2、函数对象超出普通函数的概念，函数对象可以有自己的状态 3、函数对象可内联编译，性能好。用函数指针几乎不可能 4、模版函数对象使函数对象具有通用性，这也是它的优势之一 1.2 谓词谓词是指普通函数或重载的operator()返回值是bool类型的函数对象(仿函数)。如果operator接受一个参数，那么叫做一元谓词,如果接受两个参数，那么叫做二元谓词，谓词可作为一个判断式。 1.3 内建函数对象 STL内建了一些函数对象。分为:算数类函数对象,关系运算类函数对象，逻辑运算类仿函数。这些仿函数所产生的对象，用法和一般函数完全相同，当然我们还可以产生无名的临时对象来履行函数功能。使用内建函数对象，需要引入头文件 #include<functional>。

2/3的概念.cpp

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include<algorithm> #include<functional> using namespace std; //1.一元谓词 struct GreaterThan20{ bool operator()(int val){ return val > 20; } }; void test01(){ vector<int> v; v.push_back(20); v.push_back(10); v.push_back(30); v.push_back(40); vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterThan20()); if (it == v.end()){ cout << "没找到!" << endl; } else{ cout << "找到:" << *it << endl; } } //二元谓词 struct MyComparre{ bool operator()(int v1,int v2){ return v1 > v2; } }; void test02(){ vector<int> v; v.push_back(20); v.push_back(10); v.push_back(30); v.push_back(40); for_each(v.begin(), v.end(), [](int val)->void{cout << val << " "; }); sort(v.begin(), v.end(), less<int>() ); //lambda表达式 for_each(v.begin(), v.end(), [](int val)->void{cout << val << " "; }); cout << endl; } 1.4 函数对象适配器函数对象适配器.cpp

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include<string> #include<algorithm> #include<functional> using namespace std; //1. 让自己编写的函数对象继承基类,如果是一元函数对象需要继承unary_function, //如果是二元函数对象继承binary_function //2. 函数对象operator()函数后增加 const //3. 使用bind2nd bind1st //bind2nd其实就将一个二元的函数对象转变为了一元函数对象 struct MyPrint : public binary_function<int,int,void> { void operator()(int v,int v2) const{ cout << "v:" << v << " v2:" << v2 << endl; cout << v + v2 << " "; } }; //如何让for_each算法调用二元函数对象，把二元函数对象转变为一元函数对象 void test01(){ vector<int> v; for (int i = 0; i < 10;i ++){ v.push_back(i + 1); } for_each(v.begin(), v.end(), bind1st(MyPrint(),300)); //bind2nd把300绑定为函数对象的第二个参数 //bind1st把300绑定为函数对象的第一个参数 cout << endl; } //2. 取反适配器 not1 not2 struct GreaterThan5 : public unary_function<int,bool>{ bool operator()(int v) const{ return v > 5; } }; void test02(){ vector<int> v; for (int i = 0; i < 10;i++){ v.push_back(i + 1); } //vector<int>::iterator it = find_if(v.begin(), v.end(), not1(GreaterThan5())); vector<int>::iterator it = find_if(v.begin(), v.end(), not1( bind2nd(greater<int>(),5)) ); if (it == v.end()){ cout << "么有找到!" << endl; } else{ cout << "找到:" << *it << endl; } //排序 sort(v.begin(),v.end(),not2(less<int>())); for_each(v.begin(), v.end(), [](int val){cout << val << " "; }); //not1 对一元谓词取反 //not2 对二元谓词取反 } //3. ptr_fun 函数指针适配器 void MyPrint03(int val,int v2){ cout << val + v2 << " "; } //把一个普通的函数指针适配成函数对象 void test03(){ vector<int> v; for (int i = 0; i < 10; i++){ v.push_back(i + 1); } for_each(v.begin(), v.end(), bind2nd( ptr_fun(MyPrint03), 100)); } //4. 成员函数适配器 mem_fun和mem_fun_ref class Person{ public: Person(string name,int age){ this->mName = name; this->mAge = age; } //打印函数 void ShowPerson(){ cout << "成员函数:" << "Name:" << mName << " Age:" << mAge << endl; } void AgePlus100(){ this->mAge += 100; } public: string mName; int mAge; }; void MyPrint04(Person& p){ cout << "全局函数:" << "Name:" << p.mName << " Age:" << p.mAge << endl; } void test04(){ vector<Person> v1; //创建数据 Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); v1.push_back(p1); v1.push_back(p2); v1.push_back(p3); v1.push_back(p4); for_each(v1.begin(), v1.end(), MyPrint04); cout << "-------------" << endl; //调用成员函数打印 for_each(v1.begin(), v1.end(), mem_fun_ref(&Person::ShowPerson)); for_each(v1.begin(), v1.end(), mem_fun_ref(&Person::AgePlus100)); for_each(v1.begin(), v1.end(), mem_fun_ref(&Person::ShowPerson)); } void test05(){ vector<Person*> v1; //创建数据 Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); v1.push_back(&p1); v1.push_back(&p2); v1.push_back(&p3); v1.push_back(&p4); for_each(v1.begin(), v1.end(), mem_fun(&Person::ShowPerson)); } //mem_fun 如果容器存放的是对象指针，那么用men_fun //如果容器中存放的是对象实体，那么用mem_fun_ref int main(){ //test01(); //test02(); //test03(); //test04(); test05(); system("pause"); return EXIT_SUCCESS; } 2.算法概述算法主要是由头文件<algorithm> <functional> <numeric>组成。 <algorithm>是所有STL头文件中最大的一个,其中常用的功能涉及到比较，交换，查找,遍历，复制，修改，反转，排序，合并等... <numeric>体积很小，只包括在几个序列容器上进行的简单运算的模板函数. <functional> 定义了一些模板类,用以声明函数对象。

3.常用算法遍历

常用遍历算法.cpp

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<algorithm> #include<vector> using namespace std; //1. for_each算法 /* template<class _InIt,class _Fn1> inline _Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func) { for (; _First != _Last; ++_First) _Func(*_First); } */ struct MyPrint01{ MyPrint01(){ mCallNums = 0; } void operator()(int v){ mCallNums++; cout << v << " "; } public: int mCallNums; }; struct MyPrint02{ void operator()(const int& v){ //v += 100; cout << v << " "; } }; void test01(){ vector<int> v; for (int i = 0; i < 10;i++){ v.push_back(i + 1); } MyPrint01 print; MyPrint01 m = for_each(v.begin(), v.end(), print); cout << "调用次数:" << print.mCallNums << endl; cout << "调用次数:" << m.mCallNums << endl; for_each(v.begin(), v.end(), MyPrint02()); for_each(v.begin(), v.end(), MyPrint02()); } //2. transform 搬运 /* template<class _InIt, class _OutIt, class _Fn1> inline _OutIt _Transform(_InIt _First, _InIt _Last,_OutIt _Dest, _Fn1 _Func) { for (; _First != _Last; ++_First, ++_Dest) *_Dest = _Func(*_First); return (_Dest); } template<class _InIt1,class _InIt2,class _OutIt,class _Fn2> inline _OutIt _Transform(_InIt1 _First1, _InIt1 _Last1,_InIt2 _First2, _OutIt _Dest, _Fn2 _Func) { for (; _First1 != _Last1; ++_First1, ++_First2, ++_Dest) *_Dest = _Func(*_First1, *_First2); return (_Dest); } */ struct Transform1{ int operator()(int v){ return v + 100; } }; void test02(){ vector<int> v; for (int i = 0; i < 10; i++){ v.push_back(i + 1); } vector<int> vTarget; //目标容器 //vTarget.reserve(10); 不可行 vTarget.resize(v.size()); transform(v.begin(), v.end(), vTarget.begin(), Transform1()); for_each(vTarget.begin(), vTarget.end(), [](int val){cout << val << " "; }); } struct Transform2{ int operator()(int v1,int v2){ return v1 + v2; } }; void test03(){ vector<int> v1; vector<int> v2; for (int i = 0; i < 10; i++){ v1.push_back(i + 100); v2.push_back(i + 200); } vector<int> vTarget; //目标容器 vTarget.resize(v1.size()); transform(v1.begin(), v1.end(), v2.begin(), vTarget.begin(), Transform2()); for_each(vTarget.begin(), vTarget.end(), [](int val){cout << val << " "; }); } int main(){ //test01(); //test02(); test03(); system("pause"); return EXIT_SUCCESS; } 4.常用查找算法

常用查找算法.cpp

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include<string> #include<algorithm> #include<functional> using namespace std; //1. find find_if //查找基础数据类型 /* template<class _InIt, class _Ty> inline _InIt _Find(_InIt _First, _InIt _Last, const _Ty& _Val, false_type) { // find first matching _Val for (; _First != _Last; ++_First) if (*_First == _Val) break; return (_First); } */ void test01(){ vector<int> v; for (int i = 0; i < 10;i ++){ v.push_back(i + 1); } vector<int>::iterator it = find(v.begin(),v.end(),5); if (it == v.end()){ cout << "没有找到!" << endl; } else{ cout << "找到:" << *it << endl; } } class Person{ public: Person(string name,int age){ this->mName = name; this->mAge = age; } //重载== bool operator==(const Person& p){ if (this->mName == p.mName && this->mAge == p.mAge){ return true; } return false; } //重载< bool operator<(const Person& p) const{ return this->mAge < p.mAge; } public: string mName; int mAge; }; void test02(){ vector<Person> v; //创建数据 Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); vector<Person>::iterator it = find(v.begin(), v.end(), p2); if (it == v.end()){ cout << "没有找到!" << endl; } else{ cout << "找到:" << it->mName <<":" << it->mAge << endl; } } //查找对象指针 struct search_condition : public binary_function<Person*,Person*,bool>{ bool operator()(Person* p,Person* p2) const{ if (p->mName == p2->mName && p->mAge == p2->mAge){ return true; } return false; } }; void test03(){ vector<Person*> v; //创建数据 Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); v.push_back(&p1); v.push_back(&p2); v.push_back(&p3); v.push_back(&p4); Person* p = new Person("bbb",20); vector<Person*>::iterator it = find_if(v.begin(), v.end(), bind2nd(search_condition(),p)); if (it == v.end()){ cout << "找不到!" << endl; } else{ cout << "找到:" << (*it)->mName << ":" << (*it)->mAge << endl; } } //adjacent_find 查找相邻重复元素 1 2 3 3 4 5 6 void test04(){ vector<int> v; v.push_back(1); v.push_back(2); v.push_back(5); v.push_back(3); v.push_back(4); v.push_back(4); vector<int>::iterator it = adjacent_find(v.begin(),v.end()); if (it == v.end()){ cout << "找不到!" << endl; } else{ cout << "找到:" << *it << endl; } } //bool::binary_search 二分查找法需要序列有序的 void test05(){ vector<int> v; for (int i = 0; i < 10; i++){ v.push_back(i + 1); } bool flag = binary_search(v.begin(), v.end(), 5); if (flag){ cout << "找到!" << endl; } else{ cout << "没有找到!" << endl; } } //binary_search void test06(){ vector<Person> v; //创建数据 Person p1("aaa", 10); Person p2("bbb", 20); Person p3("ccc", 30); Person p4("ddd", 40); v.push_back(p1); v.push_back(p2); v.push_back(p3); v.push_back(p4); if (binary_search(v.begin(), v.end(), p2)){ cout << "摘到!" << endl; } else{ cout << "摘不到!" << endl; } } //count count_if 统计元素的个数 struct GreaterTwo{ bool operator()(int v){ return v > 2; } }; void test07(){ vector<int> v; v.push_back(1); v.push_back(2); v.push_back(5); v.push_back(3); v.push_back(4); v.push_back(4); /* for (; _First != _Last; ++_First) if (*_First == _Val) ++_Count; */ int num = count(v.begin(), v.end(),4); cout << "NUM:" << num << endl; num = count_if(v.begin(), v.end(), GreaterTwo()); cout << "NUM:" << num << endl; } int main(){ //test01(); //test02(); //test03(); //test04(); //test05(); //test06(); test07(); system("pause"); return EXIT_SUCCESS; }

5 常用排序算法

常用排序算法.cpp

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include<algorithm> #include<string> #include<functional> #include<list> using namespace std; //1. merge 合并两个有序序序列 struct MyCompare{ bool operator()(int v1,int v2){ return v1 > v2; } }; void test01(){ vector<int> v1; vector<int> v2; for (int i = 10; i > 0; i --){ v1.push_back(i); v2.push_back(i + 1); } vector<int> vtarget; vtarget.resize(v1.size() + v2.size()); //默认从小到大 //merge(v1.begin(),v1.end(),v2.begin(),v2.end(),vtarget.begin()); //从大到小 merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vtarget.begin(), MyCompare()); for_each(vtarget.begin(), vtarget.end(), [](int v){cout << v << " "; }); } //sort算法 void test02(){ #if 0 //使用sort算法容器必须支持随机访问 list<int> mylist; mylist.push_back(10); mylist.push_back(70); mylist.push_back(50); mylist.push_back(20); sort(mylist.begin(), mylist.end()); #endif vector<int> v; v.push_back(10); v.push_back(70); v.push_back(50); v.push_back(20); //sort默认从小到大排序 sort(v.begin(),v.end()); sort(v.begin(), v.end(),greater<int>()); for_each(v.begin(), v.end(), [](int val){cout << val << " "; }); } //random_shuffle 洗牌，打乱容器中元素的次序 void test03(){ vector<int> v; v.push_back(10); v.push_back(70); v.push_back(50); v.push_back(20); for_each(v.begin(), v.end(), [](int val){cout << val << " "; }); cout << endl; random_shuffle(v.begin(),v.end()); for_each(v.begin(), v.end(), [](int val){cout << val << " "; }); cout << endl; } //reverse 反转 void test04(){ vector<int> v; v.push_back(10); v.push_back(70); v.push_back(50); v.push_back(20); for_each(v.begin(), v.end(), [](int val){cout << val << " "; }); cout << endl; reverse(v.begin(),v.end()); for_each(v.begin(), v.end(), [](int val){cout << val << " "; }); cout << endl; } int main(){ //test01(); //test02(); //test03(); test04(); system("pause"); return EXIT_SUCCESS; }

6 常用拷贝和替换算法

常用拷贝算法和替换算法.cpp

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include<functional> #include<algorithm> #include<iterator> using namespace std; //copy void test01(){ vector<int> v1; for (int i = 0; i < 10;i++){ v1.push_back(i + 1); } vector<int> v2; v2.resize(v1.size()); copy(v1.begin(), v1.end(), v2.begin()); copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " ")); } //replace bool MyCompare02(int v){ return v > 2; } void test02(){ vector<int> v1; v1.push_back(2); v1.push_back(7); v1.push_back(2); v1.push_back(9); v1.push_back(10); v1.push_back(3); v1.push_back(0); //replace(v1.begin(), v1.end(), 2, 100); replace_if(v1.begin(), v1.end(),MyCompare02,100); copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " ")); } //swap void test03(){ vector<int> v1; vector<int> v2; for (int i = 0; i < 10; i++){ v1.push_back(i + 1); v2.push_back(i); } for_each(v1.begin(), v1.end(), [](int val){cout << val << " "; }); cout << endl; for_each(v2.begin(), v2.end(), [](int val){cout << val << " "; }); cout << endl; swap(v1, v2); cout << "------------" << endl; for_each(v1.begin(), v1.end(), [](int val){cout << val << " "; }); cout << endl; for_each(v2.begin(), v2.end(), [](int val){cout << val << " "; }); cout << endl; } int main(){ //test01(); //test02(); test03(); system("pause"); return EXIT_SUCCESS; } 7 常用算数生成算法

常用算数生成算法.cpp

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include<algorithm> #include<numeric> #include<iterator> using namespace std; //accumulate 累加容器中元素 void test01(){ vector<int> v; for (int i = 0; i <= 100;i++){ v.push_back(i); } int total = accumulate(v.begin(),v.end(),0); cout << "total:" << total << endl; } //fill填充 void test02(){ vector<int> v; v.resize(10); fill(v.begin(), v.end(), 100); copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")); } int main(){ //test01(); test02(); system("pause"); return EXIT_SUCCESS; } 8 常用集合算法

常用集合算法.cpp

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include<functional> #include<iterator> #include<algorithm> using namespace std; //求交集 set_intersection void test01(){ vector<int> v1; vector<int> v2; for (int i = 0; i < 10;i++){ v1.push_back(i); } for (int i = 5; i < 15;i ++){ v2.push_back(i); } vector<int> v3; v3.resize(min(v1.size(),v2.size())); vector<int>::iterator MyEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); copy(v3.begin(), MyEnd, ostream_iterator<int>(cout, " ")); } //求并集 set_union void test02(){ vector<int> v1; vector<int> v2; for (int i = 0; i < 10; i++){ v1.push_back(i); } for (int i = 5; i < 15; i++){ v2.push_back(i); } vector<int> v3; v3.resize(v1.size()+ v2.size()); vector<int>::iterator MyEnd = set_union(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin()); copy(v3.begin(), MyEnd, ostream_iterator<int>(cout, " ")); } //求差集 set_difference void test03(){ vector<int> v1; vector<int> v2; for (int i = 0; i < 10; i++){ v1.push_back(i); } for (int i = 5; i < 15; i++){ v2.push_back(i); } vector<int> v3; v3.resize(max(v1.size(),v2.size())); vector<int>::iterator MyEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); copy(v3.begin(), MyEnd, ostream_iterator<int>(cout, " ")); } int main(){ //test01(); //test02(); test03(); system("pause"); return EXIT_SUCCESS; } 演讲比赛—综合案例.cpp

#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<map> #include<vector> #include<string> #include<algorithm> #include<deque> #include<time.h> #include<numeric> #include<functional> using namespace std; //选手类 class Player{ public: string mName; int mScore[3]; }; //创建24名选手 void Create_Player(vector<int>& v, map<int,Player>& m){ string seedName = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; for (int i = 0; i < 24; i ++){ Player player; player.mName = "选手"; player.mName += seedName[i]; for (int j = 0; j < 3;j++){ player.mScore[j] = 0; } //生成当前选手的编号 int ID = 100 + i; //保存编号 v.push_back(ID); //保存选手信息 m.insert(make_pair(ID,player)); } } /* 选手抽签选手比赛查看比赛结果 */ //抽签 void Draw(vector<int>& v){ random_shuffle(v.begin(),v.end()); } //比赛 void SpeechContest(int index,vector<int>& vIDs, map<int, Player>& m,vector<int>& vLevelUp){ srand((unsigned int)time(NULL)); //保存分组的信息,指定按照分数从大到小排列 multimap<int, int, greater<int>> mGroup; //遍历每一个选手 for (vector<int>::iterator it = vIDs.begin(); it != vIDs.end(); it ++){ //保存选手的分数 deque<int> dScore; //对每一个选手打分 for (int i = 0; i < 10; i++){ int score = rand() % 40 + 60; dScore.push_back(score); } //排序 sort(dScore.begin(), dScore.end()); //去除最高分去除最低分 dScore.pop_back(); dScore.pop_front(); //求总分 int totalScore = accumulate(dScore.begin(), dScore.end(), 0); //求平均分 int avgScore = totalScore / dScore.size(); //保存选手得分 m[*it].mScore[index - 1] = avgScore; //放到分组中 mGroup.insert(make_pair(avgScore,*it)); if (mGroup.size() == 6){ int index = 0; for (multimap<int, int, greater<int>>::iterator it = mGroup.begin(); it != mGroup.end() && index < 3; it++,index++){ vLevelUp.push_back(it->second); } mGroup.clear(); } } } //显示晋级名单 void ShowLevelUpPeople(int index,vector<int>& vLevel, map<int, Player>& m){ cout << "第" << index << "轮晋级名单:" << endl; for (vector<int>::iterator it = vLevel.begin(); it != vLevel.end(); it ++){ cout << "Name:" << m[*it].mName << " 分数:" << m[*it].mScore[index - 1] << endl; } cout << "------打印信息结束------" << endl; } int main(){ //创建选手 vector<int> v1; //选手编号 vector<int> v2; vector<int> v3; vector<int> v4; //选手信息 map<int, Player> mPlist; Create_Player(v1, mPlist); //第一轮比赛 Draw(v1); //抽签 SpeechContest(1,v1, mPlist, v2); ShowLevelUpPeople(1,v2,mPlist); //第二轮 Draw(v2); //抽签 SpeechContest(2, v2, mPlist, v3); ShowLevelUpPeople(2, v3, mPlist); //第三轮 Draw(v3); //抽签 SpeechContest(3, v3, mPlist, v4); ShowLevelUpPeople(3, v4, mPlist); system("pause"); return EXIT_SUCCESS; }

转载请注明原文地址: https://ju.6miu.com/read-1201442.html

最新回复(0)