priority_queue指向彼此

Question

我有一個類Node，除了存儲數據，有一個指針指向其父Node對象。我在priority_queue中存儲了一些節點，並將<運營商作爲比較。

class Node { 
public: 
    string name; 
    Node *parent; 
    int cost; 
}; 

static bool operator<(const Node& lhs, const Node& rhs) { 
    return lhs.cost < rhs.cost; 
} 

priority_queue<Node> queue; 

的問題是，父指針似乎搞砸了。我的猜測是，當我從隊列彈出一個Node，該Nodes實際上是在內存中向上移動，並使指針指向錯誤Nodes。這可能嗎？

我試着用指針的priority_queue代替Node*（並用new創建它們），這樣只有指針被重新排序，而不是對象本身。這似乎解決了指針問題，但現在隊列按內存地址排序，而不是Nodes的成本。

我怎樣才能實現一個priority_queue具有指向對方的對象？

Answer 1

使用Node*併爲您的隊列中的自定義比較。用你現在有的東西，你可以做以下事情，不過我建議你使用智能指針，如果它們在當前的工具鏈中可用的話。

class Node { 
public: 
    string name; 
    Node *parent; 
    int cost; 
}; 

class CompareNodePtr 
{ 
public: 
    bool operator()(const Node*& left, const Node*& right) const 
    { 
     return left->cost < right->cost; 
    } 
}; 

// your priority queue with custom comparator. 
std::priority_queue<Node*, std::vector<Node*>, CompareNodePtr> myqueue; 

另外，對於比較更局部defintiion，你可以在Node東西比較，我的指針類，以免污染全局命名空間：

class Node { 
public: 
    string name; 
    Node *parent; 
    int cost; 

    struct ComparePtr 
    { 
     bool operator()(const Node*& left, const Node*& right) const 
     { 
      return left->cost < right->cost; 
     } 
    }; 
}; 

// your priority queue with custom comparator. 
std::priority_queue<Node*, std::vector<Node*>, Node::ComparePtr> myqueue; 

關於指針是使用對象級存儲（與上面的指針存儲相對）「優化」，優先級隊列可以/將在每次重新彈出消息後重新消隱內容時移動元素（如果您不知道，標準lib默認使用堆結構作爲優先級隊列）。

最後，我留下了如何處理某些節點的父指針在其子節點之前被彈出的概念，並將其刪除，從而爲隊列中留下的任何子節點創建一個無效指針你，但它聽起來像你知道會發生。