标准库中涉及比较函数的常用用法整理

时间:2022-03-09 23:18:35

标准库中常用的需要定义比较函数的工具:

sort 排序

priority_queue 优先队列(或称堆)

lower_bound upper_bound 二分查找

nth_element 找数组第n大

set 集合

map 映射表

常用的定义比较函数的方法:

对于普通的数据类型,如int,double,或已经重载好大于小于号的类库,如string,直接使用大于小于号

greater和less函数

对于自定义的结构体和类,重载大于小于运算符

自定义比较函数

sort:

用法:sort(首个元素地址,最后一个元素的元素的地址的后一个,比较函数)

int a[10]={7,8,1,2,4,5,6,0,3,9};
sort(&a[0],&a[10],less<int>());
for(int i=0;i<10;i++){
    printf("%d ",a[i]);
}
// 0 1 2 3 4 5 6 7 8 9

如果比较函数是less就是从小到大排序,如果比较函数是greater就是从大到小排序。

省略比较函数,就默认是less

priority_queue

用法:

定义:priority_queue<类型,容器,比较函数>

方法:

push() 往堆中放元素

top() 取堆顶

pop() 弹出堆顶

size() 询问堆大小

由于priority_queue类没有自己实现存储功能,因此必须借用vector作为存储容器

int a[10]={7,8,1,2,4,5,6,0,3,9};
priority_queue<int,vector<int>,less<int> >que;
//注意定义时要把两个连在一起的,包裹template的尖括号用空格隔开,否则编译器会认为这是一个位移运算符并报错
for(int i=0;i<10;i++){ que.push(a[i]); }
printf("%d\n",que.size());
for(int i=0;i<10;i++){ printf("%d ",que.top()); que.pop(); }
//9 8 7 6 5 4 3 2 1 0

很迷的是,priority_queue如果用less作为比较函数,会是个大顶堆,用greater却是个小顶堆.

如果您知道这种机制的意义何在,恳请在下方留言区告诉我,我会非常感谢。

也可以省略比较函数,则默认为less.

lower_bound/upper_bound

用法:

lower_bound(首个元素地址,最后一个元素地址的后一个,关键字,比较函数)

upper_bound(首个元素地址,最后一个元素地址的后一个,关键字,比较函数)

lower_bound,upper_bound必须在排好序的数组上调用才有意义,如果排序用的是sort,那么它们用的比较函数应该和sort相同,如果sort省略了比较函数,它们也应当省略。

如果数列从小到大排序,那么lower_bound返回的是第一个大于等于关键字的元素的地址,upper_bound返回的是第一个大于关键字的元素的地址

如果数列从大到小排序,那么lower_bound返回的是第一个小于等于关键字的元素的地址,upper_bound返回的是第一个小于关键字的元素的地址

int a[10]={1,3,1,4,2,3,5,7,9,4};
sort(&a[0],&a[10],less<int>());
for(int i=0;i<10;i++){
    printf("%d ",a[i]);
}
printf("\n");
printf("%d\n",*lower_bound(&a[0],&a[10],3,less<int>()));
printf("%d\n",*upper_bound(&a[0],&a[10],3,less<int>()));
//1 1 2 3 3 4 4 5 7 9
//3
//4

有个小技巧,某地址减去第0位的地址,等于它的下标

printf("%d\n",lower_bound(&a[0],&a[10],3,less<int>())-&a[0]);
//4

 

nth_element

用法 nth_element(首个元素地址,要找的第n个地址,最后一个元素的后一个,比较函数)

这个函数用来找数组中第n大的元素,工作原理类似于快排的第一步。

如果比较函数是less,那么,第n小的数放在第n位,比它小的在左边,比它大的在右边,但具体在哪不确定

如果比较函数是greater,那么,第n大的数放在第n位,比它大的在左边,比它小的在右边,但具体在哪不确定

可以看出,比较函数的方向和sort一样,就是相当于一个弱化的sort,但只有第n位在他该在的位置。

同样和sort一样,省略比较函数就默认为less

int a[10]={7,8,1,2,4,5,6,0,3,9};
nth_element(&a[0],&a[3],&a[10],less<int>());
for(int i=0;i<10;i++)printf("%d ",a[i]);
//1 0 2 3 4 5 6 8 7 9

set和map

用法:

定义:

set<数据类型,比较函数> 

map<索引的类型,值的类型,比较函数>

不去深究他们的内部实现,这两者相当于一个有序数列,你每次扔进去一个东西它们就会自动让开一个位置,每次拿走一个东西他们就会自动补上位置,保证这个数列始终是有序的。

有关于set和map的介绍很多,这里仅探讨有关于比较函数的使用方法。

同sort一样,less是从小到大,greater是从大到小,

二者可以省略比较函数的定义,默认为less。

set<int,greater<int> >s;
s.insert(1);
s.insert(8);
s.insert(2);
s.insert(6);
set<int,greater<int> >::iterator it;
for(it=s.begin();it!=s.end();it++){
    printf("%d ",*it);
}
//8 6 2 1

重载运算符

greater和less是依托于大于小于号的,自定义的类或结构体默认没有大于小于号,就需要我们自己定义一个。

假如我定义了一个结构体,里面有两个int元素x和y,但我只想把y作为排序关键字,那么我们可以通过如下方式将大于,小于号重载。

struct Example{
    int x,y;
    friend bool operator >(const Example &a,const Example &b){
        return a.y>b.y;
    }
    friend bool operator <(const Example &a,const Example &b){
        return a.y<b.y;
    }
}example;

然后就可以像普通数据类型一样调用greater和less了。

注意,重载运算符中,将传入的参数限制为引用和常量不是必须的,因为一般结构体都比较大,每次比大小都搞出一个拷贝会浪费时间和空间,所以调用引用。又因为比大小的运算在逻辑上不应该修改比大小的两个元素的值,所以限制为常量。

自定义比较函数

如果我们要给某种类型的元素多次以不同的方式排序,因为运算符不可能你想什么时候重载就什么时候重载,或者有一些很奇葩的需求,这时候就需要自定义一个比较函数。

比如我想把int元素以这样的方式排序:所有奇数放在所有偶数前面,奇偶性相同的从小到大排,那么我们就可以定义这样一个比较函数:认为奇数比偶数小,奇偶性相同的,按照正常方式比大小。然后把这个比较函数作为参数传给sort。

inline bool cmp(const int &x,const int &y){
    if((x&1)!=(y&1)){
        return x&1;
    }else return x<y;
}
int main(){
    int a[10]={7,8,1,2,4,5,6,0,3,9};
    sort(&a[0],&a[10],cmp);
    for(int i=0;i<10;i++)printf("%d ",a[i]);
    return 0;
}
//1 3 5 7 9 0 2 4 6 8

自定义比较函数,如果其核心操作的符号是小于号,就对应着less,如果其核心操作的符号是大于号,就对应着greater