首页 > stl算法
头像
阅遍星辰任是少年
编辑于 2020-03-09 17:20
+ 关注

stl算法

算法主要由
<algorithm>是所有stl头文件中最大的一个,其中涉及功能到比较,交换,查找边历,复制,修改,反转,排序,合并等
<numeric>体积很小,只包括在几个序列容器上进行简单运算的模板函数
<functional>定义了一些模板类,用以声明函数对象
1、常用边历算法
for_each算法
  • 正向遍历,逆向遍历
  • for_each绑定参数
  • for_each修改元素值
  • for_each返回值
transform算法
容器,目标容器,算法;
#include<algorithm>
#include<iostream>
#include<vector>
#include<functional>
#include<numeric>
using namespace std;

//for_each算法
class  print{
public:
	print() :count(0){}
	void operator()(int v){
		cout << v << " ";

	}
	int count;
};
void test01()
{
	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);

	}
	/*
	template<class _InIt,
	class _Fn1> inline
	_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
	{	// perform function for each element
	_DEBUG_RANGE(_First, _Last);
	_DEBUG_POINTER(_Func);
	_For_each(_Unchecked(_First), _Unchecked(_Last), _Func);

	return (_STD move(_Func));
	}*/
	//他是拷贝过来的
	print p1;
	print p2=for_each(v.begin(), v.end(), p1);
	cout << endl;
	cout << "count:" << p1.count << endl;
	cout << "count:" << p2.count << endl;


	
}
//transform算法
class myplus100{
	int operator()(int v){
		return v + 100;
	}
};
class myminute{
public:
	int operator()(int v1, int v2){
		return v2 - v1;
	}
};
void test02()
{
	/*
	vector<int> v1,v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);

	}
	//第一种方式,一个容器经过运算,把结果放进目标容器v2
	v2.resize(v1.size());
	for_each(v2.begin(), v2.end(), print());
	cout << endl;
	transform(v1.begin(), v1.end(), v2.begin(), myplus100());
	for_each(v2.begin(), v2.end(), print());
	cout << endl;*/
	//第二种方式
	vector<int> v3, v4, v5;
	for (int i = 0; i < 10; i++)
	{
		v3.push_back(i);
		v4.push_back(i+1);

	}
	v5.resize(v3.size());
	for_each(v5.begin(), v5.end(), print());
	cout << endl;
	transform(v3.begin(), v3.end(), v4.begin(), v5.begin(), myminute());
	for_each(v5.begin(), v5.end(), print());
	cout << endl;

}
int main()
{
	test02();
	return EXIT_SUCCESS;
}
2、常用的查找算法
  • find算法
  • find_if算法
  • count算法
  • count_if算法
  • adiacent_find算法,返回相零的重复元素出现的第一个位置
  • binary_search算法,二分查找法,需要容器中元素有序,需要排序
  • #include<iostream>
    #include<numeric>
    #include<vector>
    #include<algorithm>
    
    using namespace std;
    
    class print{
    public:
    	void operator()(int v){
    		/*if (v!=0)
    		cout << v << " ";
    		*/
    		cout << v << " ";
    	}
    };
    
    //find
    void test01()
    {
    	vector<int> v;
    	v.push_back(8);
    	v.push_back(4);
    	v.push_back(5);
    	v.push_back(3);
    	/*
    	template<class _InIt,
    	class _Ty> inline
    	_InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)
    	{	// find first matching _Val
    	_DEBUG_RANGE(_First, _Last);
    	return (_Rechecked(_First,
    		_Find(_Unchecked(_First), _Unchecked(_Last), _Val)));
    	}*/
    	vector<int>::iterator pos = find(v.begin(), v.end(), 4);
    	if (pos == v.end())
    	{
    		cout << "没有找到" << endl;
    	}
    	else
    	{
    		cout << *pos << endl;
    	}
    	//for_each(v.begin(), v.end(), print());
    }
    
    class student{
    public:
    	student(int id, int age) :id(id), age(age){}
    	int id;
    	int age;
    	bool operator==(const student& s){
    		if (this->id == s.id && this->age == age)
    		{
    			return true;
    		}
    		else
    		{
    			return false;
    		}
    		return this->id == s.id && this->age == s.age;
    	}
    };
    
    
    
    //查找对象
    void test02()
    {
    	vector<student> v;
    	student s1(1, 2), s2(3, 4), s3(5, 6);
    	v.push_back(s1);
    	v.push_back(s2);
    	v.push_back(s3);
    	vector<student>::iterator pos = find(v.begin(), v.end(), s1);
    	if (pos != v.end()){
    		cout << "zhaodao" << pos->age <<" "<< pos->id << endl;
    	}
    	else{
    		cout << "没有找到" << endl;
    	}
    }
    //find_if
    class mycompare03{
    public:
    	bool operator()(int v){
    		if (v > 2){
    			return true;
    		}
    		else{
    			return false;
    		}
    	}
    };
    void test03()
    {
    	vector<int> v;
    	v.push_back(8);
    	v.push_back(4);
    	v.push_back(5);
    	v.push_back(3);
    	//find_if(v.begin(), v.end(), mycompare03());
    	vector<int>::iterator pos = find_if(v.begin(), v.end(), mycompare03());
    	if (pos == v.end())
    	{
    		cout << "没有找到" << endl;
    	}
    	else
    	{
    		cout << *pos << endl;
    	}
    }
    //ad_jacent_find查找相邻重复元素,并返回第一个重复元素出现的位置
    void test04()
    {
    	vector<int> v;
    	v.push_back(8);
    	v.push_back(4);
    	v.push_back(4);
    	v.push_back(5);
    	v.push_back(3);
    	/*_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last, _Pr _Pred)
    	{	// find first satisfying _Pred with successor
    	_DEBUG_RANGE(_First, _Last);
    	_DEBUG_POINTER(_Pred);
    	return (_Rechecked(_First,
    		_Adjacent_find(_Unchecked(_First), _Unchecked(_Last), _Pred)));
    	}*/
    	vector<int>::iterator pos = adjacent_find(v.begin(), v.end());
    	if (pos == v.end())
    	{
    		cout << "没有找到" << endl;
    	}
    	else
    	{
    		cout << *pos << endl;
    	}
    }
    
    //binary_search二分查找法
    void test05()
    {
    	//binary_search需要对有序的元素查找
    	vector<int> v;
    	v.push_back(8);
    	v.push_back(4);
    	v.push_back(5);
    	v.push_back(3);
    	sort(v.begin(), v.end());
    
    	/*template<class _FwdIt,
    	class _Ty> inline
    	bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val)
    	{	// test if _Val equivalent to some element, using operator<
    	return (_STD binary_search(_First, _Last, _Val, less<>()));
    	}*/
    	bool flag = binary_search(v.begin(), v.end(),11);
    	if (flag)
    	{
    		cout << flag << endl;
    	}
    	else
    	{
    		cout << "没有找到" << endl;
    	}
    }
    
    class mycompare06{
    public:
    	bool operator()(int v){
    		return v > 2;
    	}
    };
    //count count_if
    void test06()
    {
    	//统计那个元素出现的次数
    	vector<int> v;
    	v.push_back(3);
    	v.push_back(8);
    	v.push_back(4);
    	v.push_back(5);
    	v.push_back(3);
    	sort(v.begin(), v.end());
    
    	int n=count(v.begin(), v.end(),3);
    	cout << "n" << n << endl;
        n = count_if(v.begin(), v.end(), mycompare06());
    	cout << "n" << n << endl;
    	
    }
    
    int main()
    {
        test06();
    	return EXIT_SUCCESS;
    }
    


