32. STL算法库详解

1.前言

STL内容的最后就是我们的STL提供的强大算法函数了,这些算法所在头文件:

#include<algorithm>

2.排序函数

首先是最常用的排序函数:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int num[5] = { 4,1,6,7,0 };
	vector<int> v{ 5,1,3,8,7 };
	//默认升序
	sort(num, num + 5);
	sort(v.begin(), v.end());
}

即可以排序普通数组,也可以排序容器。

可以在第三个参数填入自定义排序规则(后续函数同理, 不再赘述):

	vector<int> v{ 5,1,3,8,7 };

	sort(v.begin(), v.end(),std::greater<int>()); //使用标准库的排序规则

	//填入lambda表达式,或函数, 自定义排序规则, 该函数有两个参数, 参数类型为你要排序的元素类型, 返回前一个大于后一个为true,则为降序
	sort(v.begin(), v.end(), [](int a, int b) {
		return a > b;
		});

上面的sort函数,如果排序的数据中存在相同元素,它不能保证这些元素的相对顺序,所以可以采用stable_sort

	vector<int> v{ 5,1,1,8,7 };
	stable_sort(v.begin(), v.end());

它能保证相同的元素,相对位置不变,即前面的元素,一定在其它相等元素的前面。

有时候我们仅仅只想要取出100万个数据中最大的十个数据,如果按上面全排的话,有点没必要了,所以就可以用partial_sort函数

	vector<int> v{ 5,1,3,8,7 };
	partial_sort(v.begin(), v.begin()+3,v.end()); //将最小的三个元素放在前三个位置,需要自定义规则的,填第4个参数

前两个参数决定了我们需要选取多少个元素,并且第1与第3参数决定了选取的范围。

但它会更改原数据,如果不想更改原有数据,可以使用partial_sort_copy

	vector<int> v{ 5,1,3,8,7 };
	vector<int> result(3); //保存排序结果
	partial_sort_copy(v.begin(), v.end(), result.begin(), result.end());

最后两个参数为保存结果的迭代器范围,前两个迭代器则表示排序的数据范围,如果要自定义排序,则继续填第5个参数填入lambda表达式等等。

上面我们是想要得到前几大(或小)的元素,但有时我们只想要得到第几大的元素,那么就可以使用nth_element

	vector<int> v{ 5,1,3,8,7 };
	nth_element(v.begin(), v.begin() + 2, v.end());

它的原理是将第二个参数减去第一个参数作为要求的第几大元素,并将结果移动到第二个迭代器所在位置。

有时我们可能需要判断一个容器中的数据是否已经是排序的状态:

	vector<int> v{ 5,1,3,8,7 };
	is_sorted(v.begin(), v.end()); //判断是否为升序排序, 是返回true.否返回false
	is_sorted_until(v.begin(), v.end()); //判断是否为升序排序, 是返回迭代器的end, 否则返回破坏该排序的第一个元素迭代器

有时我们可能还需要将两个已经排好序的合并:

	vector<int> v1{ 1,2,3};
	vector<int> v2{ 4,5,6};
	vector<int> v3(6);

	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3); //将合并排序的结果保存到最后一个参数

或者在同一个容器中:

	vector<int> v1{ 4,5,6,1,2,3};
	inplace_merge(v1.begin(), v1.begin() + 3, v1.end()); //将前两个迭代器之间的范围与后两个迭代器之间的范围合并

3.查找函数

除了排序以外,查找也是一个非常常用的操作:

	vector<int> v{ 4,5,6,1,2,3};
	find(v.begin(), v.end(), 6);//在前两个迭代器范围内查找第三个参数,返回找到的第一个元素的迭代器

如果没找到,则返回传入的第二个参数。

除了查找指定值,有时我们还需要查找满足指定条件的元素:

	vector<int> v{ 4,5,6,1,2,3};
	auto it=find_if(v.begin(), v.end(), [](int a) {
		return a < 3;
		});
	cout << *it;

或者是不满足条件的元素:

	vector<int> v{ 4,5,6,1,2,3};
	auto it=find_if_not(v.begin(), v.end(), [](int a) {
		return a < 3;
		});
	cout << *it;

查找失败则返回传入的第二个参数。

还有就是查找A序列中,B序列最后一次出现的位置:

	vector<int> v{ 4,5,6,1,2,3};
	vector<int> v1{ 1,2,3 };

	auto it=find_end(v.begin(), v.end(), v1.begin(), v1.end());
	cout << distance(v.begin(), it)<<endl; //输出据起始的距离

或者A序列中, 第一次出现B序列中任意一个元素的位置:

	vector<int> A{ 4,5,6,1,2,3};
	vector<int> B{ 5,3,1 };

	auto it=find_first_of(A.begin(), A.end(), B.begin(), B.end());
	cout << *it<<endl;

序列中第一个出现的是B序列中的5,则返回5对应的迭代器。

或者查找连续两个元素相等:

	vector<int> A{ 4,5,1,1,2,3};
	auto it=adjacent_find(A.begin(), A.end());
	cout << *it;

前面有find_end,与之对应的是search,用于查找A序列中出现B序列的开始位置:

	vector<int> v{ 1,2,3,4,5,6,1,2,3 };
	vector<int> v1{ 1,2,3 };
	auto it = search(v.begin(), v.end(), v1.begin(), v1.end());
	cout << distance(v.begin(), it) << endl; //输出据起始的距离

当B序列中元素元素相同时,可以使用search_n函数:

	vector<int> v{ 1,2,3,1,1,1,4,5,6,1,2,3 };
	auto it = search_n(v.begin(), v.end(), 3,1); //首次出现3个1的位置
	cout << distance(v.begin(), it) << endl; //输出据起始的距离

4.筛选函数

然后就是从数据中筛选出所有符合条件的元素:

	vector<int> v{ 1,2,3,4,5,6};

	//按自定义规则分组, 返回分界点迭代器
	auto it=partition(v.begin(), v.end(), [](int i) {
		return i % 2; //筛选奇数与偶数
		});
	//功能同上,但不会影响同组元素的相对位置
	auto it1 = stable_partition(v.begin(), v.end(), [](int i) {
		return i % 2;
		});

但上面两个函数都修改了原有数据,如果不想修改,则可以:

	vector<int> v{ 1,2,3,4,5,6};
	vector<int> a1(10);
	vector<int> a2(10);

	partition_copy(v.begin(), v.end(), a1, a2, [](int a) {
		return a % 2;
		});

它会将分组后的数据保存到第三四个参数里面。

有时候是已经分好的组,但我们想要知道两者的界限在哪里:

	vector<int> v{ 1,2,3,4,5,6};
	auto i=partition_point(v.begin(), v.end(), [](int i) {
		return i < 4;
		});

5.二分查找

前面的查找函数都是采用的顺序查找,如果数据原本就是有序的,那么顺序查找就有些低效了,所以STL也提供了二分查找的函数。

首先是查找不小于某个数的第一个元素:

	vector<int> v{ 1,2,3,4,5,6};
	auto it=lower_bound(v.begin(), v.end(), 3); //查找不小于3的数,返回迭代器,不存在则返回第二个参数,这里返回结果为指向3的迭代器

然后是查找大于某个数的第一个元素:

作者:余识
全部文章:0
会员文章:0
总阅读量:0
c/c++pythonrustJavaScriptwindowslinux