C++ STL-常用算法

STL-常用算法

概述：

• 算法主要是由头文件< algorithm > < functional > < numeric > 组成
• < algorithm >是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历操作、复制、修改等等
• < numeric >体积很小，只包括几个在序列上面进行简单数学运算的模板函数
• < functional >定义了一些模板类，用以声名函数对象

常用遍历算法

算法简介：

• for_each //遍历容器
• transform //搬运容器到另一个容器中

for_each

功能：

• 实现遍历容器

函数原型：

• for_each(iterator beg, iterator end, _func);
  //遍历算法 遍历容器元素
  // beg开始迭代器
  // end结束迭代器
  // _func 函数或者函数对象

示例：

#include
#include 
using namespace std;
#include

//常用遍历算法 for_each
//1、普通函数遍历输出
void myPrint(int val)
{
	cout << val << " ";
}

//2、仿函数遍历输出
class MyPrint
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};
void _01Test01()
{
	vector v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	for_each(v.begin(), v.end(), MyPrint());
	cout << endl;
}

void main()
{
	_01Test01();
}

transform

功能：

• 搬运容器到另一个容器

函数原型：

• transform(iterator beg1, iterator end1, iterator beg2, _func);
  //beg1 源容器开始迭代器
  //end2 源容器结束迭代器
  //beg2 源容器开始迭代器
  //_func 函数或函数对象
  示例：

#include
#include
using namespace std;
#include

//常用遍历算法 transform
class Transform
{
public:
	int operator()(int val)
	{
		val += 100;
		cout << val << " ";
		return val;
	}


};

void _02Test01()
{
	vector v1;
	for(int i=0;i<10;i++)
	{
		v1.push_back(i);
	}

	vector v2;//目标容器
	v2.resize(10);//目标容器提前开辟空间
	transform(v1.begin(),v1.end(), v2.begin(),Transform());
	cout << endl;
}

void main()
{
	_02Test01();
}

常用查找算法

算法简介：

• find //查找元素
• find_if //按条件查找
• adjacent_find //查找相邻重复元素
• binary_search //二分法查找
• count //统计元素个数
• count_if //按条件统计元素个数

find

功能：

• 查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()

函数原型：

• find(iterator beg, iterator end, value);
  // 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
  // beg 开始迭代器
  // end 结束迭代器
  // value 查找的元素

注意：当查找元素为自定义数据类型时，必须在底层重载一下"=="；

#include
#include 
using namespace std;
#include
//常用查找算法
//find
class Person
{
public:
	string m_Name;
	int m_Age;
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	//重写相等关系运算符
	bool operator==(const Person& p)
	{
		return this->m_Name == p.m_Name && this->m_Age == p.m_Age;
	}

};

//查找 内置数据类型
void _01Test01()
{
	vector v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	//查找 容器中 是否有5这个元素
	vector::iterator it;
	it = find(v.begin(), v.end(), 5);
	if (it != v.end())
	{
		cout << "找到该元素，该元素为" << *it << endl;
	}
	else
	{
		cout << "未找到该元素！" << endl;
	}
}

//查找 自定义数据类型
void _01Test02()
{
	Person p1("aaaa", 10);
	Person p2("bbbb", 20);
	Person p3("cccc", 30);
	Person p4("dddd", 40);

	vector v;
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	vector::iterator it;
	it = find(v.begin(), v.end(), Person("cccc",30));

	if (it != v.end())
	{
		cout << "找到该元素 : " << "姓名："<m_Name<<"  年龄："<m_Age << endl;
	}
	else
	{
		cout << "未找到该元素！" << endl;
	}
}

void main()
{
	//_01Test01();
	_01Test02();
}

find_if

功能：

• 按条件进行查找

函数原型：

• find_if(iterator beg, iterator end, _Pred);
  //按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
  //beg开始迭代器
  //end结束迭代器
  //_Pred函数或谓词（返回bool类型的仿函数）

示例：

#include
#include
using namespace std;
#include
//常用查找算法 find_if

//1、查找内置数据类型
bool greater5(int val)
{
	return val > 5;
}