3、常用的排序算法(需要容器支持随机访问,list不可以)
  • sort算法
  • merge算法(将两个容器中元素合并,放在第三个容器中,两个容器中元素必须是有序的)
    • merge(iterator beg,iterator end,iterator beg,iterator end,iterator dest)
  • random_shuffle算法(将容器元素打乱)
  • reverse算法(将容器中元素反转)
4、常用的拷贝替换算法
  • copy算法
  • replace算法(替换)
    • replace(iterator beg,iterator end,oldvalue,newvalue)
  • replace_if算法(把所有满足条件的元素全部替换)
  • swap算法(交换)
#include<iostream>
#include<numeric>
#include<vector>
#include<algorithm>

using namespace std;

class print{
public:
	void operator()(int v){
		/*if (v!=0)
		cout << v << " ";
		*/
		cout << v << " ";
	}
};

//copy
void test01()
{
	vector<int> v1, v2;
	for (int i = 0; i <= 10; i++)
	{
		v1.push_back(i);
	}
	v2.resize(v1.size());
	copy(v1.begin(), v1.end(), v2.begin());
	for_each(v2.begin(), v2.end(), print());
}
//replace
class mycompare02{
public:
	bool operator() (int v){
		return v > 5;
	}
};
void test02()
{
	vector<int> v1;
	for (int i = 0; i <= 10; i++)
	{
		v1.push_back(i);
	}	
	for_each(v1.begin(), v1.end(), print());
	cout << endl;
	replace(v1.begin(), v1.end(), 3, 100);
	for_each(v1.begin(), v1.end(), print());
	cout << endl;
	//replace_if
	replace_if(v1.begin(), v1.end(), mycompare02(), 365);
	for_each(v1.begin(), v1.end(), print());
	cout << endl;

	//swap
	vector<int> v2;
	for (int i = 0; i <= 10; i++)
	{
		v2.push_back(i);
	}
	cout << "swap front ::" << endl;
	for_each(v2.begin(), v2.end(), print());
	swap(v1, v2);
	cout << endl;
	cout << "swap back ::" << endl;
	for_each(v2.begin(), v2.end(), print());


}
int main()
{
    test02();
	return EXIT_SUCCESS;
}
6、常用的算术生成算法<numeric>
accumulate算法(将容器中元素累加)
fill算法
#include<iostream>
#include<numeric>
#include<vector>
#include<algorithm>

