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的迭代器
然后是查找大于某个数的第一个元素: