STL-常用算法

时间：2024-01-24 22:10:52

简介

1、算法主要是由头文件<algorithm>[<functional><numeric>组成。

2 <algorithm>是所有STL头文件中最大的一个,范围涉及到比较、 交换、查找、遍历操作、复制、修改等等。

3、<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数。

4、<unctional>定义了一些模板类，用以声明函数对象。

常用遍历算法

算法简介

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

for_each

功能：实现遍历容器

函数原型:

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

例子

//普通函数
void printf1(int v)
{
	cout << v << " ";
}

//仿函数
class printf2
{
public:
	void operator()(int v)const
	{
		cout << v << " ";
	}
};

void test()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	//利用普通函数
	for_each(v.begin(), v.end(), printf1);
	cout << endl;
	cout << "________________________" << endl;
	//利用仿函数
	for_each(v.begin(), v.end(), printf2());
}

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

transform

功能：搬运容器到另一个容器中

函数原型：

transform(iterator beg1, iterator end1, iterator beg2, _fun2);
//beg1 源容器开始迭代器
//end1 源容器结束迭代器
//beg2 目标容器开始迭代器
//_func函数或者函数对象

例子

class Tragetsform
{
public:
	int operator()(int v)const
	{
		return v+100;
	}
};

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

void test()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	
	vector<int> Target; //目标容器
	//在搬运前需要给目标容器开辟空间
	Target.resize(v.size());
	transform(v.begin(), v.end(), Target.begin(), Tragetsform());
	cout << "v容器中数据：" << endl;
	for_each(v.begin(), v.end(), printf1());
	cout << endl;
	cout << "Target容器中数据：" << endl;
	for_each(Target.begin(), Target.end(), printf1());
	cout << endl;
}

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

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

常用查找算法

算法简介

find		    //查找元素
find_if		    //按条件查找元素
adjacent_ find  //查找相邻重 复元素
binary_ search	//二分查找法
count			//统计元素个数
count_if        //按条件统计元素个数

find

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

函数原型

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

例子：

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

	//查找容器中是否有5个元素
	vector<int>::iterator pos = find(v.begin(), v.end(), 5);
	if (pos == v.end())
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << "找到了，并且元素为：" << *pos << endl;
	}
}


class Person
{
public:
	Person(string name, int age)
	{
		this->m_name = name;
		this->m_age = age; 
	}

	//重载==号，让底层知道自定义类型如何对比
	bool operator== (const Person& v1)
	{
		if (this->m_name == v1.m_name && this->m_age == v1.m_age)
			return true;
		else
			return false;
	}

	string m_name;
	int m_age;
};
//查找自定义数据类型
void test2()
{
	vector<Person> v;
	Person p1("张三", 20);
	Person p2("王五", 21);
	Person p3("赵六", 21);
	Person p4("泰七", 22);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	//不插入vector容器中
	Person p5("泰七", 22);

	vector<Person>::iterator pos = find(v.begin(), v.end(), p5);
	if (pos == v.end())
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << "找到了，并且人名为：" << pos->m_name<<" " << "年龄：" << pos->m_age << endl;
	}
}

int main()
{
	test1();
	cout << "__________________________" << endl;
	test2();
	system("pause");
	return 0;
}


find_if

功能：按条件查找元素

函数原型：

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

例子

//内置数据类型
class Great
{
public:
	bool operator()(const int v)
	{
		return v > 5;
		
	}
};

void test1()
{
	vector<int> v;
	for (int i=0; i < 10; i++)
	{
		v.push_back(i);
	}
	vector<int>::iterator pos = find_if(v.begin(), v.end(), Great());
	if (pos == v.end())
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << "找到了，数据为：" << *pos << endl;
	}
}

//自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_name = name;
		this->m_age = age;
	}
	string m_name;
	int m_age;
};

class compare
{
public:
	bool operator()(Person& v)
	{
		return v.m_age > 20;
	}
};

