[数据结构与算法]STL中的算法

一、函数对象（仿函数）

1.函数对象（仿函数）

#include <iostream>
using namespace std;
//函数对象 （仿函数）
//有参数有返回值有自己的状态
class Myadd {
public:
	int operator () (int v1, int v2) {//模板
		return v1 + v2;
	}
};
class Myprint {
public:
	int count;
	Myprint() {
		count = 0;
	}
	void operator()(string test) {
		cout << test << endl;
		count++;
	}
};
void doPrint(Myprint& mp, string test) {
	mp(test);
}
int main() {
	Myadd myadd;
	cout << myadd(10, 10) << endl;
	Myprint myprint; 
	cout << myprint.count;
	myprint("dhgsgfagfh");
	cout << myprint.count;
	doPrint(myprint, "sdadsadasda");
	cout << myprint.count;
	return 0;
}

2.内建函数对象(算术)

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <functional>//记得头文件
int main() {
	//template<class t>t plus<t>
	//negate 一元仿函数 取反仿函数
	negate<int> n;
	cout << n(50) << endl;
	plus<int> p;
	cout<<p(10, 20)<<endl;
	return 0;
}

3.内建函数对象(关系仿函数）

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <functional>//记得加头文件
int main() {
	vector <int> v;
	v.push_back(1);

	v.push_back(2);

	v.push_back(4);

	v.push_back(6);

	v.push_back(0);
	for (vector <int> ::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << endl;
	}
	sort(v.begin(), v.end(), greater<int>());//匿名对象 用编译器提供的仿函数
	for (vector <int> ::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << endl;
	}
	return 0;
}

4.内建函数对象（逻辑仿函数）

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include <functional>//记得加头文件

//逻辑非 logical_not
int main() {
	vector <bool> v;
	v.push_back(true);
	v.push_back(false);
	v.push_back(true);
	v.push_back(false);
	v.push_back(true);
	for (vector <bool> ::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
	//利用逻辑非 将容器v 搬运到容器v2中并且取反
	vector <bool> v2;
	v2.resize(v.size());
	transform(v.begin(), v.end(),v2.begin(),logical_not<bool>());//logical_not<bool>()//transform是算法,下面有
	for (vector <bool> ::iterator it = v2.begin(); it != v2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
	return 0;
}

二、谓词

bool 类型仿函数

1.一阶谓词

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
class GreatFive {
public:
	bool operator()(int val) {
		return val > 5;
	}

};
int main() {
	vector<int> v;
	for (int i = 0; i < 4; i++) {//函数对象中的bool类型
		v.push_back(i);
	}
	//查找容器中有没有大于5的
	//GreatFive()匿名函数对象
	vector<int> ::iterator it = find_if(v.begin(), v.end(), GreatFive());
	if (it == v.end()) {
		cout << "未找到" << endl;
	}
	return 0;
}

2.二阶谓词

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
class MyCompare {
public:
	bool operator ()(int val1,int val2) {//bool 且含有两个形参
		return val1 > val2;
	}
};
int main() {
	vector<int> v;
	for (int i = 0; i < 4; i++) {
		v.push_back(i);
	}
	sort(v.begin(), v.end());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it ++ ) {
	
		cout << *it << endl;
	}
	//使用函数对象改变函数算法
	sort(v.begin(), v.end(),MyCompare());
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {

		cout << *it << endl;
	}
	return 0;
}

三、算法

记得 #include <functional 头文件

1.常用遍历算法 *find算法

直接查找准确元素

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>//记得加头文件
using namespace std;
//find 找到返回迭代器 找不到返回end（）迭代器 

class person {
public:
	string name;
	int m_age;
	person(int age,string name) {
		this->m_age = age;
		this->name = name;
	}
	//重载==号 让find知道如何对比person类型
	bool operator == (const person &p) {
		if (this->name == p.name && this->m_age == p.m_age) {
			return true;
		}
		else {
			return false;
		}
	}
};
int main() {
	vector <int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	vector<int>::iterator it = find(v.begin(), v.end(),5);//查找是否有5这个元素
	if (it == v.end()) {
		cout << "没有找到！" << endl;

	}
	else {
		cout << "找到！" << endl;
	}
	cout << "--------------------------------------" << endl;
	vector<person> v1;//自定义数据对象
	person p1(1, "aaa");
	person p2(1, "asddsa");
	person p3(1, "aad");
	person p4(1, "sdsa");
	v1.push_back(p1);
	v1.push_back(p2);
	v1.push_back(p3);
	v1.push_back(p4);
	vector<person>::iterator it1 = find(v1.begin(), v1.end(), p2);
	if (it1 == v1.end()) {
		cout << "没有找到！" << endl;

	}
	else {
		cout << "找到！" << endl;
	}
	return 0;
}

2.常用遍历算法 *find_if算法

加谓词判断 条件仿函数 找到一个就break

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class GreatFive {//仿函数//大于5这个条件
public:
	bool operator()(int val) {
		return val > 5;
	}
};
class person {
public:
	person(string name, int age) {
		this->age = age;
		this->name = name;
	}
	string name;
	int age;
	//重载==
	bool operator == (const person &a) {
		if (this->age == a.age &&  this->name==a.name) {
			return true;
		}
		else {
			return false;
		}
	}

};
class Great20 {
public:
	bool operator ()(person& p) {
		return p.age > 20;
	}
};
int main() {
	//查找内置数据类型
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	vector<int>::iterator it =find_if(v.begin(), v.end(), GreatFive());//匿名对象
	if (it == v.end()) {
		cout << "没有找到" << endl;
	}
	else {
		cout<<"找到大于五的数字： " << *it<< endl;
	}
	//自定义数据类型
	vector<person> v1;
	person p1("aaaa", 111);
	person p2("bbb", 11);
	person p3("asdsaa", 12);
	person p4("a564", 1532);
	person p5("asda21a", 142);
	v1.push_back(p1);
	v1.push_back(p2);
	v1.push_back(p3);
	v1.push_back(p4);
	v1.push_back(p5);
	vector<person>::iterator it1 = find_if(v1.begin(), v1.end(), Great20());//谓词 匿名对象
	if (it1 == v1.end()) {
		cout << "没有找到" << endl;
	}
	else {
		cout << "找到age大于20的姓名： " << (*it1).name << endl;
	}
	return 0;
}

3.常用遍历算法 *adjacent_find算法

查找相邻重复元素

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	//查找内置数据类型
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	v.push_back(9);
	vector<int>::iterator it = adjacent_find(v.begin(), v.end());
	if (it == v.end()) {
		cout << "没有找到" << endl;
	}
	else {
		cout<<"找到相邻重复元素" << *it<< endl;
	}
	
	return 0;
}

4.常用遍历算法binary_search

查找指定元素 true false
注意无序序列不可用 无序结果未知
bool binary_search（iterator beg,iterator end,value）;

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
	//查找内置数据类型
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	v.push_back(9);
	bool flag = binary_search(v.begin(), v.end(),5);
	if (flag == false) {
		cout << "没有找到" << endl;
	}
	else {
		cout << "二分查找 找到元素"  << endl;
	}
	//必须是有序序列
	return 0;
}

