关于运算符重载

P4779 【模板】单源最短路径(标准版)

Ayaka_T @ 2022-04-07 14:14:34

Rt,dij这样重载是可以通过的:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct node{
    int to,v;
    bool operator < (const node &x)const
    {
        return x.v<v;
    }
};
vector<node>d[maxn];
priority_queue<node>q;
int n,m,s,u,v,to,ans[maxn];
bool vis[maxn];
void dij(){
    memset(ans,0x3f,sizeof ans);
    ans[s]=0;
    q.push({s,0});
    while(!q.empty()){
        node now=q.top();
        q.pop();
        if(vis[now.to])continue;
        vis[now.to]=true;
        for(int i=0;i<d[now.to].size();i++){
            node next=d[now.to][i];
            if(ans[next.to]>ans[now.to]+next.v){
                ans[next.to]=ans[now.to]+next.v;
                q.push({next.to,ans[next.to]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&to);
        d[u].push_back({v,to});
    }
    dij();
    return 0;
}

而将重载的部分改为这样:

friend const bool operator <(node x,node y){
    return x.v<y.v;
}

就无法通过

改成这样就可以通过:

friend bool operator<(node x,node y){
    if(x.v<y.v)
        return false;
    else 
        return true;
}

或这样也可以

friend bool operator<(node x,node y)
{
    return x.v>y.v;
}

问题:

1,为什么定义大根堆要重载小于号

2,为什么用友元重载时,函数内就要反着过来

望解答,谢谢!


by Mzk2333 @ 2022-04-07 14:17:06

第一个模板下会先判断<,条件就反了,即当x.v<y.v 时才会返回真,与你第二个AC代码完全不一样。


by 蒟酱 @ 2022-04-07 14:21:13

@tanjianlang 你那个不写友元的也是反的……仔细想想为什么
c++ STL 里面都是重载小于号,然后 STL 的优先队列默认是大根堆而不是小根堆,所以只能反着重载运算符


by Terrible @ 2022-04-07 15:17:47

并非都需要友元函数的形式,常函数、体外定义都可以。


by Ayaka_T @ 2022-04-07 17:28:08

@蒟酱 所以第一个模板是可以理解为这样吗?

bool operator < (const node &x)const
{
    return v>x.v;
}

另外,为什么我改为小根堆后重载小于号就会报错,要重载大于号才行,想问这是为什么


by 蒟酱 @ 2022-04-07 18:56:00

@tanjianlang
1.确实
2.STL 里面都是重载小于号的


by Ayaka_T @ 2022-04-08 13:59:44

@蒟酱 明白了,万分感谢


|