void test2()
{
	vector<Person> v;
	Person p1("张三", 20);
	Person p2("王五", 21);
	Person p3("赵六", 21);
	Person p4("泰七", 22);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	//年龄大于20
	vector<Person>::iterator pos = find_if(v.begin(), v.end(), compare());
	if (pos == v.end())
	{
		cout << "未找到" << endl;
	}
	else
	{
		cout << "找到了,此人为：" <<pos->m_name<<" "<<"年龄：" <<pos->m_age<< endl;
	}
}

int main()
{
	test1();
	cout << endl << "________________" << endl;
	test2();
	system("pause");
	return 0;
}


adjacent_find

功能：查找相邻重复元素

函数原型：

adjacent_find(iterator beg, iterator end);
//查找相邻重复元素，返回相邻元素的第一个位置的迭代器
//beg 开始迭代器
//end 结束迭代器

例子

void test()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(10);
	v.push_back(20);
	vector<int>::iterator pos=adjacent_find(v.begin(), v.end());
	if (pos == v.end())
	{
		cout << "未找到相邻重复的元素" << endl;
	}
	else
	{
		cout << "找到了相邻重复的元素，他为：" << *pos << endl;
	}
}

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


binary_search

功能：查找指定元素是否存在

函数原型：

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

例子

void test()
{
	vector<int> v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	//查找容器中是否有9这个元素
	bool a=binary_search(v.begin(), v.end(), 10);
	if (a)
	{
		cout << "找到" << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
	
}

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

总结：二分查找法效率很高，但值得注意的是查找的容器中元素必须是有序序列


count

功能：统计元素的个数

函数原型：

count(iterator beg, iterator end, value);
//统计元素的个数
//beg 开始迭代器
//end 结束迭代器
//value 统计的元素

例子

//统计内置数据类型
void test1()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	int a=count(v.begin(), v.end(), 1);
	cout << "1的个数：" << a << endl;
}

//统计自定义数据类型
class Person
{
public:
	bool operator==(const Person& p)
	{
		if (this->m_age == p.m_age)
		{
			return true;
		}
		else
			return false;
	}
	Person(string name, int age)
	{
		this->m_name = name;
		this->m_age = age;
	}
	string m_name;
	int m_age;
};
void test2()
{
	vector<Person> v;
	Person p1("张三", 30);
	Person p2("李四", 31);
	Person p3("王五", 35);
	Person p4("赵六", 30);
	Person p5("泰七", 30);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);
	Person p6("秦八", 30);
	int a=count(v.begin(), v.end(), p6);
	cout << "与秦八年龄相同的有：" << a << endl;
}

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

总结:对于统计自定义数据类型的时候，需要配合重载operator==


count_if

功能：按条件统计元素个数

函数原型

count_if(iterator beg, iterator end, _Pred)
//按条件统计元素出现的次数
//beg 开始迭代器
//end 结束迭代器
//_Pred 谓词

例子

//统计内置数据类型
class compare
{
public:
	bool operator()(const int a)
	{
		return a > 20;
	}
};
void test1()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	//统计有多少个大于20的数
	int a = count_if(v.begin(), v.end(), compare());
	cout << "大于20的数有：" << a << endl;
}

//统计自定义数据类型
class Person
{
public:
	Person(string name, int age)
	{
		this->m_name = name;
		this->m_age = age;
	}
	string m_name;
	int m_age;
};

class compare25
{
public:
	bool operator()(const Person& p)
	{
		return  p.m_age > 25;
	}
};

void test2()
{
	vector<Person> v;
	Person p1("张三", 25);
	Person p2("李四", 23);
	Person p3("王五", 35);
	Person p4("赵六", 37);
	Person p5("泰七", 30);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);
	v.push_back(p5);
	int a = count_if(v.begin(), v.end(), compare25());
	cout << "年龄大于25的人有：" << a << endl;
}

int main()
{
	test1();
	cout << endl;
	test2();
	system("pause");
	return 0;
}


常用排序算法

算法简介：

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

sort

功能：对容器内的元素进行排序