void _02Test01()
{
	vector v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	v.push_back(2);
	v.push_back(10);
	v.push_back(4);
	vector::iterator it;
	it= find_if(v.begin(), v.end(), greater5);
	while (it!=v.end())
	{
		if (it != v.end())
		{
			cout << "找到该元素：" << *it << endl;
		}
		else
		{
			cout << " 没有找到该元素" << endl;
		}
		it=find_if(++it, v.end(), greater5);
	}
}

//2、查找自定义数据类型
class Student
{
public:
	string m_Name;
	int m_Age;
public:
	Student(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	//重写相等关系运算符
	bool operator==(const Student& p)
	{
		return this->m_Name == p.m_Name && this->m_Age == p.m_Age;
	}

};

bool greaterAge_20(Student &s)
{
	return s.m_Age > 20;
}

void _02Test02()
{
	Student s1("aaaa", 10);
	Student s2("bbbb", 20);
	Student s3("cccc", 30);
	Student s4("dddd", 40);

	vector v;
	v.push_back(s1);
	v.push_back(s2);
	v.push_back(s3);
	v.push_back(s4);

	vector::iterator it =find_if(v.begin(), v.end(), greaterAge_20);
	while (it != v.end())
	{
		if (it == v.end())
		{
			cout << "未找到该学生" << endl;
		}
		else
		{
			cout << "找到该学生：" << " 姓名：" 
				<< it->m_Name << "  年龄：" << it->m_Age << endl;
		}
		it = find_if(++it, v.end(), greaterAge_20);
	}
}

void main()
{
	//_02Test01();
	_02Test02();
}

adjacent_find

功能：

• 寻找相邻重复元素

函数原型：
adjacent_find(iterator beg, iterator end); //返回相邻重复元素迭代器位置，如果没有相邻重复元素则返回结束迭代器位置

binary_search

功能：

• 查找指定元素是否存在

函数原型：

• bool binary_search(iterator beg ,iterator end, value);
  //查找指定的元素，查到 返回true 否则返回false
  //注意：在无序序列中不可用
  //beg 开始迭代器
  //end 结束迭代器
  //value 要查找的元素

示例：

#include
#include
using namespace std;
#include

//常用查找算法  binary_search
class _04Person
{
public:
	string m_Name;
	int m_Age;
public:
	_04Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
};

//谓词 规定Person元素按年龄升序放入set容器
class ComparePerson
{
public:
	bool operator()( const _04Person& p1,const _04Person &p2)const
	{
		return p1.m_Age 
	set<_04Person, ComparePerson> s;
	_04Person p1("刘备", 40);
	_04Person p2("关羽", 35);
	_04Person p3("张飞", 32);
	_04Person p4("赵云", 30);
	_04Person p5("诸葛亮", 31);

	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);
	s.insert(p5);

	//测试
	for (set<_04Person, ComparePerson>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << "姓名：" << it->m_Name << "  年龄：" << it->m_Age << endl;
	}

	bool finded= binary_search(s.begin(), s.end(), _04Person("张飞", 35), ComparePerson());

