c++ - 如何在 std::unordered_map 中维护 std::队列而不丢失对队列所做的更改？

Question

我正在尝试为有根树构建一个欧拉路径，其中根可以有多个 child (即它不是二叉树)。为了跟踪每个已经遍历的 child ，我在 map 中维护了一个队列。当我遇到一个根时，我只需弹出它的一个子节点并将其设置为根。问题是，每当我弹出一个子节点并再次遍历其父节点时，弹出的节点再次出现。我猜我需要存储队列的引用，但无法理解它。任何帮助，将不胜感激。

vector<int> getEulerPath(Node* root) {

    Node* node = root;
    vector<int> path;
    unordered_map<int, queue<Node*>> uvc;

    while(node != NULL) {
        path.push_back(node->data);
        cout << "processing node " << node->data << endl;
        if(uvc.find(node->data) != uvc.end()) {
            cout << "found queue: " << node->data << endl;
            uv = uvc.find(node->data)->second;
        } else {
            for(int i = 0; i < node->children.size(); i++) {
                uv.push(node->children[i]);
            }
            cout << "adding queue: " << node->data << endl;
            uvc.insert(pair<int, queue<Node*>>{node->data, uv});
        }

        if(!uv.empty()) {
            cout << "queue size before popping: " << uv.size() << endl;
            cout << "have some children left for : " << node->data << endl;
            node = uv.front();
            uv.pop();
            cout << "queue size after popping: " << uv.size() << endl;
        } else {
            cout << "no children left reverting back to : " << node->parent->data << endl; 
            node = node->parent;
        }

        cout << "new node is: " << node->data << endl;
    }

    return path;
}

更新

以下是最小的可运行示例

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

class Node {
public:
    vector<Node*> children;
    Node* parent;
    int data;
    Node();
    Node(int, Node*);
};

Node::Node() {
    parent = NULL;
    data = -1;
}

Node::Node(int d, Node* p) {
    parent = p;
    data = d;
}

Node* generateTree(vector<vector<int>> edges) {
    unordered_map<int, Node*> nodes;
    Node* root = new Node();
    for(int i = 0; i < edges.size(); i++) {
        vector<int> edge = edges[i];
        Node* parent;
        Node* child;
        if(nodes.find(edge[0]) == nodes.end()) {
            parent = new Node(edge[0], NULL);
            nodes.insert(pair<int, Node*>{edge[0], parent});
        } else {
            parent = nodes.find(edge[0])->second;
        }
        if(nodes.find(edge[1]) == nodes.end()) {
            child = new Node(edge[1], parent);
            nodes.insert(pair<int, Node*>{edge[0], child});
        } else {
            child = nodes.find(edge[1])->second;
        }
        if(i == 0) root = parent;
        parent->children.push_back(child);
    }
    return root;
}

vector<int> getEulerPath(Node* root) {

    Node* node = root;
    vector<int> path;
    unordered_map<int, queue<Node*>> uvc;

    while(node != NULL) {
        path.push_back(node->data);
        cout << "processing node " << node->data << endl;
        queue<Node*> uv;
        if(uvc.find(node->data) != uvc.end()) {
            cout << "found queue: " << node->data << endl;
            uv = uvc.find(node->data)->second;
        } else {
            for(int i = 0; i < node->children.size(); i++) {
                uv.push(node->children[i]);
            }
            cout << "adding queue: " << node->data << endl;
            uvc.insert(pair<int, queue<Node*>>{node->data, uv});
        }

        if(!uv.empty()) {
            cout << "queue size before popping: " << uv.size() << endl;
            cout << "have some children left for : " << node->data << endl;
            node = uv.front();
            uv.pop();
            cout << "queue size after popping: " << uv.size() << endl;
        } else {
            cout << "no children left reverting back to : " << node->parent->data << endl; 
            node = node->parent;
        }

        cout << "new node is: " << node->data << endl;
    }

    return path;
}

int main() {
    vector<vector<int>> edges;
    edges.push_back(vector<int> {1, 2});
    edges.push_back(vector<int> {1, 3});
    edges.push_back(vector<int> {1, 4});
    edges.push_back(vector<int> {3, 5});
    edges.push_back(vector<int> {3, 6});
    edges.push_back(vector<int> {3, 7});
    Node* root = generateTree(edges);
    vector<int> euler_path = getEulerPath(root);
    for(int i = 0; i < euler_path.size(); i++) {
        cout << euler_path[i] << " ";
    }
    cout << endl;
    return 0;
}

Answer 1

您正在使用 uv = uvc.find(node->data)->second 复制 map 中的数据。表达。然后你修改那个拷贝。 map 中的数据永远不会改变。同样，当您将节点插入 map 时，您仍在修改拷贝。
您需要使用指向存储在 uvc 中的队列的指针。 .这些方面的东西:

queue<Node*> *uvc;
auto fit = uvc.find(node->data);
if(fit != uvc.end()) {
    cout << "found queue: " << node->data << endl;
    uv = &fit->second;
} else {
    cout << "adding queue: " << node->data << endl;
    uv = &uvc[node->data];
    for(int i = 0; i < node->children.size(); i++) {
        uv->push(node->children[i]);
    }
}

通过保存 find 返回的迭代器，您可以避免重复查找它。而且，因为 [] unordered_map 上的运算符如果键不存在，将插入一个键/值对，您可以快速添加一个新节点并获取指向它的指针(或引用)。
对 uv. 的其他引用在下面的代码中需要更新为 uv-> .