函数原型

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

例子

void Printf(int v)
{
	cout << v << " ";
}

void test()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(40);
	v.push_back(20);
	v.push_back(50);
	//默认排序 升序
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), Printf);
	cout << endl;

	//改变为降序
	sort(v.begin(), v.end(),greater<int> ());
	for_each(v.begin(), v.end(), Printf);
	cout << endl;
}

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


random_ shuffle

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

函数原型

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

例子

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

void test()
{
	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(), Printf);
	cout << endl;
}

int main()
{
	srand((unsigned int) time(NULL));
	test();
	system("pause");
	return 0;
}

总结：random_ shuffle洗牌算法比较实用，使用时记得加上随机数种子


merge

功能：容器元素合并，并存储到另一容器中

函数原型：

merg(iterator beg1, iterator end1, iterator beg2, iterator end2 ,iterator dest);
//容器元素合并，并存储到另一容器中
//注意：两个容器必须是有序的
//beg1 容器1开始迭代器
//end1 容器1结束迭代器
//beg2 容器2开始迭代器
//end2 容器2结束迭代器
//dest 目标容器开始迭代器

例子

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

void test()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 5; 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(), Printf);
	cout << endl;
}

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

总结：1、合并前的源容器必须是有序的。

2、合并前必须给目标容器开辟空间


reverse

功能：将容器内元素进行反转

函数原型

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

例子

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

void test()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	cout << "反转前：" << endl;
	for_each(v.begin(), v.end(), Printf);
	cout << endl;
	cout << "---------------------"<<endl;
	cout << "反转后：" << endl;
	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), Printf);
	cout << endl;
}

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

常用拷贝和替换算法

算法简介

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

copy

功能：容器内指定范围的元素拷贝到另一容器中

函数原型

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

例子

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

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());
	cout << "v1的元素：";
	for_each(v1.begin(), v1.end(), Printf);
	cout << endl;
	cout << "v2的元素：";
	for_each(v2.begin(), v2.end(), Printf);
	cout << endl;

}

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

总结：利用copy算法在拷贝时，目标容需要提前开辟空间


replace

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

函数原型

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

例子：

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

void test()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);
	v.push_back(10);
	//将v容器中的10替换成60
	cout << "替换前：" << endl;
	for_each(v.begin(), v.end(), Printf);
	cout << endl;
	cout << "替换后：" << endl;
	replace(v.begin(), v.end(), 10, 60);
	for_each(v.begin(), v.end(), Printf);
	cout << endl;
}

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


replace_if

功能：容器内指定范围满足条件的元素替换为指定元素

函数原型

replace_if(iterator beg, iterator end, _pred, newvalue);
//按条件替换元素，满足条件的替换成指定元素
//beg 开始迭代器
//end 结束迭代器
//_pred 谓词
//newvalue 替换的新元素

例子

class compare
{
public:
	bool operator()(const int& a)
	{
		return a > 20;
	}
};

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

void test()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(20);
	v.push_back(21);
	v.push_back(30);
	v.push_back(40);
	v.push_back(10);
	cout << "替换前：" << endl;
	for_each(v.begin(), v.end(), Printf);
	cout << endl;
	//将大于20的数替换成1000
	cout << "替换后：" << endl;
	replace_if(v.begin(), v.end(), compare(), 1000);
	for_each(v.begin(), v.end(), Printf);
	cout << endl;
}

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

swap

功能：互换两个容器的元素

函数原型

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

  例子

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

void test()
{
	vector<int> v1;
	vector<int> v2;
	v2.push_back(1111);
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i + 100);
	}
	
	cout << "交换前：" << endl;
	for_each(v1.begin(), v1.end(), comper());
	cout << endl;
	for_each(v2.begin(), v2.end(), comper());
	cout << endl;
	cout << "交换后：" << endl;
	swap(v1, v2);
	for_each(v1.begin(), v1.end(), comper());
	cout << endl;
	for_each(v2.begin(), v2.end(), comper());
	cout << endl;
}

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

