यह कॉन्स्टिगर कैसे किया गया है?

Question

मेरे पास एक कॉन्स्ट-शुद्धता समस्या है जो मुझे हल करने में सक्षम नहीं लगती है।

class Node 
{ 
    private: 
     int   id; 
     std::set<Node*> neighbours; 
    public: 
     Node(); 
     Node(int id_p); 

     void set_id(const int& id_p); 
     int get_id() const; 
     void add_neighbour(Node* neighbour); 
     bool is_neighbour(Node* neighbour) const; 

     friend bool operator <(const Node& lhs, const Node& rhs); 
}; 

class Graph 
{ 
    private: 
     std::set<Node> node_list; 
    public: 
     Graph(); 

     void  add_node(int id); 
     const Node* get_node_by_id(int id) const; 
     bool  has_node(int id) const; 
     void  check_add_node(int id); 
     void  add_edge(int id_1, int id_2); 
     bool  has_edge(int id_1, int id_2) const; 
     void  check_add_edge(int id_1, int id_2); 

     (...) 
}; 

अब बात, अगर मैं समारोह Graph::get_node_by_id() कहते हैं, मैं किसी दिए गए नोड (प्रकार Node) के लिए सूचक वापस करना चाहते है: यहाँ मेरी कार्यक्रम की संरचना है। लेकिन ऐसा करना असंभव प्रतीत होता है, क्योंकि std::set निहित रूप से मेरे नोड प्रकार की वस्तुओं को const Node ऑब्जेक्ट्स में परिवर्तित करता है, और मैं const ऑब्जेक्ट से non-const pointer लाने में असमर्थ हूं।

हालांकि, मैं, क्योंकि मैं Graph::add_edge() से Node::add_neighbour() कॉल करना चाहते हैं const Node के लिए सब कुछ किसी और सेट (जो समस्या का समाधान होता है) नहीं हो सकता है, लेकिन जब भी मैं ऐसा करते हैं, मेरी संकलक का कहना है कि मैं const सत्ता (आवश्यक उल्लंघन कर रही है node_list सेट में तत्वों का क्रमबद्ध सेट करने के लिए), भले ही मैंने को केवल id पर ध्यान देने के लिए परिभाषित किया हो।

क्या इस दुविधा को हल करने के लिए मैं कुछ भी कर सकता हूं (सॉर्ट किए गए सेट को छोड़ दिए बिना)? आपके जवाबों के लिए शुक्रिया! त्रुटि पर

और जानकारी:

अगर मैं गैर लगातार खेतों, Graph::get_node_by_id() में त्रुटि का उपयोग करें:

for(Node& element : this->node_list) // Error: element should be const Node& 
{ 
    if(element->get_id() == id) 
    { 
     return element; 
    } 
} 
return nullptr; 

अगर मैं Graph::add_edge() में लगातार खेतों, त्रुटि का उपयोग करें:

(...) 
const Node* node_1 = this->get_node_by_id(id_1); 
const Node* node_2 = this->get_node_by_id(id_2); 
node_1->add_neighbour(node_2); // Error for disregarding constness 
node_2->add_neighbour(node_1); 

Answer 1

आपका मुद्दा यह प्रतीत होता है कि आपके पास Node पर दो अलग-अलग 'मान अर्थशास्त्र' हैं।

एक ऐसा है जो operator< द्वारा खुलासा किया गया है जो add_neighbour से प्रभावित नहीं है। चीजों को आदेश देने के लिए यह set ज़रूरत है, और यह Nodeconst बनाकर लागू करता है।

दूसरा क्लास एपीआई द्वारा खुलासा किया गया है, जहां set_id और add_neighbour दोनों मान बदल देंगे।

अपना सॉर्ट set रखने के लिए, आपको सेट में होने के बाद किसी नोड को बदलने की अनुमति नहीं देनी चाहिए। लेकिन आप पड़ोसियों को बदलने की अनुमति दे सकते हैं।

तो मैं आप neighbourssetmutable बनाने के सुझाव देंगे, add_neighbourprivate और const बनाने के लिए, और GraphNode के friend बनाते हैं।

यह mutable आपको डेटा सदस्यों को देता है जो किसी प्रकार के 'मान' का हिस्सा नहीं हैं। ध्यान दें कि इसका मतलब है कि आप इंगित कर रहे हैं कि const Node* वाले कुछ को कॉल के बीच बदलने के लिए is_neighbour के परिणाम की उम्मीद हो सकती है।

तो ...

class Node 
{ 
    private: 
     // Trust Graph not to mess directly with these! 
     int   id; 
     mutable std::set<Node*> neighbours; 

     friend class Graph; 
     // For Graph's exclusive use 
     void add_neighbour(Node* neighbour) const; 


    public: 
     Node(); 
     Node(int id_p); 