	if (finded)
	{
		cout << "找到了";
	}
	else
	{
		cout << "没找到" << endl;
	}
}

void main()
{
	_04Test01();
}

count

功能：

• 统计元素个数

函数原型：

• count(iterator beg, iterator end, value);
  //返回所要统计元素的个数
  //beg 开始迭代器
  //end 结束迭代器
  //value 要查找的元素
  注意： 在统计自定义数据类型时，必须在自定义类中重载关系运算符“==”，bool opertor ==(const 自定义类 &变量名)；

count_if

功能：

• 按条件统计元素个数

函数原型：

• count_if(iterator beg, iterator end, _Pred);
  //按条件统计元素个数
  //beg 开始迭代器
  //end 结束迭代器
  //_Pred 谓词

示例：

#include
#include
using namespace std;
#include

//常用查找算法 count_if
class MyClass
{
public:
	string m_Str;
	int m_Num;
public:
	MyClass(string str, int num)
	{
		this->m_Str = str;
		this->m_Num = num;
	}
};

//1、采用普通函数规定条件
bool MyPred(const MyClass& mc)
{
	return mc.m_Num > 10;
}

void _06Test01()
{
	MyClass m1("aaaa", 10);
	MyClass m2("bbbb", 12);
	MyClass m3("cccc", 9);
	MyClass m4("dddd", 13);

	vectorv;
	v.push_back(m1);
	v.push_back(m2);
	v.push_back(m3);
	v.push_back(m4);

	int count= count_if(v.begin(), v.end(), MyPred);
	cout << "采用普通函数规定条件:" << endl;
	cout << "大于10的自定义数据类型MyClass有：" << count << " 个" << endl;
}

//2、采用谓词规定条件
class MyRule
{
public:
	bool operator()(const MyClass& mc)
	{
		return mc.m_Num > 10;
	}
};

void _06Test02()
{
	MyClass m1("aaaa", 10);
	MyClass m2("bbbb", 12);
	MyClass m3("cccc", 9);
	MyClass m4("dddd", 13);

	vectorv;
	v.push_back(m1);
	v.push_back(m2);
	v.push_back(m3);
	v.push_back(m4);

	int count = count_if(v.begin(), v.end(), MyRule());
	cout << "采用谓词规定条件:" << endl;
	cout << "大于10的自定义数据类型MyClass有：" << count << " 个" << endl;
}

void main()
{
	//_06Test01();
	_06Test02();
}

常用排序算法

算法简介：

• sort //对容器内元素进行排序
• random_shuffle //洗牌 指定范围内的元素随机调整次序
• merge //容器元素合并， 并存储到另一个容器中
• reverse //反转指定范围的元素

sort

功能：

• 对容器内元素进行排序

函数原型：

• sort(iterator beg, iterator end, _Pred);
  //按值查找元素，查找返回指定位置迭代器，找不到返回结束迭代器位置
  //beg 开始迭代器

示例：

**#include
using namespace std;
#include
#include

//sort算法
class Person
{
public:
	string m_Name;
	int m_Age;

public:
	Person() {}
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	bool operator()(const Person& p1, const Person& p2)
	{
		return p1.m_Age < p2.m_Age;
	}

};

bool mySort01(const Person& p1, const Person& p2)
{
	return p1.m_Age < p2.m_Age;
}

void _01Test01()
{
	vector v;
	Person p1("aaaa", 10);
	Person p2("bbbb", 30);
	Person p3("cccc", 20);
	Person p4("dddd", 40);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	//采用普通函数规定排序方式
	//sort(v.begin(), v.end(),Person());

	//在类中重写operator()
	sort(v.begin(), v.end(),mySort01);

	for (vector::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << "姓名：" << it->m_Name << "  年龄：" << it->m_Age << endl;
	}
}

bool mySort02(int& num1, int& num2)
{
	return num1 > num2;
}

void _01Test02()
{
	vector v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	sort(v.begin(), v.end(), mySort02);
	for (vector::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << endl;
	}
}

void main()
{
	_01Test01();
	//_01Test02();
}**

random_shuffle

功能：

• 洗牌 指定范围内元素随机调整次序

函数原型：

• random_shuffle(iterator beg, iterator end);
  //指定范围内的元素随机调整次序
  //beg开始迭代器
  //end结束迭代器

示例：

#include
#include
#include
using namespace std;

//random_shuffle算法
void Print(int& num)
{
	cout << num << " ";
}

void _02Test01()
{
	srand((unsigned int)time(NULL));
	vector v;
	for (int i= 0; i < 10;i++)
	{
		v.push_back(i);
	}

	random_shuffle(v.begin(), v.end());

	for_each(v.begin(), v.end(), Print);
	cout << endl;
}

void main()
{
	_02Test01();
}

merge

功能：

• 将两个容器的元素合并，并存储到另一个容器

函数原型：

• merge(iterator beg1, iterator end1, iterator beg2, interator end2, iterator dest);
  //容器元素合并，并存储到另一个容器
  //beg1 容器1开始迭代器
  //end1 容器1结束迭代器
  //beg2 容器2开始迭代器
  //end2 容器2结束迭代器
  //dest 目标容器开始迭代器

注意：
1、使用merge算法的前提，必须是两个有序序列容器，并且排序方式一致；
2、将合并后的元素放入到目前容器时，必须提前为目标容器开辟空间，targetVessle.resize(v1.size()+v2.size())。

示例：

#include
#include
#include
using namespace std;

//merge算法
void myPrint(int& num)
{
	cout << num << " ";
}
void _03Test01()
{
	vector v1;
	vector v2;
	vector vTarget;

	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i+1);
	}

	//v1.push_back(2);//运行报错 当插入2时会导致原有的有序序列被破坏

	//提前开辟空间
	vTarget.resize(v1.size() + v2.size());

	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), vTarget.end(), myPrint);
	cout << endl;
}

