算法设计与分析课件 06 STL常用函数

算法设计与分析本节要点CONTENTSSTL常用函数STL常用函数STL在头文件#include<algorithm>中提供了一些常用函数。（1）min(x,y)：求两个元素的最小值。（2）max(x,y)：求两个元素的最大值。（3）swap(x,y)：交换两个元素。（4）find(begin,end,x)：返回指向区间[begin,end)第1个值为x的元素指针。如果没找到，则返回end。（5）count(begin,end,x)：返回指向区间[begin,end)值为x的元素数量，返回值为整数。STL常用函数（6）reverse(begin,end)：翻转一个序列。（7）shuffle(begin,end)：随机打乱一个序列。（8）unique(begin,end)：将连续的相同元素压缩为一个元素，返回去重后的尾指针。不连续的相同元素不会被压缩，因此一般先排序后去重。（9）fill(begin,end,val)：将区间[begin,end)的每个元素都设置为val。STL常用函数（10）sort(begin,end,compare)：对一个序列排序，参数begin和end表示待排序数组的首地址和尾地址；compare表示排序的比较函数，可省略，默认为升序。stable_sort(begin,end,compare)为稳定排序，即保持相等元素的相对顺序。（11）nth_element(begin,begin+k,end,compare)：使区间[begin,end)第k小的元素处在第k个位置上，左边元素都小于或等于它，右边元素都大于或等于它，但并不保证其他元素有序。STL常用函数（12）lower_bound(begin,end,x)/upper_bound(begin,end,x)利用二分查找的方法，在有序数组中查找第1个满足条件(≥、>)的元素，返回指向该元素的指针。（13）next_permutation(begin,end)/prev_permutation(begin,end)next_permutation()是求按字典序的下一个排列的函数；prev_permutation()是求按字典序的上一个排列的函数。STL常用函数1．fillfill(begin,end,val)将区间[begin,end)的每个元素设置为val。与#include<cstring>中的memset不同，memset是按字节填充的。例如，int占4字节，因此memset(a,0x3f,sizeof(a))按字节填充相当于将0x3f3f3f3f赋值给数组a[]的每个元素。memset经常用来初始化一个int型数组为0、-1，或者最大值、最小值，也可以初始化一个bool型数组为true(1)或false(0)。STL常用函数注意：不可以用memset初始化一个int型数组为1，因为memset(a,1,sizeof(a))相当于将每个元素都赋值为00000001000000010000000100000001，即将00000001分别填充到4字节中。布尔数组可以赋值为true，是因为布尔数组中的每个元素只占1字节。STL常用函数注意：动态数组或数组作为函数参数时，不可以用sizeof(a)测量数组空间，因为这样只能测量到首地址的空间。可以用memset(a,0x3f,n*sizeof(int))的方法处理，或者用fill函数填充。如果用memset(a,0x3f,sizeof(a))填充double类型的数组，则经常会得到一个连1都不到的小数。double类型的数组填充极值时需要用fill(a,a+n,0x3f3f3f3f)。第9页STL常用函数和容器2．sortsort(begin,end,compare)用于对一个序列进行排序。其中，参数begin和end分别表示待排序数组的首地址和尾地址；compare表示用于排序的比较函数，可省略，默认为从小到大排序。stable_sort(begin,end,compare)为稳定排序，即保持相等元素的相对顺序。第10页STL常用函数和容器（1）使用默认的函数排序。intmain(){

inta[10]={7,4,5,23,2,73,41,52,28,60};

sort(a,a+10);//将数组a[]从小到大排序

for(inti=0;i<10;i++)

cout<<a[i]<<"";

return0;}第11页STL常用函数和容器（2）自定义比较函数。sort()默认为从小到大排序。如何用sort()实现从大到小排序呢？可以编写一个比较函数来实现，自定义比较函数同样适用于结构体类型，可以指定按照结构体的某个成员进行从小到大排序或从大到小排序。第12页STL常用函数和容器boolcmp(inta,intb){returna<b;//从小到大排序，若为returna>b，从大到小排序}intmain(){inta[10]={7,4,5,23,2,73,41,52,28,60};sort(a,a+10,cmp);//将数组a[]从小到大排序

for(inti=0;i<10;i++)cout<<a[i]<<"";return0;}第13页STL常用函数和容器（3）利用functional标准库。对于简单的排序，引入头文件#include<functional>即可。functional提供了一些基于模板的比较函数对象（其中的Type表示数据类型）。

equal_to<Type>：等于。

not_equal_to<Type>：不等于。

greater<Type>：大于。

greater_equal<Type>：大于或等于。

less<Type>：小于。

less_equal<Type>：小于或等于。第14页STL常用函数和容器例如，sort(begin,end,less<type>())为从小到大排序，sort(begin,end,greater<type>())为从大到小排序。intmain(){inta[10]={7,4,5,23,2,73,41,52,28,60};sort(a,a+10,greater<int>());//从大到小排序

for(inti=0;i<10;i++)cout<<a[i]<<"";return0;}STL常用函数3．nth_element(begin,begin+k,end,compare)当省略最后一个参数时，该函数使区间[begin,end)第k（k从0开始）小的元素处在第k个位置上。当最后一个参数为greater<int>()时，该函数使区间[begin,end)第k大的元素处在第k个位置上。特别注意：在函数执行后会改变原序列，但不保证其他元素有序。STL常用函数4．lower_bound(begin,end,x)/upper_bound(begin,end,x)在从小到大的排序数组中：lower_bound(begin,end,x)：从数组的begin位置到end-1位置二分查找第1个大于或等于x的元素，找到后返回该元素的地址，不存在则返回end。upper_bound(begin,end,x)：从数组的begin位置到end-1位置二分查找第1个大于x的元素，找到后返回该元素的地址，不存在则返回end。STL常用函数5．next_permutation(begin,end)/prev_permutation(begin,end)next_permutation()是求按字典序排序的下一个排列的函数；prev_permutation()是求按字典序排序的上一个排列的函数。中位数问题分析本题很简单，可以在排序后输出中位数，或者使用nth_element函数找中