सी ++ वस्तुओं को खोजने और संशोधित करने के लिए प्राथमिकता कतार

Question

मैं ए * एल्गोरिदम लागू करने की कोशिश कर रहा हूं और मुझे प्राथमिकता कतार की आवश्यकता है, लेकिन std::priority_queue मेरे लिए काम नहीं करता है क्योंकि मुझे यह पता लगाने की आवश्यकता है कि कोई तत्व (Node ऑब्जेक्ट) priority_queue में है या नहीं, इसके डेटा तक पहुंचने के लिए और यदि आवश्यक हो तो इसे संशोधित करने के लिए।

क्या मैं इसे std::priority_queue किसी भी तरह से उपयोग कर सकता हूं?

मैं कोड सुझावों की सराहना करता हूं क्योंकि मुझे std::priority_queue के साथ अधिक अनुभव नहीं है।

Answer 1

"लेकिन एसटीएल :: priority_queue मेरे लिए काम नहीं करता है, क्योंकि मैं खोजने के लिए कि क्या एक तत्व (एक नोड वस्तु) या priority_queue में है नहीं, अपने डेटा का उपयोग करने और अगर यह संशोधित करने की आवश्यकता ज़रूरी।"

आप अच्छी तरह से एक उपयुक्त Compare वर्ग पैरामीटर प्रदान वर्ग के किसी भी प्रकार के लिए ऐसा कर सकते हैं।

std::priority_queue<T> को की अवधारणा का अनुपालन करने के लिए अंतर्निहित Container की आवश्यकता है।

template< 
    class T, 
    class Container = std::vector<T>, 
    class Compare = std::less<typename Container::value_type> 
> class priority_queue; 

आप std::priority_queue<T>::front() संदर्भ का पता लग सकता है, और कतार के माध्यम से पुनरावृति, कुछ मामलों को खोजने के लिए।

---

तुम सच में वस्तुओं के विशिष्ट विद्यमान उदाहरणों, कि कुछ प्राथमिकता एल्गोरिथ्म द्वारा अतिरिक्त प्रबंधित किया जाना चाहिए की आवश्यकता है, तो यह एक अच्छा विचार स्मार्ट संकेत स्टोर करने के लिए हो सकता है (उदाहरण के लिए std::shared_ptr<T>), बल्कि मूल्यों या कच्चे संकेत से । Compare कक्षा को निश्चित रूप से उचित रूप से अनुकूलित करने की आवश्यकता है।

---

struct CompareNodes { 
    bool operator 
     (const std::shared_ptr<Node>& lhs 
     , const std::shared_ptr<Node>& rhs 
     ) { 
     // Provide some operation to compare lhs < rhs (less) results in true 
     // This function is meant to determine the actual priority of your Node 
     // instances, when referenced in the priority_queue<> in question. 
    } 
}; 

std::priority_queue 
    < std::shared_ptr<Node> 
    , std::vector<std::shared_ptr<Node>> 
    , CompareNodes 
    > myQueue; 

---

"अपने डेटा का उपयोग करने और यदि आवश्यक हो यह संशोधित करने के लिए।"

std::shared_ptr साथ प्राथमिकता कतार के रूप में ऊपर नमूने में बताया गया हो सकता है का उपयोग करना भी भी से आप जारी कतार में उदाहरणों खोजने की जरूरत है, और मूल उदाहरण से डेटा संशोधनों सिंक्रनाइज़।