void main()
{
	_03Test01();
}

reverse

功能：

• 将容器内元素进行反转

函数原型：

• reverse(iterator beg, iterator end);
  //反转指定范围内的元素
  //beg开始迭代器
  //end结束迭代器

常用拷贝和替换算法

算法简介：

• copy //容器内指定范围的元素拷贝到另一个容器中
• replace //将容器内指定元素范围的旧元素修改为新元素
• replace_if //容器内指定范围内满足条件的元素替换成新元素
• swap //互换两个容器的元素

copy

功能：

• 容器内指定范围的元素拷贝到另一个容器中

函数原型：

• copy(iterator beg,iterator end, iterator dest);
  //按值查找元素，找到返回位置迭代器，找不到返回结束迭代器
  //beg开始迭代器
  //end结束迭代器

replace

功能：

• 将容器内指定元素范围的旧元素修改为新元素

函数原型：

• replace(iterator beg, iterator end, oldValue, newValue);
  //将区间内旧元素 替换成 新元素
  //beg开始迭代器
  //end结束迭代器
  //oldValue旧元素
  //newValue新元素

replace_if

功能：

• 容器内指定范围内满足条件的元素替换成新元素

函数原型：

• replace_if(iterator beg, iterator end, _Pred, newValue);
  //将区间内满足条件旧元素 替换成 新元素
  //beg开始迭代器
  //end结束迭代器
  //_Pred谓词
  //newValue新元素

示例：

#include
#include
#include
using namespace std;

class MyConditon
{
public:
	bool operator()(int& num)
	{
		return num < 5;
	}
};

void showElement(int& num)
{
	cout << num << " ";
}

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

	replace_if(v.begin(), v.end(), MyConditon(), 8);

	for_each(v.begin(), v.end(), showElement);
	cout << endl;
}

void  main()
{
	test01();
}

swap

功能：

• 互换两个容器的元素

函数原型：

• swap(container c1, container c2);
  //互换两个容器的元素
  //c1 容器1
  //c2 容器2

示例：

#include
#include
#include
using namespace std;

//常用拷贝和替换算法 swap
void showResult(int& num)
{
	cout << num << " ";
}

void test()
{
	vector v1;
	vector v2;

	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}

	for (int i = 0; i < 20; i++)
	{
		v2.push_back(i+10);
	}
	cout << "交换前:" << endl;

	cout << "v1: ";
	for_each(v1.begin(), v1.end(), showResult);
	cout << endl;

	cout << "v2:";
	for_each(v2.begin(), v2.end(), showResult);
	cout << endl;

	swap(v1, v2);
	cout << "交换后:" << endl;
	cout << "v1: ";
	for_each(v1.begin(), v1.end(), showResult);
	cout << endl;

	cout << "v2:";
	for_each(v2.begin(), v2.end(), showResult);
	cout << endl;
}

void main()
{
	test();
}

常用算术生成算法

注意：

• 算术生成算法属于小型算法，使用时包含头文件为#include< numeric >

算法简介;

• accumulate //计算容器中元素累加总和
• fill //向容器中添加元素

accumulate

功能：

• 计算容器中元素累加总和

函数原型：

• accumulate(tierator beg, iterator end, value);
  //beg为起始迭代器
  //end为结束迭代器
  //value为起始值

示例：

#include
#include
#include
using namespace std;

//accumulate
void _01Test01()
{
	vector v;
	for (int i = 1; i <= 100; i++)
	{
		v.push_back(i);
	}
	int total=0;
	total=accumulate(v.begin(), v.end(),100);

	cout << "总和为：" << total << endl;
}

