投稿
  1. 首页
  2. C

【C++】STL常用算法

仓储笼•2022-6-12•C•阅读23

【C++】STL常用算法,第1张

这篇博客主要用来记录学习到的STL中的常用算法和它们的使用方法。

目录

遍历算法：

1.for_each

2.transform

查找算法：

1.find

2.find_if

3.adjancent_find

4.binary_search

5.count

6.count_if

排序算法：

1.sort

2.random_shuffle

3.merge

4.reverse

拷贝和替换算法：

1.copy

2.replace

3.replace_if

4.swap

算术算法：

1.accumulate

2.fill

集合算法：

1.set_intersection

2.set_union

3.set_difference

遍历算法： 1.for_each

for_each(容器起始位置, 容器终止位置下一位, 仿函数/普通函数)

使用方法如下图所示：

	vector v;
	v.push_back(1);
	v.push_back(1);
	v.push_back(1);
	//普通函数
    for_each(v.begin(), v.end(), print);
	//仿函数
    for_each(v.begin(), v.end(), print02());

其中它的第三个参数是输出的一个仿函数，这个仿函数可以是一个匿名对象；也可以是一个普通函数；

1.普通函数：

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

2.仿函数：

class print02
{
public:
	void operator()(int val)
	{
		cout << val << " ";
	}
};
2.transform

transform( 容器1的起始迭代器 , 容器1的终止迭代器 , 容器2的起始迭代器 , 转移 *** 作函数 )

这个算法主要用来将容器1中的数据传递到容器2中，并且在传递中可以通过某个函数实现一种功能。

这里先列出几个注意事项：

1.将容器1中的数据搬到容器2前，需要对容器2的大小进行指定。这个 *** 作一般使用resize成员函数，而不用之前的reserve成员函数。reserve的作用一般是让起始迭代器在容器增长过程中不发生变化。

2.转移的 *** 作函数需要返回类型，即使不需要对数据进行改变，也需要写一个转移的 *** 作函数，它需要返回值， *** 作函数的返回值不能为空。

下面为一次转移过程：

	vector v;
	vector v2;
	v2.resize(6);
	transform(v.begin(), v.end(), v2.begin(), fun);

由于不需要在转移过程中对数据进行修改，所以 *** 作函数不需要起作用。所以默认返回每个数据自身就行了，这里不能不返回数据！！！不能用void

int fun(int val)
{
	return val;
}

当然，要是想在搬过去时将每个数都进行加1也可以改变 *** 作函数实现方式即可：

int fun(int val)
{
	return ++val;
}
查找算法： 1.find

find( 起始迭代器 , 终止迭代器 , 需要查找的元素 )

find是用来查找容器中是否存在某个元素的算法，如果查到了，就返回元素对应的迭代器，没查到，就返回终止迭代器。

find算法也可以用来查找一些不是内置数据类型的数据，当然，我们需要重载运算符才能进行比较。

下面是 *** 作示例：通过查找算法查找一个自定义数据类型的对象。

class Stu
{
public:
	Stu(int id, int num)
	{
		this->id = id;
		this->num = num;
	}
    //重载运算符
	bool operator==(const Stu &s1)
	{
		if (s1.id == this->id && s1.num == this->num)
		{
			return true;
		}
	}
    //
	int id;
	int num;
};

