这是一个创建于 147 天前的主题，其中的信息可能已经有所发展或是发生改变。
求问以下的代码，为什么"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;
}
}
 |
1
Andiry 147 天前  1
因为你的 node 绑定到了 top 返回的 const reference 上，pop 之后你的 node 也一起更新了
在 pop 前后各打印一次 node 就知道了 |
 |
2
GeruzoniAnsasu 147 天前
…… 我没看懂
node 弹出来之后又塞回去了，priority_queue::push 的时候就会重新排序，所以原来的头塞回去了还是头有啥问题吗 原本是想写啥 |
 |
3
geelaw 147 天前 via iPhone 1
这段代码含有未定义行为。
top 得到的引用在修改容器之后不再有效，pop 修改容器，因此 cur->next = node 触发未定义行为。 具体实现来说，priority_queue 可能的实现里，经过 pop 之后，你先前得到的 node 或许仍然引用有意义的位置，但那个位置等同于新的 top ，因此读取它可能会得到新的最大元。 |
 |
5
russian OP @GeruzoniAnsasu 原本是 sort k list node 的代码。在你没有 next 的情况下不会塞回去
|
 |
7
iceheart 147 天前 via Android
pop 是删除顶部元素，你删除之后还引用原来的元素地址，就是引用未定义内存，可算野指针了。
解决也简单，就是在 pop(失效)之前对 next 赋值 |
Select Language