STL常用算法：遍历、查找、排序、拷贝、替换

00 概述

算法主要是由头文件< algorithm> < functional> < numeric>组成；

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

01 遍历算法

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

for_each 遍历容器

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//普通函数
void print1(int v)
{
	cout << v<<" ";
}
//仿函数
class print2
{
public:
	void operator()(int v)
	{
		cout << v << " ";
	}
};
void test() 
{
	vector<int>v;
	v.push_back(343);
	v.push_back(566);
	v.push_back(23);
	v.push_back(54);

	//普通函数实现遍历操作 把函数名放进来
	for_each(v.begin(), v.end(), print1);
	cout << endl;

	//仿函数实现遍历操作 把函数对象放进来
	for_each(v.begin(), v.end(), print2());
	cout << endl;
}

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

for_each在实际开发中是最常用的遍历算法；

transform 搬运容器到另一个容器中

transform(iterator beg1,iterator end1,iterator beg2,_func);

//beg1 原容器的开始迭代器

//end1 原容器的结束迭代器

//beg2 目标容器的开始迭代器

// _func 函数或函数对象，搬运过程器件可以对数据进行一些运算

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

class Transform
{
public:
	int operator()(int v)
	{
		return v+100;
	}
};
class Print
{
public:
	void operator()(int v)
	{
		cout << v << " ";
	}
};
void test() 
{
	vector<int>v;
	v.push_back(343);
	v.push_back(566);
	v.push_back(23);
	v.push_back(54);

	vector<int>v2;

	//目标容器需要提前开启空间
	v2.resize(v.size());
	//搬运
	transform(v.begin(), v.end(), v2.begin(), Transform());
	for_each(v2.begin(), v2.end(), Print());
	cout << endl;
}

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

搬运的目标容器必须要提前开辟空间，否则无法正常搬运；

02 查找算法

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

find 查找指定元素

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

• find(iterator beg,iterator end,value);

  //按值查找，value为要查找的元素；

  1）查找内置的数据类型

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

void test() 
{
	vector<int>v;
	v.push_back(343);
	v.push_back(566);
	v.push_back(23);
	v.push_back(54);
	//查找内置的数据类型 无论能不能找到 都会返回一个迭代器
	vector<int>::iterator it=find (v.begin(), v.end(), 23);
	if (it == v.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找到：" << *it << endl;
	}
}

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

2）查找自定义的数据类型

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Age = age;
		this->m_Name = name;
	}
	//重载==号 让底层知道如何对比Person类型
	bool operator==(const Person&p)
	{

		if (this->m_Age == p.m_Age&&this->m_Name == p.m_Name)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	string m_Name;
	int m_Age;
};
void test() 
{
	vector<Person>v;

	Person p1("liu", 20);
	Person p2("gao", 22);
	Person p3("wang", 26);
	Person p4("zheng", 18);
	Person p5("zhou", 29);

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

	//需要重载==号 返回值是迭代器
	vector<Person>::iterator it=find (v.begin(), v.end(), p2);
	if (it == v.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找到：" << "姓名：" << it->m_Name << " 年龄：" << it->m_Age << endl;
	}
}

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

find_if 条件查找

• find_if(iterator beg,iterator end, _pred);

  //按条件查找元素

  // _pred函数或者谓词（返回bool类型的仿函数）

  1）内置数据类型

#include<iostream>
#include"vector"
using namespace std;