4.常用算法count

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class person {
public:
	string name;
	int age;
	person(string name, int age) {
		this->age = age;
		this->name = name;
	}
	bool operator ==(const person& p) {
		if (this->age = p.age) {//只对比年龄
			return true;
		}
		else {
			false;
		}
	}
};
int main() {
	vector <int> v;
	v.push_back(10);
	v.push_back(10);
	v.push_back(10);
    v.push_back(10);
	v.push_back(10);
	v.push_back(10);
	int num = count(v.begin(), v.end(), 10);
	cout << "10的元素个数：" << num << endl;
	//自定义数据类型
	vector<person> v1;
	person p1("sdsa", 11);
	person p2("sdsa", 11);
	person p3("sdsa", 11);
	person p4("sdsa", 11);
	person p5("sdsa", 11);
	person p6("sdsa", 11);
	v1.push_back(p1);
	v1.push_back(p2);
	v1.push_back(p3);
	v1.push_back(p4);
	v1.push_back(p5);
	v1.push_back(p6);
    num = count(v1.begin(), v1.end(),p1);//传入元素 不需要具体特征 判断方式通过重载==确定
	cout << "跟p1年龄相同的人数：" << num << endl;
	return 0;
}

常用算法 count_if 同上

5常用排序算法sort

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>//remember
using namespace std;
void myprint(int val) {
	cout << val <<" ";
}
class mycompare {
public:
	int operator() (int val1, int val2){
		return val1 > val2;
	}

};
int main() {
	//查找内置数据类型
	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i);
	}
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), myprint);//函数名称即可
	sort(v.begin(), v.end(),greater<int>());//用内置函数对象
	cout << endl;
	for_each(v.begin(), v.end(), myprint);//函数名称即可
	sort(v.begin(), v.end(), mycompare());//仿函数
	cout << endl;
	for_each(v.begin(), v.end(), myprint);//函数名称即可
	return 0;
}

