V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
russian
V2EX  ›  问与答

C++的指针的 const &导致了优先队列函数调用出现了错误,不理解

  •  
  •   russian · 2022-10-25 02:38:59 +08:00 · 1016 次点击
    这是一个创建于 520 天前的主题,其中的信息可能已经有所发展或是发生改变。

    求问以下的代码,为什么"auto& node = q.top()" 这一行,在第二次循环的时候会得到旧的 top ,而不是新的?因为这个,我的代码出现了死循环。旧的 top 不是已经被 pop 掉了么?

    百思不得其解,我试了把容器换成 vector ,就正常了,或者可以把 “auto&” 的 "&" 去掉。 看了下 debugger ,如果不改代码,node 的类型是 Node * const &。 如果去掉&,类型就是 Node * ,那没问题,如果容器是 vector ,类型就是 Node * &,也是没问题的。

    可是我还是没法把 Node* const &和第二轮 loop 依然得到旧的 top 值联系在一起。怎么回事?

    #include <queue>
    
    struct Node {
        int val;
        Node* next = nullptr;
        Node(int x) : val(x){}	
    };
    
    int main()
    {
     Node* n1 = new Node(1);
     Node* n2 = new Node(2);
    
    std::priority_queue<Node*> q;
    q.push(n1);
    q.push(n2);
    
    Node* head = new Node(-1);
    auto cur = head;
    
    while (!q.empty()) 
    {
        auto& node = q.top();
        q.pop();
        cur->next = node;
    
        if (node->next)  q.push(node->next);
    
        cur = cur->next;
    }
    }
    
    8 条回复    2022-10-25 08:44:24 +08:00
    Andiry
        1
    Andiry  
       2022-10-25 03:27:29 +08:00   ❤️ 1
    因为你的 node 绑定到了 top 返回的 const reference 上,pop 之后你的 node 也一起更新了
    在 pop 前后各打印一次 node 就知道了
    GeruzoniAnsasu
        2
    GeruzoniAnsasu  
       2022-10-25 03:50:32 +08:00
    …… 我没看懂

    node 弹出来之后又塞回去了,priority_queue::push 的时候就会重新排序,所以原来的头塞回去了还是头有啥问题吗

    原本是想写啥
    geelaw
        3
    geelaw  
       2022-10-25 04:06:54 +08:00 via iPhone   ❤️ 1
    这段代码含有未定义行为。

    top 得到的引用在修改容器之后不再有效,pop 修改容器,因此 cur->next = node 触发未定义行为。

    具体实现来说,priority_queue 可能的实现里,经过 pop 之后,你先前得到的 node 或许仍然引用有意义的位置,但那个位置等同于新的 top ,因此读取它可能会得到新的最大元。
    russian
        4
    russian  
    OP
       2022-10-25 04:13:17 +08:00
    @Andiry 确实!刚才看 debugger 的时候没注意,确实是 node 和 top 绑定以后,pop 了,node 也变成了新的 top 。谢谢!
    russian
        5
    russian  
    OP
       2022-10-25 04:14:12 +08:00
    @GeruzoniAnsasu 原本是 sort k list node 的代码。在你没有 next 的情况下不会塞回去
    russian
        6
    russian  
    OP
       2022-10-25 04:17:15 +08:00
    @geelaw 确实,以前只注意到了迭代器在修改以后就失效了,没注意 top 这种引用的。
    那就是如果使用 top 就只可以通过拷贝?如果之后也做 pop 。
    iceheart
        7
    iceheart  
       2022-10-25 08:01:01 +08:00 via Android
    pop 是删除顶部元素,你删除之后还引用原来的元素地址,就是引用未定义内存,可算野指针了。
    解决也简单,就是在 pop(失效)之前对 next 赋值
    lovelylain
        8
    lovelylain  
       2022-10-25 08:44:24 +08:00 via Android
    @iceheart 不是把&去掉最简单吗,本来就是指针,直接复制指针就行,
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3489 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 11:08 · PVG 19:08 · LAX 04:08 · JFK 07:08
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.