求问以下的代码,为什么"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 天前 ![]() 因为你的 node 绑定到了 top 返回的 const reference 上,pop 之后你的 node 也一起更新了
在 pop 前后各打印一次 node 就知道了 |
2
GeruzoniAnsasu 147 天前
…… 我没看懂
node 弹出来之后又塞回去了,priority_queue::push 的时候就会重新排序,所以原来的头塞回去了还是头有啥问题吗 原本是想写啥 |
![]() |
3
geelaw 147 天前 via iPhone ![]() 这段代码含有未定义行为。
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 赋值 |