void main()
{
	_01Test01();
}

fill

功能：

• 向容器中填充自定的元素

函数原型：

• fill(iterator beg, iterator end, value);
  //向容器中填充元素
  //beg 开始迭代器
  //end 结束迭代器
  //value 填充的值

示例：

#include
#include
#include
#include
using namespace std;

//fill
void show(int& num)
{
	cout << num << " ";
}

void _02Test01()
{
	vector v;
	v.resize(10);

	fill(v.begin(), v.end(), 100);
	
	for_each(v.begin(), v.end(), show);
	cout << endl;
}

void main()
{
	_02Test01();
}

常用集合算法

算法简介：

• set_intersection //求两个容器的交集
• set_union //求两个容器的并集
• set_difference //求两个容器的差集

set_intersection

功能：

• 求两个容器的交集

函数原型：

• set_intersection(iterator beg1, iterator end2, iterator beg2, iterator end2, iterator dest);
  // beg1 容器1的开始迭代器
  // end1 容器1的结束迭代器
  // beg2 容器2的开始迭代器
  // end2 容器2的结束迭代器
  // dest 目标容器的开始迭代器

注意：
1、两个容器中的元素必须按照顺序排列，且排序规则一致
2、目标容器的开辟空间为两个容器中较大的那个
3、set_intersection返回值是交集中最后一个元素的迭代器位置

示例：

#include
#include
using namespace std;
#include

//常用集合算法 set_intersection
void Print(int& num)
{
	cout << num << "  ";
}

void _01Test01()
{
	vector v1, v2,v3;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);//0~9
		v2.push_back(i + 5);//5~14
	}

	//v1.push_back(2);// 运行发生错误 v1 和 v2中的元素必须按顺序排列，且排列规则一样

	//开辟的空间大小为 v1 v2中空间较小的那个容器的大小
	v3.resize(min(v1.size(), v2.size()));

	//取v1 v2的交集
	vector::iterator end= set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());

	//使用最后一个交集元素的迭代器作为结束迭代器
	for_each(v3.begin(), end, Print);
	cout << endl;
}

void main()
{
	_01Test01();
}

set_union

功能:

• 求两个容器的并集

函数原型：

• set_union(iterator beg1, iterator end2, iterator beg2, iterator end2, iterator dest);
  // beg1 容器1的开始迭代器
  // end1 容器1的结束迭代器
  // beg2 容器2的开始迭代器
  // end2 容器2的结束迭代器
  // dest 目标容器的开始迭代器

注意：
1、两个容器中的元素必须按照顺序排列，且排序规则一致
2、目标容器的开辟空间需要两个容器相加
3、set_union返回值是并集中最后一个元素的迭代器位置

示例：

#include
#include
using namespace std;
#include

//常用集合算法 set_union
void myPrint(int& num)
{
	cout << num << "  ";
}

void _02Test01()
{
	vector v1, v2, v3;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}

	v3.resize(v1.size() + v2.size());

	vector::iterator end= set_union(v1.begin(), v1.end(), v2.begin(),v2.end(), v3.begin());

	//使用最后一个交集元素的迭代器作为结束迭代器
	for_each(v3.begin(), end, myPrint);
	cout << endl;
}

void main()
{
	_02Test01();
}

set_difference

功能：

• 求两个容器中元素的差集(即容器1减去容器2中与容器1交集的部分)

函数原型;

• set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
  // beg1 容器1的开始迭代器
  // end1 容器1的结束迭代器
  // beg2 容器2的开始迭代器
  // end2 容器2的结束迭代器
  // dest 目标容器的开始迭代器

注意：
1、两个容器中的元素必须按照顺序排列，且排序规则一致
2、目标容器的开辟空间为容器1的空间
3、set_difference返回值是差集中最后一个元素的迭代器位置

示例：

#include
#include
using namespace std;
#include

//常用集合算法 set_difference
void show(int& num)
{
	cout << num << "  ";
}
void _03Test01()
{
	vector v1, v2, v3;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}

	v3.resize(v1.size());

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

void main()
{
	_03Test01();
}