     void set_id(const int& id_p); // Callable when not in Graph's set 
     int get_id() const; 
     void add_neighbour(Node* neighbour); // Callable when not in Graph's set 
     bool is_neighbour(Node* neighbour) const; 

     friend bool operator <(const Node& lhs, const Node& rhs); 
}; 

class Graph 
{ 
    private: 
     std::set<Node> node_list; 
    public: 
     Graph(); 

     void  add_node(int id); 
     const Node* get_node_by_id(int id) const; 
     bool  has_node(int id) const; 
     void  check_add_node(int id); 
     void  add_edge(int id_1, int id_2); 
     bool  has_edge(int id_1, int id_2) const; 
     void  check_add_edge(int id_1, int id_2); 

     (...) 
}; 

अब क्या आपको लगता है कि Graph के set में नहीं हैं Node उदाहरण के लिए है सार्वजनिक, गैर स्थिरांक mutators, और Graph के लिए एक अतिरिक्त mutator है अपने set में Node के पड़ोसियों को बदलने के लिए उपयोग करने के लिए ।

तो केवल Graph

const Node b; 
b.add_neighbour(nullptr); 

कर सकते हैं क्या तुम सच में Graph पर विश्वास नहीं करते हैं, तो आप एक static add_neighbour(Node* node, Node* neighbour विधि के साथ एक आंतरिक class साथ privateconstadd_neighbour जगह ले सकता है, क्योंकि एक आंतरिक class परोक्ष करने में सक्षम है बाहरी वर्ग के निजी डेटा का उपयोग करें।

class NeighbourHelper { 
    friend class Graph; 
    static void add(const Node* node, Node* neighbour) { 
     node->add_neighbour(neighbour); 
    } 

अब केवल Graph

const Node b; 
Node::NeighbourHelper::add(&b, nullptr); 

दोनों ही मामलों में कर सकते हैं, हर किसी के लिए निम्न कार्य:

Node a; 
a.add_neighbour(nullptr); 

---

इस बिंदु पर, आप एक code- पीड़ित किया जाना चाहिए गंध ... समस्या ग्राफ में publicget_node_by_id विधि है। आप वास्तव में कच्चे Node* की बजाय किसी प्रकार के एक पुनरावर्तक का पर्दाफाश करना चाहते हैं, और Node ग्राफ़ की एक निजी आंतरिक कक्षा बनाते हैं।

या यहां तक ​​कि बस std::map<int,std::set<int>> साथ पूरे Node अवधारणा की जगह ...

लेकिन यह अपने वास्तविक उपयोग के मामले पर निर्भर करता है।

Answer 2

हालांकि टीबीबीएल का विश्लेषण सही है, लेकिन एक बहुत ही सरल समाधान है: std::map<int,Node> के साथ ग्राफ के std::set<Node> को प्रतिस्थापित करें।

आपका वर्तमान Graph::get_node_by_id() एक रैखिक खोज का उपयोग कर रहा है क्योंकि set वास्तव में इच्छित लुकअप प्रदान नहीं करता है। कुंजी बाहरी बनाना आपको operator< अधिभार को हटाने की अनुमति देता है और अभी भी एक तेज़ और अधिक प्राकृतिक लुकअप प्राप्त करता है: map.find(id)।

एकमात्र बदसूरत हिस्सा यह है कि अब आपके Node में एक आंतरिक आईडी है जो बाहरी कुंजी से मेल खाना चाहिए। यदि आप मानचित्र में नोड को देखने के अलावा आईडी का कभी भी उपयोग नहीं करते हैं, तो आप इसे पूरी तरह से हटा सकते हैं। आप ग्राफ किनारों (पड़ोसियों) का पालन करें और फिर आईडी जांच करने की जरूरत है, तो आप संकेत के अपने सेट मानचित्र iterators का एक सेट के साथ, की तरह की जगह ले सकता:

typedef std::map<int, Node> NodeMap; 
typedef std::set<NodeMap::iterator> NeighbourMap; 

फिर अपने ट्रेवर्सल pair<const int,Node> उपलब्ध है।

---

एनबी। प्रतिबिंब पर, सेट से मानचित्र में बदलना लगभग उसी भेद को टीबीबीएल के उत्तर के रूप में उत्पन्न करता है: आप नोड को कॉन्स और म्यूटेबल भागों में विभाजित करते हैं। लुकअप इस समाधान के साथ क्लीनर है (आप set::find के लिए एक नकली नोड बनाने के द्वारा लॉगरिदमिक-टाइम लुकअप प्राप्त कर सकते हैं, लेकिन यह अभी भी थोड़ा सा सुरुचिपूर्ण है), और ऑब्जेक्ट पहचान दूसरे समाधान के साथ थोड़ा साफ है।