lundi 24 octobre 2022

Why does top of priority queue returns the wrong reference? If I remove the reference symbol from "auto& node" then it works as expected?

With the following code, it runs in a infinite loop, because in the second loop, the priority queue's top function still returns the old top, rather than the new top. I have to access the correct top by removing the reference symbol. How does it happen?

My compiling environment is Visual studio 2022.

#include <iostream>
#include <queue>

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    
};

using namespace std;


int main()
{
    ListNode* n1 = new ListNode(1);
    ListNode* n4 = new ListNode(4);
    vector<ListNode*> lists{ n1
        , n4 
    };

    priority_queue<ListNode*> q;
    for (auto n : lists) {
        q.push(n);
    }
    ListNode* pre = new ListNode(-1);
    auto tmp = pre;

    while (not q.empty()) {
       // will execute correctly if remove &
        auto& node = q.top();
        q.pop();
        tmp->next = node;

        if (node->next) {
            q.push(node->next);
        }

        tmp = tmp->next;
    }
    
}

Aucun commentaire:

Enregistrer un commentaire