admin管理员组文章数量:1623796
目录
1.sort函数中的cmp
1.1 重载小于操作符
1.2 自定义Cmp函数
1.3 自定义仿函数
2.priority_queue中的cmp
2.1 重载小于操作符
2.2 自定义仿函数
3. 补充说明
1.sort函数中的cmp
sort函数的说明如下:
由图中可以看到,sort函数有两种原型,一种是未定义比较函数的一种是需要指定比较函数的。图中清楚写到第一种类型的比较是使用的operator<来作为比较函数的,即通过小于号来进行比较的,而第二种就需要自行定义comp比较函数了。那么比较函数有什么作用呢?再来看看下面这个说明:
这段话是对比较函数comp的解释,通过这段话揭示出最重要的意思是:comp函数用来比较两个元素a和b,通过bool型的返回值来确定a和b在严格弱排序中的相对位置,如果是true,那么a在严格弱排序序列中就在b之前,否则在b之后。
那么什么是严格弱排序呢?说得简单一点,就是序列中严格满足相邻元素i<j时,s[i]<s[j],不能取等于,个人理解:如果不做深究,可以简单的把一个严格弱排序当做是一个升序序列。
因此,在sort函数中,如果comp(a,b)为true,那么sort函数就会将a放在b的前面,否则a就放在b的后面。
是不是这样呢?我们先来看看默认方式使用的operator<。
1.1 重载小于操作符
对于operator<(a,b)来说,该重载函数的返回值必定是a<b,按照我们前面说的,如果返回值为true,那么就把a放在b前面,也就是说,如果a<b,那么a在排序后序列中是在b前面的,而这一点恰好印证了sort函数的默认排序方式为升序。为了更好的理解这一点,我们来用另一种方式来重载小于号:(重载的方式有多种,可见)
struct stu
{
string name;
int num;
int age;
bool operator<(const stu &p)const
{
return age<p.age;
}
}S[5];
int main(int argc, char *argv[])
{
S[0]={"aa",1,10};
S[1]={"bb",2,9};
S[2]={"cc",3,8};
S[3]={"dd",4,7};
S[4]={"ee",5,6};
sort(S,S+5);
for(auto s:S)
cout<<s.name<<" ";
return 0;
}
在这段程序中,小于号重载为比较两个结构体的成员变量(age)的大小,如果第一个参数的age较小,那么就将该结构体变量放在排序序列的前面。按照上面所说的,经sort排序后的结构体变量应当按age值从小到大排列,是不是这样呢?来看看运行结果 ,可以看到,这和之前分析的是一样的。那么再来看第二种自定义comp函数:
1.2 自定义Cmp函数
代码如下:
struct stu
{
string name;
int num;
int age;
}S[5];
bool cmp(const stu &q,const stu &p)
{
return q.num<p.num;
}
int main(int argc, char *argv[])
{
S[0]={"aa",1,10};
S[1]={"bb",2,9};
S[2]={"cc",3,8};
S[3]={"dd",4,7};
S[4]={"ee",5,6};
sort(S,S+5,cmp);
for(auto s:S)
cout<<s.name<<" ";
return 0;
}
运行结果为:
根据程序可知,这里自定义的cmp是将num较小的结构体放前面,运行结果也完全符合。
1.3 自定义仿函数
struct stu
{
string name;
int num;
int age;
}S[5];
struct cmp
{
operator ()(const stu &q,const stu &p)
{
return q.num>p.num;
}
};
int main(int argc, char *argv[])
{
S[0]={"aa",1,10};
S[1]={"bb",2,9};
S[2]={"cc",3,8};
S[3]={"dd",4,7};
S[4]={"ee",5,6};
sort(S,S+5,cmp());
for(auto s:S)
cout<<s.name<<" ";
return 0;
}
程序中的仿函数定义将num较大的放在前面,因此最终是按num从大到小排列的,运行结果为,不过这里需要注意的,在sort中调用cmp函数时,需要加上括号。
2.priority_queue中的cmp
priority_queue优先队列的实质还是堆排序,默认的优先队列是以大顶堆构造,即序列中最大数的优先级最高,通过top()可以访问当前优先级最高的数,pop()来弹出当前优先级最高的数。实际上,优先队列的优先级只是一种形象说法,其实质还是排序,至于为什么这样说,下面进行解释。
我们还是先来看看priority_queue中对cmp的说明:
根据这段话,可以看到priority_queue的比较函数的意义与sort函数的比较函数相类似,均是当比较函数返回true时,将第一个参数放在第二个参数前面。段末提到,默认比较函数为less<T>,和小于操作符的作用一样,即让较小的数放在前面。
这时可能就会有问题了:priority_queue的默认方式是构造大顶堆,每次top()返回当前序列中的最大值,这和比较函数有什么关系呢?实际上,优先队列内部也是排序,它的排序方式也是通过比较函数来确定的,至于排序方式和优先队列返回最大值有什么关系呢?我们来看看下面这句话:
这说明了一个问题:当你调用pop()时,实际上是弹出优先队列的序列中的最后一个数(back),而这个被弹出的数也就是priority_queue的top()。也就是说,我们所认为的top()和pop()是获取、弹出优先级最高的数,实际上这个数就是当前优先队列序列中的最后一个数。
这似乎也就不难解释cmp比较函数与优先队列返回的最大值之间的关系了:以默认的比较函数less<T>为例,它的作用是将较小的数放在前面,因此最大的数肯定就位于序列的末尾了,当调用top()函数时,返回末尾的数,也就是序列中最大的数,而pop()则弹出这个数,而这个数,通常被认为是“优先级最高”的数。
相应的,优先队列的比较函数含有一种形式是greater<T>,它的效果就与less<T>相反了,也能根据上面的分析得到解释。
那么,怎么来写priority_queue的比较函数呢?
2.1 重载小于操作符
priority_queue也是可以在不指定比较函数的情况下重载小于运算符,重载示例如下:
struct stu
{
string name;
int num;
int age;
bool operator<(const stu &p)const
{
return age>p.age;
}
}S[5];
int main(int argc, char *argv[])
{
S[0]={"aa",1,10};
S[1]={"bb",2,9};
S[2]={"cc",3,8};
S[3]={"dd",4,7};
S[4]={"ee",5,6};
priority_queue<stu>q;
for(int i=0;i<5;i++)q.push(S[i]);
while(!q.empty())
{
cout<<q.top().name<<" ";
q.pop();
}
return 0;
}
运行结果为:
此时按照age从大到小排列为aa bb cc dd ee,然后从序列尾(优先级最高)依次弹出,结果即是ee dd cc bb aa。
2.2 自定义仿函数
struct stu
{
string name;
int num;
int age;
}S[5];
struct cmp
{
operator ()(const stu &q,const stu &p)
{
return q.num<p.num;
}
};
int main(int argc, char *argv[])
{
S[0]={"aa",1,10};
S[1]={"bb",2,9};
S[2]={"cc",3,8};
S[3]={"dd",4,7};
S[4]={"ee",5,6};
priority_queue<stu,vector<stu>,cmp >q;
//priority_queue<stu>q;
for(int i=0;i<5;i++)q.push(S[i]);
while(!q.empty())
{
cout<<q.top().name<<" ";
q.pop();
}
return 0;
}
这里的cmp是按num的从小到大进行排列,然后从末尾(优先级最高)开始弹出,运行结果为。
另外还可以用lambda来定义,后面学习了lambda之后再来补充吧。。。
3. 补充说明
除了前面的sort、priority_queue,经常会用到比较函数的还有map、set等等,查看他们的比较函数说明如下:
其实可以发现,这些比较函数都是当其返回true时,就把第一个参数放在第二个参数前面,从而完成排序,基本的原理都是大同小异的,并且可以发现,默认的排序方式都是按“<”来排序,也就是说默认比较函数会将原序列排为升序。
本文标签: 函数写法sortpriorityqueue
版权声明:本文标题:sort函数、priority_queue中比较函数的写法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728896254a1178447.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论