总结：swap交换容器时，注意交换的容器需要同种类型。

常用算术生成算法

算法简介

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

注意：

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

accumulate

功能：计算区间内，容器元素累计总和

函数原型

accumulate(iterator beg, iterator end, value);
//计算容器中元素累计总和
//beg 开始迭代器
//end 结束迭代器
//value 起始值

例子

void test()
{
	vector<int> v;
	for (int i = 0; i <= 100; i++)
	{
		v.push_back(i);
	}
	int total=accumulate(v.begin(), v.end(), 0); //5050
	cout << "total=" << total << endl;
	//如果起始值为1000
	int total2 = accumulate(v.begin(), v.end(), 1000); //6050
	cout << "total2=" << total2 << endl;
}

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

fill  

功能：向容器中填充指定元素

函数原型：

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

例子

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

void test()
{
	vector<int> v;
	v.resize(10);
	fill(v.begin(), v.end(), 100);
	for_each(v.begin(), v.end(), Printf);
	cout << endl;
	
}

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

常用集合算法

算法简介

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

set_intersection

功能：求两个容器的交集

函数原型

set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
//求两个容器的交集，返回相交的最后一个元素迭代器位置
//注意：两个集合必须是有序序列
//beg1 容器1开始迭代器
//end1 容器1结束迭代器
//beg2 容器2开始迭代器
//end2 容器2结束迭代器
//dest 目标容器开始迭代器

例子

oid Printf(int a)
{
	cout << a << " ";
}

void test()
{
	vector<int> v1;
	vector<int> v2;
	vector<int> v3;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i+5);
	}
	v3.resize(min(v1.size(),v2.size()));
	vector<int>::iterator it=set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	for_each(v3.begin(), it, Printf);
	cout << endl;
}

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

总结：

1、求交集的两个集合必须是有序序列

2、目标容器开辟的空间需要从两个容器中取小值

3、set_intersection返回值既是交集中最后一个元素的位置

set_union

功能：求两个容器的并集

函数原型

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
//求两个容器的并集
//注意：两个集合必须是有序序列
//beg1 容器1开始迭代器
//end1 容器1结束迭代器
//beg2 容器2开始迭代器
//end2 容器2结束迭代器
//dest 目标容器开始迭代器

例子

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

void test()
{
	vector<int> v1;
	vector<int> v2;
	vector<int> v3;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i+5);
	}
	v3.resize(v1.size()+v2.size());
	vector<int>::iterator it=set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	for_each(v3.begin(), it, Printf);
	cout << endl;
}


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

总结：

1、求并集的两个集合必须的有序序列

2、目标容器开辟空间需要两个容器相加

3、set_union返回值既是并集中最后一 个元素的位置

set_difference    

功能：求两个容器的差集

函数原型：

set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
//求两个容器的差集
//注意：两个集合必须是有序序列
//beg1 容器1开始迭代器
//end1 容器1结束迭代器
//beg2 容器2开始迭代器
//end2 容器2结束迭代器
//dest 目标容器开始迭代器

例子

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

void test()
{
	vector<int> v1;
	vector<int> v2;
	vector<int> v3;
	vector<int> v4;
	for (int i = 0; i < 10; i++)
	{
		v1.push_back(i);
		v2.push_back(i+5);
	}
	v3.resize(max(v1.size(),v2.size()));
	cout << "v1和v2的差集为：" << endl;
	vector<int>::iterator it= set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	for_each(v3.begin(), it, Printf);
	cout << endl;

	v4.resize(max(v1.size(), v2.size()));
	cout << "v2和v1的差集为：" << endl;
	vector<int>::iterator it1 = set_difference( v2.begin(), v2.end(),v1.begin(), v1.end(), v4.begin());
	for_each(v4.begin(), it1, Printf);
	cout << endl;
}


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

总结：

1、求差集的两个集合必须的有序序列

2、目标容器开辟空间需要从两个容器取较大值

3、set_difference返回值既是差集中最后一 个元素的位置


相关文章