C++STL总结笔记(三)—— 常见算法

文章目录


一、基本概念

算法是STL中很重要的一部分,其功能包括比较,查找,排序,交换,遍历,复制等等。

最大的算法头文件是algorithm,封装了很多种模板类。还有numeric和functional也比较常见。

二、程序示例

1.遍历

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;

void print(int a)
{
	cout << a << " ";
}

class print1
{
public:
	void operator()(int a)
	{
		cout << a << " ";
	}
};

class print2
{
public:
	int operator()(int a)
	{
		cout << a << " ";
		return a;
	}
};

void test()
{
	list<int>L;

	L.push_back(1);
	L.push_back(2);
	L.push_back(3);

	//函数作为形参进行遍历输出
	for_each(L.begin(), L.end(), print);
	cout << endl;

	//仿函数进行遍历
	for_each(L.begin(), L.end(), print1());
	cout << endl;

	//transform实现遍历
	list<int>L1;
	L1.resize(L.size());
	transform(L.begin(),L.end(),L1.begin(), print2());

}

int main()
{
	test();

	system("pause");
}

2. 查找

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;

class Compare
{
public:
	//一元谓词
	bool operator()(int a)
	{
		return a > 1;
	}
};

class Cat
{
public:
	Cat(string name, int color, int age)
	{
		this->Name = name;
		this->Color = color;
		this->Age = age;
	}

	//自定义数据类型需要重载==
	bool operator==(const Cat& cat)
	{
		if (Name == cat.Name && Color == cat.Color && Age == cat.Age)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

public:
	string Name;
	int Color;
	int Age;
};

class print1
{
public:
	bool operator()(Cat& cat)
	{
		return cat.Age > 3;
	}
};

void test()
{
	list<int>L;

	L.push_back(1);
	L.push_back(2);
	L.push_back(3);

	//find算法查找
	list<int>::iterator i = find(L.begin(), L.end(), 1);
	if (i == L.end())
	{
		cout << "未查找到" << endl;
	}
	else
	{
		cout << "查找到" << *i<<endl;
	}

	//find_if查找
	list<int>::iterator i1 = find_if(L.begin(),L.end(),Compare());
	if (i1 == L.end())
	{
		cout << "未查找到" << endl;
	}
	else
	{
		cout << "查找到" << *i1 << endl;
	}

	//查找元素是否存在,无序序列结果未知
	bool i2 = binary_search(L.begin(), L.end(), 1);
	if (i2)
	{
		cout << "查找到1" << endl;
	}
	else
	{
		cout << "未查找到" << endl;
	}

	//count统计
	int n = count(L.begin(), L.end(),1);
	cout << n << endl;

	//count_if统计
	int n1 = count_if(L.begin(), L.end(), Compare());
	cout << n1 << endl;

}

void test1()
{
	list<Cat>L;

	Cat cat1("小100", 76, 2);
	Cat cat2("小200", 32, 2);
	Cat cat3("小300", 32, 4);
	Cat cat4("小400", 32, 3);
	Cat cat5("小500", 54, 1);

	//插入
	L.push_back(cat1);
	L.push_back(cat2);
	L.push_back(cat3);
	L.push_back(cat4);
	L.push_back(cat5);

	//find查找
	list<Cat>::iterator i = find(L.begin(), L.end(), cat1);

	if (i == L.end())
	{
		cout << "未查找到" << endl;
	}
	else
	{
		cout << "查找到" << (*i).Name << endl;
	}

	//find_if查找
	list<Cat>::iterator i1 = find_if(L.begin(), L.end(), print1());

	if (i1 == L.end())
	{
		cout << "未查找到" << endl;
	}
	else
	{
		cout << "查找到" << (*i1).Name << endl;
	}

	//查找相邻的重复元素
	list<Cat>::iterator i2 = adjacent_find(L.begin(), L.end());
	if (i2 == L.end())
	{
		cout << "未查找到" << endl;
	}
	else
	{
		cout << "查找到" << (*i2).Name << endl;
	}

	Cat cat6("小300", 32, 4);
	//count统计,需要重载
	int n = count(L.begin(), L.end(), cat6);
	cout << n << endl;
}

int main()
{
	test1();
	system("pause");
}

3. 排序、拷贝、替换

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

class Compare
{
public:
	//一元谓词
	bool operator()(int a,int b)
	{
		return a > b;
	}
};

class Compare3
{
public:
	//一元谓词
	bool operator()(int a)
	{
		return a > 3;
	}
};

void print(int a)
{
	cout << a << " ";
}

class Cat
{
public:
	Cat(string name, int color, int age)
	{
		this->Name = name;
		this->Color = color;
		this->Age = age;
	}