//find_if
class  GreaterFive
{
public:
	bool operator()(int val)
	{
		return val > 5;//>5返回真
	}

};
void test()
{
	vector<int>v;
	for(int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
	if (it == v.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找到大于5的数字为：" << *it << endl;
	}
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

2）自定义数据类型

查找一个年龄大于20岁的人

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

//find_if 查找自定义的数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_Age = age;
		this->m_Name = name;
	}
	string m_Name;
	int m_Age;
};
//仿函数 
class  Greater20
{
public:
	bool operator()(Person& p)//只要年龄大于20就返回
	{
		return p.m_Age > 20;
	}

};
void test()
{
	vector<Person>v;

	Person p1("yutong", 26);
	Person p2("runqi", 19);
	Person p3("xiaoxiong", 19);
	Person p4("keke", 19);

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

	vector<Person>::iterator it = find_if(v.begin(), v.end(), Greater20());
	if (it == v.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "找到姓名：" << it->m_Name << " 年龄：" << it->m_Age << endl;
	}
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

adjacent_find 查找相邻重复元素

• adjacent_find (iterator beg, iterator end);

  //查找相邻重复元素，返回相邻元素的第一个位置的迭代器

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

void test()
{
	vector<int>v;
	v.push_back(10);
	v.push_back(5);
	v.push_back(8);
	v.push_back(8);
	v.push_back(10);
	v.push_back(2);
	v.push_back(22);

	vector<int>::iterator it = adjacent_find(v.begin(), v.end());//迭代器接收
	if (it == v.end())
	{
		cout << "未找到相邻重复元素" << endl;
	}
	else
	{
		cout << "找到相邻重复元素" << *it << endl;
	}
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

binary_search 二分查找 查找指定元素是否存在

• bool binary_search(iterator beg, iterator end, value);

  //查找指定元素是否存在，查到返回ture，否则返回false

  //只能查找有序序列

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

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

	bool m= binary_search(v.begin(), v.end(),6);//返回bool类型
	if (m)
	{
		cout << "找到" << endl;
	}
	else
	{
		cout << "未找到"<< endl;
	}
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

count 统计元素个数

• count(iterator beg, iterator end, value);

  //统计元素出现个数

  1）统计内置的数据类型

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

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

	int m= count(v.begin(), v.end(),6);
	cout << "出现次数：" << m << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

2）统计自定义的数据类型

需要在类中 重载等号才能查找，要不然编译器不知道怎么查找

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

class Person
{
public:
	Person(string name, int age)
	{
		this->m_Age = age;
		this->m_Name = name;
	}
	string m_Name;
	int m_Age;
	//重载==
	bool operator==(const Person& p)//底层要求加const
	{
		if (this->m_Age == p.m_Age)//年龄相等即可
			return true;
		else
			return false;
	}
};

void test()
{
	vector<Person>v;
	
	Person p1("yutong", 26);
	Person p2("runqi", 19);
	Person p3("xiaoxiong", 19);
	Person p4("keke", 19);

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

	Person p("qqq", 19);
	int m = count(v.begin(), v.end(),p );
	cout << "和aaa同岁的人有" << m << "个" << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

count_if 按条件统计元素次数

• count_if(iterator beg, iterator end,_pred);

  //按条件统计元素出现次数

  //_pred是谓词

  1）统计内置的数据类型

  2）统计自定义的数据类型

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

class Person
{
public:
	Person(string name, int age)
	{
		this->m_Age = age;
		this->m_Name = name;
	}
	string m_Name;
	int m_Age;
};
//仿函数 
class  Greater20
{
public:
	bool operator()(const Person& p)//只要年龄大于20就返回
	{
		return p.m_Age > 20;
	}

};
class Ageover20
{
public:
	bool operator()(Person& p)
	{
		return p.m_Age > 20;
	}
};
void test()
{
	vector<Person>v;

	Person p1("yutong", 26);
	Person p2("runqi", 19);
	Person p3("xiaoxiong", 19);
	Person p4("keke", 19);

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

	int m = count_if(v.begin(), v.end(), Ageover20());
	cout << "年龄大于20的人有" <<m<< "个" << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

03 排序算法

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

sort 对容器内元素进行排序

• sort(iterator beg, iterator end,_pred);

  （非常常用的算法，一定要熟练掌握）

  //按值查找元素，找到返回指定位置的迭代器，找不到则返回结束迭代器的位置

  //_pred默认是升序排序

  1)默认用法

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

//默认升序排序

void myPrint(int val)
{
	cout << val << " ";
}

void test()
{
	vector<int>v;
	v.push_back(9);
	v.push_back(4);
	v.push_back(88);
	v.push_back(23);
	v.push_back(40);
	v.push_back(18);
	v.push_back(62);
	v.push_back(8);
	v.push_back(27);

	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);//普通函数，把函数名放进来
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

2）改为降序排列

使用内建的函数对象greater，当然也可以自己写一个仿函数

sort(v.begin(), v.end(), greater<int>());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
           

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

• random_shuffle(iterator beg, iterator end);

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


void myPrint(int val)
{
	cout << val << " ";
}

void test()
{
	srand((unsigned int)time(NULL));//加随机数种子
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	//洗牌
	random_shuffle(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

merge 两个容器元素合并，并存储到另一容器中

• merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);

  //目标容器开始迭代器（目标容器要提前开辟内存空间）

  //注意：两个容器必须是有序的，要么都是升序，要么都是降序才行

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

void myPrint(int val)
{
	cout << val << " ";
}

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

	vector<int>v3;
	//提前给目标容器分配内存空间
	v3.resize(v1.size() + v2.size());
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	for_each(v3.begin(), v3.end(), myPrint);
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

reverse 将容器内元素进行反转

• reverse(iterator beg, iterator end);

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

void myPrint(int val)
{
	cout << val << " ";
}

void test()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	//反转
	reverse(v1.begin(), v1.end());
	//打印
	for_each(v1.begin(), v1.end(), myPrint);
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

04 拷贝和替换算法

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

copy 拷贝

• copy(iterator beg, iterator end, iterator dest);

  //相当于赋值操作，实际应用中不常用

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

void myPrint(int val)
{
	cout << val << " ";
}

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

	vector<int>v2;
	//提前开辟空间
	v2.resize(v1.size());
	copy(v1.begin(), v1.end(), v2.begin());
	//打印
	for_each(v2.begin(), v2.end(), myPrint);
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

replace 旧元素修改为新元素

• replace(iterator beg, iterator end, old value, new value);

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

void myPrint(int val)
{
	cout << val << " ";
}
void test()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(77);
	}
	cout << "替换前：" << endl;
	for_each(v1.begin(), v1.end(), myPrint);
	cout << endl;

	//替换
	replace(v1.begin(), v1.end(), 77,22);
	cout << "替换后：" << endl;
	for_each(v1.begin(), v1.end(), myPrint);
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

replace_if 按条件替换元素

• replace(iterator beg, iterator end, _pred, new value);

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

void myPrint(int val)
{
	cout << val << " ";
}
//仿函数
class greater5
{
public:
	bool operator()(const int val)
	{
		return val > 5;
	}
};
void test()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	cout << "替换前：" << endl;
	for_each(v1.begin(), v1.end(), myPrint);
	cout << endl;

	//替换
	replace_if(v1.begin(), v1.end(), greater5(),80);
	cout << "替换后：" << endl;
	for_each(v1.begin(), v1.end(), myPrint);
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

利用仿函数可以灵活的筛选满足的条件；

swap 互换两个容器的元素

• swap(container c1,container c2);

  //交换的容器要是同一种类型的

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

void myPrint(int val)
{
	cout << val << " ";
}
void test()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
	}
	vector<int>v2;
	for (int i = 0; i < 15; i++)
	{
		v2.push_back(i+100);
	}

	//容器大小不一样 也是可以互换的
	v2.swap(v1);

	//打印
	for_each(v1.begin(), v1.end(), myPrint);
	cout << endl;
	for_each(v2.begin(), v2.end(), myPrint);
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

05 算术生成算法

• 算术生成算法属于小型算法，使用时包含的头文件为#include< numeric>
• accumulate //容器元素累计求和
• fill //重新填充

accumulate 累计求和

• accumulate(iterator beg, iterator end, value);

  //value为起始的累加值（是额外的），相当于初值；

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

void test()
{
	vector<int>v1;
	for (int i = 0; i <= 100; i++)
	{
		v1.push_back(i);
	}
	int total = accumulate(v1.begin(), v1.end(), 1);
	cout << total << endl;


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

fill 重新填充

• fill(iterator beg, iterator end, value);

  //将容器区间内的元素值填充为指定的值

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

void myPrint(int val)
{
	cout << val << " ";
}
void test()
{
	vector<int>v1;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(22);
	}
	//重新填充为100
	fill(v1.begin(), v1.end(), 100);
	for_each(v1.begin(), v1.end(), myPrint);
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

06 集合算法

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

set_intersction 求两个容器的交集

• set_intersction(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);

  //两个集合必须是有序序列

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

void myPrint(int val)
{
	cout << val << " ";
}
void test()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}
	vector<int>v3;

	v3.resize(min(v1.size(), v2.size()));
	//获取交集 返回一个迭代器 位置是交集的结束迭代器地址
	vector<int>::iterator itEnd=set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	
	for_each(v3.begin(), itEnd,myPrint);//不要使用v3的结束迭代器，使用真正的交集结束的地址
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

set_union 求两个容器的并集

• set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);

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

void myPrint(int val)
{
	cout << val << " ";
}
void test()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}
	vector<int>v3;

	//最坏的情况是两个容器元素没有交集
	v3.resize(v1.size()+v2.size());
	//获取并集 返回一个迭代器 位置是并集的结束迭代器地址
	vector<int>::iterator itEnd=set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	
	for_each(v3.begin(), itEnd,myPrint);//不要使用v3的结束迭代器
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}
           

set_difference 求两个容器的差集

• • set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator dest);

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

void myPrint(int val)
{
	cout << val << " ";
}
void test()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 5);
	}
	vector<int>v3;

	//最坏的情况 没有一点交集 取最大的那个容器
	v3.resize(max(v1.size(),v2.size()));

	cout << "v1和v2的差集为：" << endl;
	vector<int>::iterator itEnd=set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());//返回差集结束的位置
	for_each(v3.begin(), itEnd,myPrint);
	cout << endl;

	cout << "v2和v1的差集为：" << endl;
	vector<int>::iterator itEnd2 = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v3.begin());
	for_each(v3.begin(), itEnd2, myPrint);
	cout << endl;
}
int main()
{
	test();
	system("pause");
	return 0;
}