void test01()
{
	vector stu1;
	Stu s1(1, 11);
	Stu s2(2, 1);
	Stu s3(3, 152);
	Stu s4(4, 123);
	Stu s5(5, 17);
	stu1.push_back(s1);
	stu1.push_back(s2);
	stu1.push_back(s3);
	stu1.push_back(s4);
	stu1.push_back(s5);
	Stu s6(4, 123);
	if (find(stu1.begin(), stu1.end(), s6)!=stu1.end())
	{
		cout<<"找到了" << endl;
	}
	else
	{
		cout<<"找不到" << endl;
	}
2.find_if

find_if(容器起始迭代器 , 容器终止迭代器 , 谓词)

这个算法主要用于查找符合一定条件的元素，这个元素需要符合谓词的条件设定。例如我们就可以通过下面这个查找学生对象中符合年龄大于19的第一个学生。而且这个算法里的谓词是一个一元谓词。

//类
class Stu
{
public:
	Stu(int id, int age)
	{
		this->id = id;
		this->age = age;
	}
	int id;
	int age;
};

//一元谓词
class Pred
{
public:
	bool operator()(Stu s1)
	{
		if (s1.age >19)
			return true;
		else
			return false;
	}
};


int main()
{
	vector st1;
	Stu s1(1, 19);
	Stu s2(5, 18);
	Stu s3(9, 21);
	Stu s4(3, 20);
	Stu s5(7, 18);
	find_if(st1.begin(), st1.end(), Pred());
	return 0;
}
3.adjancent_find

adjancent_find(容器起始迭代器 , 容器终止迭代器);

adjancent_find查找算法主要用于查找相邻的两个重复元素。如果容器中存在两个相邻的元素相同，那么返回第一个元素的位置，否则返回终止位置的迭代器。这里貌似不能用于查找自定义的数据类型。

	vector v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(8);
	v1.push_back(9);
	v1.push_back(9);
	vector::iterator it;
	it=adjacent_find(v1.begin(), v1.end());
	if (it == v1.end())
	{
		cout<<"没找到" << endl;
	}
	else
	{
		cout<<"找到了！" << endl;
	}
4.binary_search

binary_search( 容器起始迭代器 , 容器终止迭代器 , 要查找的元素 );

这个是二分查找算法，它是一种效率很高的算法，但是它有一个很重要的前提，就是查找的容器中的元素必须是有序的，否则它的查找结果是未定义的。并且它不会返回迭代器，它查找到就返回真，否者返回假。如果我们想比较一些非内置数据类型的自定义数据，我们需要在这些自定义数据的类内部重载“==” *** 作符。这个 *** 作也可以用于其他的算法中。

	vector v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(8);
	v1.push_back(9);
	v1.push_back(10);
	if (binary_search(v1.begin(), v1.end(), 8))
		cout << "true" << endl;
	else
	{
		cout << "false" << endl;
	}
5.count

count( 容器的起始迭代器 , 容器的终止迭代器 , 要统计的元素);

count算法可以用于查找某个元素在容器中出现的次数，它返回一个整形数据，就是这个容器中要统计的元素的个数。

下列代码就可以用于统计容器st1中年龄相同的学生对象的个数。

class Stu
{
public:
	Stu(int id, int age)
	{
		this->id = id;
		this->age = age;
	}
	bool operator==(const Stu& s1)
	{
		if (s1.age == this->age)
			return true;
		else
			return false;
	}
	int id;
	int age;
};

int main()
{
	vector st1;
	Stu s1(1, 19);
	Stu s2(6, 18);
	Stu s3(9, 21);
	Stu s4(7, 18);
	Stu s5(2, 18);
	st1.push_back(s1);
	st1.push_back(s2);
	st1.push_back(s3);
	st1.push_back(s4);
	st1.push_back(s5);
	Stu need_find(7, 18);
	int num = count(st1.begin(), st1.end(), need_find);
	cout << num << endl;
	return 0;
}
6.count_if

count_if( 容器的起始迭代器 ,  容器的终止迭代器 ,  谓词);

这个算法也用于计算一个容器中某个元素的数量，其中它还增加了一种统计的方法，就是满足这个谓词的一个函数对象。

下面是一个自定义的数据类型使用这种算法的例子，目的是去计算容器中满足年龄大于18的元素个数：

class Info
{
public:
	Info(int age, int id)
	{
		this->id = id;
		this->age = age;
	}
	int age;
	int id;
};

//谓词
class Com
{
public:
	bool operator()(const Info& s)
	{
		if (s.age > 18)
			return true;
		else
			return false;
	}
};

int main()
{
	vector v;
	Info s1(17, 6);
	Info s2(18, 3);
	Info s3(17, 1);
	Info s4(21, 7);
	Info s5(20, 9);
	Info s6(23, 0);
	v.push_back(s1);
	v.push_back(s2);
	v.push_back(s3);
	v.push_back(s4);
	v.push_back(s5);
	v.push_back(s6);
	int num = count_if(v.begin(), v.end(),Com());
	cout<
排序算法： 1.sort

sort( 容器的起始迭代器 ,  容器的终止迭代器  ,  谓词 );

sort是用来对容器内的元素进行排序的算法，它默认的排序顺序是从小到大，当然，如果我们想对这种顺序进行修改，我们也可以通过修改谓词的执行方式来进行改变。

下面例子就是对一个普通内置数据类型的排序，其中，我们可以通过修改谓词来进行自定义数据类型的排序。

class mysort
{
public:
	bool operator()(int v1,int v2)
	{
		if (v1 > v2)
			return true;
		else
			return false;
	}
};

int main()
{
	vector v1;
	v1.push_back(3);
	v1.push_back(6);
	v1.push_back(1);
	v1.push_back(0);
	v1.push_back(0);
	v1.push_back(9);
	//sort(v1.begin(), v1.end());
	sort(v1.begin(), v1.end(), mysort());
	return 0;
}

当然，对于自定义的数据类型这里我们不仅可以利用谓词来进行排序，还可以在类内通过重载运算符的方式来定义一种比较方式。

class Stu
{
public:
    //这里只能重载小于号，不能重载大于号...
	bool operator<(const Stu& s2)
	{
		if (s2.age > this->age)
			return true;
		else
			return false;
	}
	Stu(int age, int id)
	{
		this->age = age;
		this->id = id;
	}
	int age;
	int id;
};

void print(Stu& s)
{
	cout< v1;
	Stu s1(29, 2);
	Stu s2(20, 1);
	Stu s3(21, 9);
	v1.push_back(s1);
	v1.push_back(s2);
	v1.push_back(s3);
	sort(v1.begin(),v1.end());
	for_each(v1.begin(),v1.end(),print);
	return 0;
}
2.random_shuffle

random_shuffle( 容器的起始迭代器 ,  容器的终止迭代器  );

这个算法用于打乱容器中的数据的顺序，它的打乱是“随机的”，但不是每一次都是随机的，所以我们要添加一个随机数种子。

	srand((unsigned)time(NULL));
	vector v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);
	for_each(v1.begin(), v1.end(), print);
	cout << endl;
	random_shuffle(v1.begin(), v1.end());
	for_each(v1.begin(), v1.end(), print);
3.merge

merge( 第一个容器的起始迭代器 , 第一个容器的终止迭代器 , 第二个容器的起始迭代器 , 第二个容器的终止迭代器 , 目标容器的起始迭代器 );

merge算法用于将两个有序的、且数据大小顺序相同的容器进行合并，它与前面的transform遍历算法有一个类似的地方，就是用于接受的容器必须要提前分配好内存空间。

	vector v1;
	vector v2;
	//v1
    v1.push_back(1);
	v1.push_back(6);
	v1.push_back(7);
	v1.push_back(11);
	//v2
    v2.push_back(9);
	v2.push_back(13);
	v2.push_back(18);
	v2.push_back(22);
	vector Get;
	Get.resize(v1.size()+v2.size());
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), Get.begin());
4.reverse

