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函数: