एसटीएल प्राथमिकता कतार और पॉइंटर्स

Question

के साथ ओवरलोडिंग यह प्राथमिकता कतार का उपयोग करने वाला मेरा पहला समय है। मैं स्कूल के लिए डिजस्ट्रा के एल्गोरिदम को लागू करने की कोशिश कर रहा हूं और मुझे लगा कि मुझे ऐसा करने के लिए एक न्यूनतम ढेर की आवश्यकता है। अभी मेरे नोड्स पॉइंटर्स हैं और मैं उनके वजन की तुलना करना चाहता हूं, लेकिन मुझे नहीं लगता कि मैं ओवरलोड कर सकता हूं> और < पॉइंटर्स के साथ? क्या ऐसा कोई तरीका है जिसे मैं पूरा कर सकता हूं?

कोड इतनी दूर:

priority_queue<Node*, vector<Node*>, node_comparison> minHeap; 

और फिर मैं नोड के वजन

struct node_comparison 
{ 
    bool operator<(const Node* a, const Node* b) const 
    { 
    return a->totalWeight < b->totalWeight; 
    } 
}; 

तुलना करने के लिए एक struct है लेकिन यह कहना है कि यह ऑपरेटर समारोह के लिए भी कई मापदंडों देखते हैं। मैं यह पता लगाने की कोशिश कर रहा हूं कि मैं थोड़ी देर के लिए अपने नोड्स के साथ एक न्यूनतम ढेर प्राथमिकता कतार कैसे प्रबंधित कर सकता हूं और अटक रहा हूं। कोई विचार?

Answer 1

अगर मैं आपके सवाल का सही ढंग से समझ, मेरा मानना ​​है कि क्या आप वास्तव में चाहते हैं बनाने के लिए है node_comparison एक functor (खासतौर पर, एक द्विआधारी विधेय):

struct node_comparison 
{ 
    bool operator() (const Node* a, const Node* b) const 
    { 
     return a->totalWeight < b->totalWeight; 
    } 
}; 

एक functor एक वर्ग जिसका वस्तुओं एक प्रदान करना है कॉल ऑपरेटर (operator()) और इसलिए, एक ही वाक्य रचना आप एक समारोह लागू करने के लिए प्रयोग करेंगे के साथ लागू किया जा सकता है की अधिभार:

Node* p1 = ...; 
Node* p2 = ...; 
node_comparison comp; 
bool res = comp(p1, p2) // <== Invokes your overload of operator() 

आंतरिक रूप से, std::priority_queue उपरोक्त कोड स्निपेट में आपके अनुमान को कम या कम करेगा, और इसके तत्वों के बीच तुलना करने के लिए इसे इस तरह से आमंत्रित करेगा।

---

नियमित कार्यों पर functors का लाभ यह है कि वे राज्य जानकारी पकड़ सकता है (कुछ आप शायद पल के लिए की जरूरत नहीं होगी, लेकिन जो अक्सर पता चला है वांछनीय होने के लिए):

#include <cmath> 

struct my_comparator 
{ 
    my_comparator(int x) : _x(x) { } 

    bool operator() (int n, int m) const 
    { 
     return abs(n - _x) < abs(m - _x); 
    } 

    int _x; 
}; 

उपर्युक्त अनुमान, उदाहरण के लिए, निर्माण समय पर प्रदान किए गए किसी अन्य पूर्णांक से कितने दूर हैं, इस पर आधारित पूर्णांक की तुलना करता है। यह है कि यह कैसे इस्तेमाल किया जा सकता है:

#include <queue> 
#include <iostream> 

void foo(int pivot) 
{ 
    my_comparator mc(pivot); 
    std::priority_queue<int, std::deque<int>, my_comparator> pq(mc); 

    pq.push(9); 
    pq.push(2); 
    pq.push(17); 

    while (!pq.empty()) 
    { 
     std::cout << pq.top(); 
     pq.pop(); 
    } 
} 

int main() 
{ 
    foo(7); 

    std::cout << std::endl; 

    foo(10); 
} 

Answer 2

आप अपने तुलना functor bool operator()(....), नहीं bool operator<(....) लागू करने के लिए की आवश्यकता होगी:

struct node_comparison 
{ 
    bool operator()(const Node* a, const Node* b) const 
    { 
    return a->totalWeight < b->totalWeight; 
    } 
};