c++ - सी++ एसटीएल क्यों "पेड़" कंटेनर प्रदान नहीं करता है?




stl tree (9)

सी ++ एसटीएल क्यों "पेड़" कंटेनर प्रदान नहीं करता है, और इसके बजाय उपयोग करने के लिए सबसे अच्छी चीज क्या है?

मैं एक वृक्ष के रूप में एक पेड़ के रूप में वस्तुओं के पदानुक्रम को एक प्रदर्शन वृद्धि के रूप में उपयोग करना चाहता हूं ...


"मैं वस्तुओं के पदानुक्रम को एक पेड़ के रूप में स्टोर करना चाहता हूं"

सी ++ 11 आ गया है और चला गया है और उन्हें अभी भी std::tree प्रदान करने की आवश्यकता नहीं दिखाई दे रही है, हालांकि विचार आया है ( here देखें)। हो सकता है कि उन्होंने यह नहीं जोड़ा है कि मौजूदा कंटेनर के शीर्ष पर अपना खुद का निर्माण करना मुश्किल है। उदाहरण के लिए...

template< typename T >
struct tree_node
   {
   T t;
   std::vector<tree_node> children;
   };

एक सरल ट्रैवर्सल रिकर्सन का उपयोग करेगा ...

template< typename T >
void tree_node<T>::walk_depth_first() const
   {
   cout<<t;
   for ( auto & n: children ) n.walk_depth_first();
   }

यदि आप पदानुक्रम बनाए रखना चाहते हैं और आप इसे एसटीएल एल्गोरिदम के साथ काम करना चाहते हैं, तो चीजें जटिल हो सकती हैं। आप अपने खुद के इटरेटर बना सकते हैं और कुछ संगतता प्राप्त कर सकते हैं, हालांकि कई एल्गोरिदम केवल पदानुक्रम के लिए कोई समझ नहीं लेते हैं (उदाहरण के लिए, किसी श्रेणी के क्रम को बदलते हैं)। पदानुक्रम के भीतर एक सीमा को परिभाषित करना भी एक गन्दा व्यवसाय हो सकता है।


std :: नक्शा लाल काले पेड़ पर आधारित है। आप अपने स्वयं के पेड़ों को लागू करने में मदद के लिए अन्य containers का भी उपयोग कर सकते हैं।


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

आम तौर पर, यदि कोई मूल लाइब्रेरी कार्यक्षमता है जो आप चाहते हैं, तो यह एसएलएल में नहीं है, तो फिक्स को देखना ठीक है।

अन्यथा, आपके पेड़ की जरूरतों के आधार पर there libraries का एक bunch है।


एसटीएल का दर्शन यह है कि आप गारंटी के आधार पर एक कंटेनर चुनते हैं और इस पर आधारित नहीं है कि कंटेनर कैसे कार्यान्वित किया जाता है। उदाहरण के लिए, कंटेनर की आपकी पसंद तेजी से लुकअप की आवश्यकता पर आधारित हो सकती है। आपकी सभी देखभाल के लिए, कंटेनर को एक यूनिडायरेक्शनल सूची के रूप में कार्यान्वित किया जा सकता है - जब तक कि खोज बहुत तेज हो, आप खुश होंगे। ऐसा इसलिए है क्योंकि आप किसी भी तरह आंतरिक को स्पर्श नहीं कर रहे हैं, आप एक्सेसरेटर या एक्सेस फ़ंक्शंस का उपयोग कर रहे हैं। आपका कोड इस बात से बंधे नहीं है कि कंटेनर कैसे कार्यान्वित किया गया है लेकिन यह कितना तेज़ है, या क्या यह एक निश्चित और परिभाषित क्रम है, या यह अंतरिक्ष पर कुशल है या नहीं।


पेड़ का उपयोग करने के दो कारण हैं:

आप पेड़ की तरह संरचना का उपयोग कर समस्या को दर्पण करना चाहते हैं:
इसके लिए हमने ग्राफ लाइब्रेरी को बढ़ावा दिया है

या आप एक कंटेनर चाहते हैं जिसमें पेड़ है विशेषताओं की तरह पेड़ है इसके लिए हमारे पास है

असल में इन दो कंटेनरों की विशेषताओं ऐसी है कि वे पेड़ों का उपयोग करके व्यावहारिक रूप से लागू किए जाने चाहिए (हालांकि यह वास्तव में एक आवश्यकता नहीं है)।

यह प्रश्न भी देखें: सी पेड़ कार्यान्वयन


मुझे लगता है कि कई कारण हैं कि कोई स्टेल पेड़ क्यों नहीं हैं। मुख्य रूप से पेड़ रिकर्सिव डेटा संरचना का एक रूप है जो एक कंटेनर (सूची, वेक्टर, सेट) की तरह, बहुत अलग अच्छी संरचना है जो सही विकल्पों को मुश्किल बनाता है। एसटीएल का उपयोग करके बुनियादी रूप में निर्माण करना भी बहुत आसान है।

एक सीमित जड़ वाले पेड़ को एक कंटेनर के रूप में सोचा जा सकता है जिसमें एक मूल्य या पेलोड होता है, कक्षा ए का एक उदाहरण और रूट (उप) पेड़ों का संभवतः खाली संग्रह; वृक्षों के खाली पेड़ पत्तियों के रूप में हैं।

template<class A>
struct unordered_tree : std::set<unordered_tree>, A
{};

template<class A>
struct b_tree : std::vector<b_tree>, A
{};

template<class A>
struct planar_tree : std::list<planar_tree>, A
{};