	//自定义数据类型需要重载==
	bool operator==(const Cat& cat)
	{
		if (Name == cat.Name && Color == cat.Color && Age == cat.Age)
		{
			return true;
		}
		else
		{
			return false;
		}
	}

public:
	string Name;
	int Color;
	int Age;
};

void test()
{
	vector<int>L;

	L.push_back(1);
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);

	//降序
	sort(L.begin(), L.end(),Compare());
	for_each(L.begin(), L.end(), print);

	cout << endl;
	//greater<int>()
	sort(L.begin(), L.end(),greater<int>());
	for_each(L.begin(), L.end(), print);

	cout << endl;

	sort(L.begin(), L.end());

	//随机打乱
	//srand((unsigned int)time(NULL));
	//random_shuffle(L.begin(), L.end());
	//for_each(L.begin(), L.end(), print);

	//cout << endl;

	vector<int>L1(L);

	vector<int>L2;
	L2.resize(L.size()+L1.size());
	//合并,默认只能同为升序的合并merge必须为有序序列
	merge(L.begin(), L.end(), L1.begin(), L1.end(),L2.begin());
	for_each(L2.begin(), L2.end(), print);

	cout << endl;

	//反转
	reverse(L.begin(), L.end());
	for_each(L.begin(), L.end(), print);

	cout << endl;

	//拷贝
	vector<int>L3;
	L3.resize(L.size());
	copy(L.begin(), L.end(), L3.begin());
	for_each(L3.begin(), L3.end(), print);

	cout << endl;

	//替换
	replace(L.begin(), L.end(), 2, 5);
	for_each(L.begin(), L.end(), print);

	cout << endl;

	replace_if(L.begin(), L.end(), Compare3(),20);
	for_each(L.begin(), L.end(), print);

	cout << endl;

	//互换
	swap(L, L1);
}

int main()
{
	test();
	system("pause");
}

4. numeric相关算法

#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
#include<ctime>
using namespace std;

void print(int a)
{
	cout << a << " ";
}

void test()
{
	vector<int>L;

	L.push_back(1);
	L.push_back(2);
	L.push_back(3);
	L.push_back(4);

	//计算容器元素的和,0为起始累加值
	int total = accumulate(L.begin(), L.end(), 0);
	cout << total<<endl;

	//填充元素
	vector<int>L1;
	L1.resize(L.size());
	fill(L1.begin(), L1.end(), 3);
	for_each(L1.begin(), L1.end(), print);
	cout << endl;
	//求交集
	vector<int>L2;
	L2.resize(min(L.size(),L1.size()));
	vector<int>::iterator i = set_intersection(L.begin(), L.end(), L1.begin(), L1.end(), L2.begin());
	for_each(L2.begin(), i, print);
	cout << endl;

	//求并集
	vector<int>L3;
	L3.resize(L.size()+ L1.size());
	vector<int>::iterator j = set_union(L.begin(), L.end(), L1.begin(), L1.end(), L3.begin());
	for_each(L3.begin(), j, print);
	cout << endl;

	//差集
	vector<int>L4;
	L4.resize(max(L.size() , L1.size()));
	vector<int>::iterator j1 = set_difference(L.begin(), L.end(), L1.begin(), L1.end(), L4.begin());
	for_each(L4.begin(), j1, print);
}

int main()
{
	test();
	system("pause");
}

总结

以上只是stl算法中常见的,后续会随时补充新的算法。

上一篇:pandas解析MovieLens 1M数据集报错 UnicodeDecodeError


下一篇:一、C++入门基础