using namespace std;

void test01()
{
	vector<int> v;
	for (int i=0; i <= 100; i++)
	{
		v.push_back(i);
	}
	//将元素中的值加完再加100
	int a=accumulate(v.begin(), v.end(), 100);
	cout << "n" << a<< endl;
}

class print{
public:
	void operator()(int v){
		cout << v << " ";
	}
};
void test02()
{
	vector<int> v;
	v.resize(100);//reserve(100)只开空间,未初始化
	fill(v.begin(), v.end(), 100);
	cout << "size" << v.size()<< endl;
	for_each(v.begin(), v.end(), print());
}
int main()
{
	test02();
	return EXIT_SUCCESS;
}                                                                                                                         
7、常用的集合算法
set_intersection算法(求交集)
set_union算法(并集)
set_difference算法(求两个集合的差集)
#include<iostream>
#include<numeric>
#include<vector>
#include<algorithm>

using namespace std;

class print{
public:
	void operator()(int v){
		/*if (v!=0)
		cout << v << " ";
		*/
	}
};

//求两个集合的交集
void test01()
{
	vector<int> v1,v2,v3;
	for (int i=0; i <= 10; i++)
	{
		v1.push_back(i);
	}
	for (int i = 12; i <= 30; i++)
	{
		v2.push_back(i);
	}
	v3.resi***(v1.size(), v2.size()));
	//迭代器指向最后一个元素的shang一个位置
	vector<int>::iterator myEnd=set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),v3.begin());
	for_each(v3.begin(),myEnd, print());
}
//求两个元素的并集
void test02()
{
	vector<int> v1, v2, v3;
	for (int i = 0; i <= 10; i++)
	{
		v1.push_back(i);
	}
	for (int i = 12; i <= 30; i++)
	{
		v2.push_back(i);
	}
	v3.resi***(v1.size(), v2.size()));
	//迭代器指向最后一个元素的shang一个位置
	
	vector<int>::iterator myEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	for_each(v3.begin(), v3.end(), print());
	for_each(v3.begin(), myEnd, print());
}
void print3(int v){
	cout << v << " ";
}
void test03()
{
	vector<int> v1, v2, v3;
	for (int i = 0; i <= 10; i++)
	{
		v1.push_back(i);
	}
	for (int i = 4; i <= 14; i++)
	{
		v2.push_back(i);
	}
	v3.resize(v1.size());
	//v3.resize(max(v1.size(), v2.size()));
	//迭代器指向最后一个元素的shang一个位置

	set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	for_each(v3.begin(), v3.end(), print3);
	cout << endl;
	vector<int>::iterator myEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	for_each(v3.begin(), myEnd, print3);
}

int main()
{
	//test02();
	test03();
	return EXIT_SUCCESS;
}


8、distace逆序算法
deque根据迭代器求数组下标distance()
两个迭代器之间的距离
迭代器本身是指针来用
#include<iostream>
#include<numeric>
#include<vector>
#include<algorithm>

using namespace std;

class print{
public:
	void operator()(int v){
		cout << v << " ";
	}
};

//distance
void test01()
{
	vector<int> v;
	for (int i=0; i <= 10; i++)
	{
		v.push_back(i);
	}
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		int index = distance(v.begin(), it);
		cout << v[index]<<" ";
	}
	
}

//for_each修改容器元素的值
void print(int& v){
	v = v + 100;
}

void print2(const int& v)
{
	cout << v << " ";
}
void test02()
{
	vector<int> v;
	for (int i = 0; i <= 10; i++)
	{
		v.push_back(i);
	}
	for_each(v.begin(), v.end(), print2);
	cout << endl;
	for_each(v.begin(), v.end(), print);
	cout << endl;
	for_each(v.begin(), v.end(), print2);
	cout << endl;

}

//for_each逆向遍历
void test03()
{
	vector<int> v;
	for (int i = 0; i <= 10; i++)
	{
		v.push_back(i);
	}
	for_each(v.begin(), v.end(), print2);
	cout << endl;
	for_each(v.rbegin(), v.rend(), print2);
	cout << endl;
	//for_each(v.rbegin(), v.rend(), print2);
}
int main()
{
	//test02();
	test03();
	return EXIT_SUCCESS;
}




全部评论

(0) 回帖
加载中...
话题 回帖