6.常用排序算法 randoom_shuffle

洗牌打乱顺序 random_shuffle(beg,end)

7.常用排序算法 merge

两个有序容器 整合为另外一个有序容器
注：提前用resize给v3分配空间
merge(beg1, end1, beg2, end2, beg3)

8.常用排序算法 reverse

reverse（beg,end）

9.常用拷贝替换算法 copy

容器1 --》容器2
记得提前为v2分配大小
copy(beg1,end1,beg2)

10.常用拷贝替换算法 replace

替换所有符合条件的数据
replace(beg,end,20,2000) 20---->2000

11.常用拷贝替换算法 replace_if

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
class great30 {
public:
	void operator ()(int val) {
		cout << val << "";
	}

};
class lessthan30 {
public:
	bool operator ()(int val1) {
		return val1 < 30;
	}
};
int main() {
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	v.push_back(60);
	for_each(v.begin(), v.end(), great30());
	cout << endl;
	replace_if(v.begin(), v.end(), lessthan30(),1000);//第三参数是条件，1000为替换后
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
		cout << *it << " ";
	}
	return 0;
}

12.常用拷贝替换算法 swap

sawp(v1,v2)
注意：v1 v2 为同种类型

13.常用算术生成算法 accumulate

求和
#include <numeric

#include <iostream>
#include <vector>
#include <numeric>//记得头文件
using namespace std;
int main() {
	vector<int> v;
	for (int i = 0; i <= 100; i++) {
		v.push_back(i);
	}
	int total=accumulate(v.begin(), v.end(), 0);
	cout << total;
	return 0;
}

14.常用算术生成算法 fill

用指定数据 填充指定已知大小的容器
v.resize(1000)
fill(beg,end,1000)

15.常用集合算法 set_intersection

求两个容器的交集
注意：
for_each(vTarge.begin(),itEnd, myprint());//这里结束的迭代器他要用itEnd 因为我们自己开的大小可能太大了
vTarge.resize(min(v.size(), v1.size()));//指定大小
#include //记得头文件

#include <iostream>
#include <vector>
#include <algorithm>//记得头文件
using namespace std;
class myprint {
public:
	void operator()(int val) {
		cout << val << " ";
	}
};
int main() {
	vector<int> v;
	vector<int> v1; 
	vector<int> vTarge;
	for (int i = 0; i <= 10; i++) {
		v.push_back(i);
		v1.push_back(i+5);
	}
	vTarge.resize(min(v.size(), v1.size()));//指定大小 
	vector<int> ::iterator itEnd = set_intersection(v1.begin(), v1.end(), v.begin(), v.end(),vTarge.begin());
	for_each(vTarge.begin(), vTarge.end(), myprint());//这里结束的迭代器他要用itEnd 因为我们自己开的大小可能
	cout << endl;
	for_each(vTarge.begin(),itEnd, myprint());//这里结束的迭代器他要用itEnd 因为我们自己开的大小可能太大了
	return 0;
}

16.常用集合算法 set_union

求两个容器的并集
注意：两个集合要是有序的 先开辟空间（v1+v2）
vector ::iterator itEnd =set_union(beg1,end1,brg2,end2,beg3)

17.常用集合算法 set_intersection

求两个容器的差集
v1 v2中分别不是共同交集的部分（顺序不一样结果不一样）
vTarge.resize(max(v.size(), v1.size()));//指定大小