reverse( 容器的起始迭代器 , 容器的终止迭代器 );

这个算法没什么好说的，就是将容器内的数据反转。例如1 6 3 8 5就变成 5 8 3 6 1

    vector v1;
	v1.push_back(1);
	v1.push_back(9);
	v1.push_back(6);
	v1.push_back(7);
	reverse(v1.begin(), v1.end());
拷贝和替换算法： 1.copy

copy( 第一个容器的起始迭代器 , 第一个容器的终止迭代器  , 第二个容器的起始迭代器 );

这个算法主要用于将一个容器中的数据复制到另一个容器中，而与前面类似，第二个容器也是需要提前开辟空间。其实这个算法的作用于等号赋值区别不大。

	vector v1;
	v1.push_back(1);
	v1.push_back(9);
	v1.push_back(6);
	v1.push_back(7);
	vectorv2;
	v2.resize(4);
	copy(v1.begin(), v1.end(), v2.begin());
2.replace

replace(  容器的起始迭代器, 容器的终止迭代器 , 要被替换的旧元素 , 要去替换的新元素);

replace是一个替换容器内特定元素的算法，它的实现是将容器内所有的特定旧元素全部替换为新的元素。

	vector v1;
	v1.push_back(7);
	v1.push_back(1);
	v1.push_back(9);
	v1.push_back(7);
	v1.push_back(6);
	v1.push_back(7);
	v1.push_back(7);
	replace(v1.begin(), v1.end(), 7, 20);
	for_each(v1.begin(), v1.end(), print);
3.replace_if

replace_if(容器的起始迭代器 , 容器的终止迭代器 , 谓词 , 要去替换的新元素 );

replace_if这个算法也是用于替换一个容器中的符合某种特性的元素，这个衡量标准就是谓词。我们可以通过设计谓词来规定一个要被替换的旧元素的区域。

下面是一个将容器中满足数值为7的元素被替换成20的例子：

class Pred
{
public:
	bool operator()(int val)
	{
		if (val == 7)
			return true;
		else
			return false;
	}
};

int main()
{
	vector v1;
	v1.push_back(7);
	v1.push_back(1);
	v1.push_back(9);
	v1.push_back(7);
	v1.push_back(6);
	v1.push_back(7);
	v1.push_back(7);
	replace_if(v1.begin(), v1.end(), Pred(), 20);
	for_each(v1.begin(), v1.end(), print);
	return 0;
}
4.swap

swap(第一个容器名, 第二个容器名);

swap的作用是将两个容器内容交换，它不需要考虑容器的大小是否相同，但是不同的容器不能交换。

下面就是交换两个不同大小的容器的例子：

int main()
{
	vector v1;
	v1.push_back(7);
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(6);
	v1.push_back(7);
	v1.push_back(9);
	vectorv2;
	v2.push_back(2);
	v2.push_back(1);
	swap(v1, v2);
	for_each(v1.begin(), v1.end(), print);
	cout << endl;
	for_each(v2.begin(), v2.end(), print);
	return 0;
}
算术算法： 1.accumulate

