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

[russian]

求问以下的代码，为什么"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;
}
}

[Andiry]

因为你的 node 绑定到了 top 返回的 const reference 上，pop 之后你的 node 也一起更新了
在 pop 前后各打印一次 node 就知道了

[GeruzoniAnsasu]

…… 我没看懂

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

原本是想写啥

[geelaw]

这段代码含有未定义行为。

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

具体实现来说，priority_queue 可能的实现里，经过 pop 之后，你先前得到的 node 或许仍然引用有意义的位置，但那个位置等同于新的 top ，因此读取它可能会得到新的最大元。

[russian]

@Andiry 确实！刚才看 debugger 的时候没注意，确实是 node 和 top 绑定以后，pop 了，node 也变成了新的 top 。谢谢！

[russian]

@GeruzoniAnsasu 原本是 sort k list node 的代码。在你没有 next 的情况下不会塞回去

[russian]

@geelaw 确实，以前只注意到了迭代器在修改以后就失效了，没注意 top 这种引用的。
那就是如果使用 top 就只可以通过拷贝？如果之后也做 pop 。

[iceheart]

pop 是删除顶部元素，你删除之后还引用原来的元素地址，就是引用未定义内存，可算野指针了。
解决也简单，就是在 pop(失效)之前对 next 赋值

[lovelylain]

@iceheart 不是把&去掉最简单吗，本来就是指针，直接复制指针就行，