c++ - 排队循环中的节点自引用

Question

我正在实现霍夫曼编码器。哈夫曼树是使用优先级队列自下而上构建的。我有一个简单的节点类，带有指向另外两个节点的指针。 构建树的循环是:

while(q.size() > 1)
{
    huffnode n1 = q.top();
    q.pop();
    huffnode n2 = q.top();
    q.pop();

    q.push(huffnode((char)0, n1.freq+n2.freq, &n1, &n2));
}

循环终止时剩余的节点是树根。

这段代码看起来很无辜，但在我的测试输入中，它给出了一棵树，其中根的右 child 指向它自己和根的左 child ，而不是刚刚从队列中弹出的两个节点。我已确认队列已正确排序。

我认为正在发生的事情是 n1 和 n2 是始终具有相同地址的局部变量，如在调试器中所见。推送新节点时，它指向这些地址。当该节点稍后弹出时，它的拷贝被放入这些地址之一，它已经指向其中一个地址，因此它最终指向自己。

我应该如何解决这个问题？我不能创建 n1 和 n2 指针，因为它们必须是 const 因为 top() 返回一个 const 引用，并且将 top() 的结果分配给一个 const 引用或 const 指针使得队列不可变。

Answer 1

当您使用花括号 {} 时，您处于一个新的范围内。在该范围内声明的变量是该范围的本地变量，并且仅在该范围内有效。当作用域结束时，对于您来说，循环就是每次循环迭代时，作用域消失，并且该作用域中的变量被破坏并且不再存在。

当您尝试取消引用该指针时，保存指向超出范围的变量的指针将导致未定义的行为。