accumulate( 容器的起始迭代器 , 容器的终止迭代器 , 起始数据 );

这个算法可以用于将容器内所有的数据都进行相加 *** 作，然后返回所有容器内数据的和加上起始数据的值。这里要想要对自定义数据类型进行使用，可以在类内重载对应运算符。

下面是一个将容器内所有元素相加，并且起始数据为30的例子：

	vector v1;
	v1.push_back(2);
	v1.push_back(20);
	v1.push_back(23);
	v1.push_back(7);
	v1.push_back(8);
	int num=accumulate(v1.begin(),v1.end(),30);
	cout << num;
2.fill

fill( 容器的起始迭代器 , 容器的终止迭代器  , 用来填充的元素 );

fill算法是用来对容器进行填充的，它会对容器大小内所有元素进行填充替换，即使原来有元素的地方也会被替换。

下面是一个有元素的容器被填充的例子，填充完后容器内所有元素都会被换成用来填充的元素。

	vector v1;
	v1.resize(10);
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	fill(v1.begin(), v1.end(), 100);
	for_each(v1.begin(), v1.end(), print);
集合算法： 1.set_intersection

set_intersection( 容器一的起始迭代器 , 容器一的终止迭代器 , 容器二的起始迭代器 , 容器二的终止迭代器 ,  接收容器起始迭代器 );

这个算法用于求两个同向且有序的容器的交集并放入另一个容器种。两个容器都必须有顺序，并且两容器的顺序增长方向要一致（即不能够0，1，2，3，另一个容器8，6，4，2）。与前面类似，而且这个容器用来接收数据的容器也必须要提前分配内存。但是接收容器的大小如何确定？这里我们利用集合的知识可以判断，两个集合的交集范围就是从0到两个集合中最小的那个集合，所有我们接收容器的大小取两个容器中最小的那个容器的大小。不过要是两容器的交集比其中最小的容器小，那么接收容器中多余部分就是0。而且我们也有方法取到最后一个非0的数据，这个算法本身就返回两容器交集的最后一个元素的迭代器。

下面就是一个例子：

	vector v1;
	v1.push_back(6);
	v1.push_back(8);
	v1.push_back(11);
	v1.push_back(12);
	vector v2;
	v2.push_back(6);
	v2.push_back(9);
	v2.push_back(11);
	vector v3;
	v3.resize(min(v1.size(), v2.size()));
	vector::iterator it = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),v3.begin());
    //不用算法返回的迭代器，输出6 11 0 
	//for_each(v3.begin(), v3.end(), print);
	//用算法返回的迭代器，输出6 11
    for_each(v3.begin(), it, print);
2.set_union

set_union( 容器一的起始迭代器 , 容器一的终止迭代器 , 容器二的起始迭代器 , 容器二的终止迭代器 ,  接收容器起始迭代器 );

这个容器用于接收两个容器的并集，它的作用于注意事项和交集相同，不过它不同的是它的大小取两个容器的这种情况。

下面就是一个使用例子：

	vector v1;
	v1.push_back(6);
	v1.push_back(8);
	v1.push_back(11);
	v1.push_back(12);
	vector v2;
	v2.push_back(6);
	v2.push_back(9);
	v2.push_back(11);
	vector v3;
	v3.resize(v1.size()+v2.size());
	vector::iterator it = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(),v3.begin());
	for_each(v3.begin(), v3.end(), print);
	cout << endl;
	for_each(v3.begin(), it, print);
3.set_difference

set_difference( 容器一的起始迭代器 , 容器一的终止迭代器 , 容器二的起始迭代器 , 容器二的终止迭代器 , 接收容器的起始迭代器 );

这个算法用于计算两个容器的差集，所谓容器的差集，就是一个容器中有而另一个容器中没有的元素。

例如集合A：1，2，3，4，5；集合B：3，4，5，6，7

那么集合A和集合B的差集就是集合A中有，而集合B中没有的元素：1，2；

那么集合B和集合A的差集就是集合B中有，而集合A中没有的元素：6，7；

其他注意事项和一开始的集合算法类似，就是需要注意接受容器的大小取两容器中最大的那个容器，考虑两容器没有交集的情况。

下面就是一个例子：

	vector v1;
	v1.push_back(1);
	v1.push_back(3);
	v1.push_back(5);
	v1.push_back(7);
	vector v2;
	v2.push_back(1);
	v2.push_back(5);
	v2.push_back(8);
	vector v3;
	v3.resize(max(v1.size(),v2.size()));
	//vector::iterator it = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
	vector::iterator it = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v3.begin());
	for_each(v3.begin(), it, print);

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/1324050.html

赞 (0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
仓储笼仓储笼一级用户组
00
上一篇 2022-06-12
下一篇2022-06-12

发表评论

登录后才能评论

评论列表（0条）

    保存