为何std::priority_queue.top()会修改返回对象的成员值？

背景 #

我在为《高峰时刻》（Rush Hour）游戏编写A算法学习基础原理，实现了一个Board类，实例同时作为A的搜索节点。通过generate_moves()生成可行走法，创建新的Board实例作为子节点，添加到原节点的std::priority_queue（名为children）中。但调用std::priority_queue的top()获取Board实例时，预先赋值的父节点指针（Board* parent）会变成指向自身。

核心代码片段 #

简化后的generate_moves()函数：

"for each possible move do"
...
Board newBoard = Board();
...
newBoard.parent = this; // this指向调用函数的当前对象
children.push(newBoard); // 加入当前Board的优先队列
...

调试现象 #

在a_star()函数（以调用它的Board为根节点）中，根节点扩展第一个子节点后的调试情况：

• 调用top()前：open优先队列中所有子节点的父指针都指向根节点，根节点父指针为nullptr，符合预期。
• 优先队列自定义比较类Compare执行时：从第一次比较开始，所有子节点的父指针变为指向自身，而非根节点。
• 调用top()后（取出的currNode）：取出的节点父指针自引用。
• 调用top()后（open队列内部）：队列内所有Board实例的父指针都出现自引用问题。

尝试过的无效方案 #

• 替换priority_queue为自定义类型，仍需处理const要求，结果一致
• 将父节点指针作为构造函数参数传入
• 直接操作原open队列而非复制（曾怀疑复制环节出问题）
• 将Compare函数参数从引用类型(Board&)改为值类型(Board)

最小可复现代码 #

#pragma once
#include <iostream>
#include <bitset>
#include <vector>
#include <queue>
#include <stdexcept>

using namespace std;

class SimplifiedBoard {
public:
    bitset<36> board;
    class Compare {
    public:
        bool operator() (SimplifiedBoard& a, SimplifiedBoard& b) {
            return (a.fscore < b.fscore);
        }
    };
    int fscore;
    priority_queue<SimplifiedBoard, vector<SimplifiedBoard>, Compare> children;
    SimplifiedBoard* parent;

    SimplifiedBoard() {
        fscore = 0;
        parent = nullptr;
    }

    // 生成子节点
    void generateMoves() {
        int arbitraryChildren = 5;
        for (int i = 0; i < arbitraryChildren; i++) {
            SimplifiedBoard newBoard = SimplifiedBoard();
            newBoard.fscore = (int)rand() / 100;
            // 给子节点设置父指针
            newBoard.parent = this;
            // 添加到子节点队列
            children.push(newBoard);
        }
    }

    // A*算法实现
    vector<SimplifiedBoard> aStar(SimplifiedBoard& start) {
        priority_queue<SimplifiedBoard, vector<SimplifiedBoard>, Compare> open = {};
        vector<SimplifiedBoard> closed = {};
        start.fscore = 0;
        start.parent = nullptr;
        open.push(start);

        // 主循环
        while (!open.empty()) {
            // ***BUG 出现位置：第二个循环，根节点被扩展并加入closed后****
            SimplifiedBoard currNode = open.top(); open.pop();
            if (currNode.parent != nullptr &&
                currNode.parent->parent != nullptr &&
                currNode.parent == currNode.parent->parent) {
                cout << "Self-referential bug!" << endl;
            }
            // ***第二个循环时，currNode.parent突然指向一个自引用的节点***
            
            // 生成子节点，f/g/h分数和parent在函数内赋值
            currNode.generateMoves();

            // 遍历子节点，检查是否加入open队列
            auto childrenCopy = currNode.children;
            for (int i = 0; i < (int)currNode.children.size(); i++) {
                bool isWorse = false;
                SimplifiedBoard currChildNode = childrenCopy.top(); childrenCopy.pop();

                // 是否达到目标状态
                if (currChildNode.isVictory()) {
                    closed.push_back(currChildNode);
                    // 路径回溯
                    vector<SimplifiedBoard> path = {};
                    SimplifiedBoard currPathNode = currChildNode;
                    // 从子节点回溯到父节点
                    while (currPathNode.parent != nullptr) {
                        path.push_back(currPathNode);
                        currPathNode = *currPathNode.parent;
                    }
                    // 添加根节点
                    path.push_back(currPathNode);
                    // 返回路径
                    return path;
                }
                // 检查open队列
                auto openCopy = open;
                for (int j = 0; j < (int)open.size(); j++) {
                    SimplifiedBoard currOpenNode = openCopy.top(); openCopy.pop();
                    if (currChildNode.fscore <= currOpenNode.fscore) {
                        isWorse = true; break;
                    }
                }
                if (isWorse) { continue; }

                // 检查closed队列
                for (int j = 0; j < (int)closed.size(); j++) {
                    if (currChildNode.fscore <= closed[j].fscore) {
                        isWorse = true; break;
                    }
                }
                if (isWorse) { continue; }

                // 加入open队列
                open.push(currChildNode);
            }
            // 将当前节点加入closed队列
            closed.push_back(currNode);
        }
        // 找不到路径时返回空
        return vector<SimplifiedBoard>();
    }

    // 判断是否达到胜利条件
    bool isVictory() {
        if ((int)rand() % 50 == 5) { return true; }
        else { return false; }
    }
};

int main() {
    // 调试示例
    srand((int)time(NULL));
    SimplifiedBoard b = SimplifiedBoard();
    cout << "如果程序卡住说明BUG出现了:" << endl;
    vector<SimplifiedBoard> res = b.aStar(b);
    for (int i = 0; i < (int)res.size(); i++) {
        cout << res[i].fscore << endl;
    }
}

内容的提问来源于stack exchange，提问作者Gabriel Balassa Turu