किसी को इटेटरेटर डिज़ाइन इत्यादि के बारे में थोड़ा सोचना पड़ता है और कौन सा उत्पाद और सह-उत्पाद संचालन पेड़ों के बीच परिभाषित करने और कुशल होने की अनुमति देता है - और मूल स्टेल को अच्छी तरह से लिखा जाना चाहिए - ताकि खाली सेट, वेक्टर या सूची कंटेनर हो डिफ़ॉल्ट मामले में वास्तव में किसी भी पेलोड के खाली।

पेड़ कई गणितीय संरचनाओं में एक महत्वपूर्ण भूमिका निभाते हैं (कसाई, ग्रॉसमैन और लार्सन के शास्त्रीय कागजात देखें; कॉन्स और क्रिमर के कागजात भी उनके उदाहरणों के लिए शामिल हो सकते हैं, और इन्हें कैसे गणना करने के लिए उपयोग किया जाता है)। यह सोचना सही नहीं है कि उनकी भूमिका बस कुछ अन्य परिचालनों को सुविधाजनक बनाने के लिए है। बल्कि वे डेटा संरचना के रूप में उनकी मौलिक भूमिका के कारण उन कार्यों को सुविधाजनक बनाते हैं।

हालांकि, पेड़ों के अलावा "सह पेड़" भी हैं; सभी के ऊपर के पेड़ों में संपत्ति है कि यदि आप रूट हटाते हैं तो आप सबकुछ हटा देते हैं।

पेड़ पर इटरेटर्स पर विचार करें, शायद उन्हें इटरेटर के एक साधारण ढेर के रूप में, एक नोड, और उसके माता-पिता के लिए, जड़ तक महसूस किया जाएगा।

template<class TREE>
struct node_iterator : std::stack<TREE::iterator>{
operator*() {return *back();}
...};

हालांकि, आप जितना चाहें उतने हो सकते हैं; सामूहिक रूप से वे एक "पेड़" बनाते हैं, लेकिन जहां सभी तीर जड़ की दिशा में दिशा में बहते हैं, यह सह-पेड़ पुनरावृत्त हो सकता है हालांकि यह छोटे-छोटे इटरेटर और रूट की ओर इशारा करता है; हालांकि इसे पूरे या नीचे नेविगेट नहीं किया जा सकता है (अन्य पुनरावृत्तकर्ता इसे ज्ञात नहीं हैं) और न ही सभी उदाहरणों का ट्रैक रखकर इटेटर को इकट्ठा किया जा सकता है।

पेड़ अविश्वसनीय रूप से उपयोगी हैं, उनके पास बहुत सारी संरचना है, यह निश्चित रूप से सही दृष्टिकोण प्राप्त करने के लिए एक गंभीर चुनौती बनाता है। मेरे विचार में यही कारण है कि वे एसटीएल में लागू नहीं किए गए हैं। इसके अलावा, अतीत में, मैंने लोगों को धार्मिक पाया है और एक प्रकार के कंटेनर का विचार ढूंढ लिया है जिसमें अपने स्वयं के प्रकार चुनौतीपूर्ण उदाहरण हैं - लेकिन उन्हें इसका सामना करना पड़ता है - यही वह पेड़ प्रकार है जो यह दर्शाता है - यह एक नोड है जिसमें संभवतः (छोटे) पेड़ के खाली संग्रह। वर्तमान भाषा container<B> लिए डिफ़ॉल्ट कन्स्ट्रक्टर प्रदान करने में चुनौती के बिना अनुमति देती है container<B> B , आदि के लिए ढेर (या कहीं और) पर स्थान आवंटित नहीं करता है।

अगर किसी ने एक अच्छा रूप में, मानक में अपना रास्ता खोज लिया तो मैं खुश हूं।


यह एक आशाजनक लग रहा है और ऐसा लगता है कि आप क्या देख रहे हैं: http://tree.phi-sci.com/


शायद इसी कारण से बढ़ावा में कोई पेड़ कंटेनर नहीं है। ऐसे कंटेनर को लागू करने के कई तरीके हैं, और इसका उपयोग करने वाले हर किसी को संतुष्ट करने का कोई अच्छा तरीका नहीं है।

विचार करने के लिए कुछ मुद्दे:
- क्या नोड फिक्स्ड या वेरिएबल के लिए बच्चों की संख्या है?
- प्रति नोड कितना ओवरहेड? - यानी, क्या आपको माता-पिता पॉइंटर्स, भाई पॉइंटर्स इत्यादि की आवश्यकता है।
- क्या एल्गोरिदम प्रदान करने के लिए? - विभिन्न iterators, खोज एल्गोरिदम, आदि

अंत में, समस्या यह साबित होती है कि एक वृक्ष कंटेनर जो हर किसी के लिए पर्याप्त उपयोगी होगा, इसका उपयोग करने वाले अधिकांश लोगों को संतुष्ट करने के लिए बहुत भारी वजन होगा। यदि आप कुछ शक्तिशाली खोज रहे हैं, तो बूस्ट ग्राफ लाइब्रेरी अनिवार्य रूप से एक पेड़ पुस्तकालय का उपयोग करने के लिए एक सुपरसेट है।

यहां कुछ अन्य सामान्य वृक्ष कार्यान्वयन हैं:
- कास्पर पीटर 'पेड़। एच
- एडोब का जंगल
core::tree


सभी एसटीएल कंटेनरों का उपयोग इटरेटर्स के साथ किया जा सकता है। आपके पास एक इटरेटर एक पेड़ नहीं हो सकता है, क्योंकि आपके पास पेड़ के माध्यम से 'एक सही' रास्ता नहीं है।





tree