सी ++ में एसटीएल सेट की अंतर्निहित डेटा संरचना क्या है?

मैं जानना चाहता हूं कि सी ++ में एक सेट कैसे कार्यान्वित किया जाता है। अगर मैं एसटीएल प्रदान किए गए कंटेनर का उपयोग किए बिना अपना खुद का सेट कंटेनर लागू करना चाहता हूं, तो इस कार्य के बारे में जाने का सबसे अच्छा तरीका क्या होगा?सी ++ में एसटीएल सेट की अंतर्निहित डेटा संरचना क्या है?

मुझे लगता है कि एसटीएल सेट एक बाइनरी खोज पेड़ की सार डेटा संरचना पर आधारित हैं। तो अंतर्निहित डेटा संरचना क्या है? एक सरणी?

इसके अलावा, insert() एक सेट के लिए कैसे काम करता है? सेट कैसे जांचता है कि इसमें कोई तत्व पहले से मौजूद है या नहीं?

मैंने विकिपीडिया पर पढ़ा है कि एक सेट को लागू करने का एक और तरीका हैश टेबल के साथ है। यह कैसे काम करेगा?

स्रोत

2010-04-01 zebraman

आपको सबसे पहले एक Node struct को परिभाषित करते हुए एक द्विआधारी खोज वृक्ष को लागू कर सकता है: तो फिर

struct Node 
{ 
    void *nodeData; 
    Node *leftChild; 
    Node *rightChild; 
}

, यदि आप किसी अन्य Node *rootNode;

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

डुप्लिकेट के मामले में, उन्हें आम तौर पर सेट में अनुमति नहीं दी जाती है, ताकि आप या तो अपने इनपुट के आधार पर उस इनपुट को छोड़ दें, अपवाद फेंक दें, आदि।

स्रोत

2010-04-01 04:41:45

जहां तक मुझे पता है, std :: set एक आदेशित कंटेनर है। यदि यह एक बीएसटी ट्रैवर्सिंग का आदेश कैसे दिया जा सकता है? – Shasha99

सी ++ में एक विशेष कंटेनर लागू किया गया है जो पूरी तरह कार्यान्वयन निर्भर है। यह आवश्यक है कि मानक में निर्धारित आवश्यकताओं को पूरा करने के परिणामस्वरूप, विभिन्न तरीकों के लिए जटिलता आवश्यकता, इटरेटर आवश्यकताओं आदि

स्रोत

2010-04-01 04:42:45 KTC

उसने कहा, अधिकांश (सभी?) लाल-काले पेड़ हैं। – GManNickG

http://sourceforge.net/projects/stlavlmap/ पर एक एवीएल आधारित कार्यान्वयन है और http://idlebox.net/2007/stx-btree/ – MSalters

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

केटीसी ने कहा, कैसे std::set लागू किया जा सकता है - सी ++ मानक बस एक सार डेटा प्रकार निर्दिष्ट करता है। दूसरे शब्दों में, मानक निर्दिष्ट नहीं करता है कि कंटेनर को कैसे कार्यान्वित किया जाना चाहिए, केवल समर्थन के लिए आवश्यक संचालन क्या है। हालांकि, एसटीएल के अधिकांश कार्यान्वयन, जहां तक मुझे पता है, red-black trees या किसी अन्य प्रकार के अन्य संतुलित बाइनरी खोज पेड़ का उपयोग करें (उदाहरण के लिए, जीएनयू libstdC++, लाल-काले पेड़ों का उपयोग करता है)।

जबकि आप सैद्धांतिक रूप से एक हैश तालिका के रूप में सेट को कार्यान्वित कर सकते हैं और लुकअप और डालने के लिए तेज़ एसिम्प्टोटिक प्रदर्शन (एमओ (कुंजी एन) बनाम ओ (लॉग एन) प्राप्त कर सकते हैं), जिसके लिए उपयोगकर्ता को हैश फ़ंक्शन की आवश्यकता होगी वे जो भी प्रकार स्टोर करना चाहते थे (Wikipedia's entry on hash tables देखें कि वे कैसे काम करते हैं) की एक अच्छी व्याख्या के लिए। बाइनरी सर्च पेड़ के कार्यान्वयन के लिए, आप एक सरणी का उपयोग नहीं करना चाहेंगे - जैसा कि राउल ने उल्लेख किया है, आप किसी प्रकार की Node डेटा संरचना चाहते हैं।

स्रोत

2010-04-01 05:30:43 Toli

आप एक हैश तालिका के साथ * ए * सेट प्रकार को कार्यान्वित कर सकते हैं। हालांकि, आप (कम से कम आसानी से नहीं) को लागू कर सकते हैं जो std :: set iterators की आवश्यकताओं को पूरा करता है। – dan04

@ dan04: आप std :: set lookup और insert के लिए आवश्यकताओं को पूरा करने वाले एक को भी लागू नहीं कर सकते हैं। जैसा कि टोली कहता है, आपको कुंजी प्रकार पर हैश फ़ंक्शन की आवश्यकता है, और 'std :: set' के उपयोगकर्ता को मानक प्रदान करने के लिए मानक की आवश्यकता नहीं है। तो जब उनका कोड हैश (MyElement) 'के लिए कोई मिलान नहीं मिला है, तो इसका मतलब है कि std :: set कार्यान्वयन दोषपूर्ण है। –

मुझे लगता है कि एसटीएल सेट बाइनरी सर्च पेड़ की सार डेटा संरचना पर आधारित हैं। तो अंतर्निहित डेटा संरचना क्या है? एक सरणी?

जैसा कि अन्य ने इंगित किया है, यह भिन्न होता है। एक सेट आमतौर पर एक पेड़ (लाल-काला पेड़, संतुलित पेड़, आदि) के रूप में लागू किया जाता है, लेकिन अन्य कार्यान्वयन मौजूद हो सकते हैं।

इसके अलावा, सेट के लिए कैसे सम्मिलित() काम करता है?

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

सेट कैसे जांचता है कि तत्व पहले से मौजूद है या नहीं?

यदि यह एक पेड़ के रूप में लागू किया जाता है, तो यह पेड़ को पार करता है और प्रत्येक तत्व की जांच करता है। हालांकि, सेट डुप्लिकेट तत्वों को संग्रहीत करने की अनुमति नहीं देते हैं। यदि आप एक सेट चाहते हैं जो डुप्लिकेट तत्वों को अनुमति देता है, तो आपको एक मल्टीसेट की आवश्यकता है।

मैं विकिपीडिया पर पढ़ा है कि एक और तरीका एक सेट लागू करने के लिए एक हैश तालिका के साथ है। यह कैसे काम करेगा?

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

स्रोत

2010-04-01 06:55:40 jasonline

सी ++ में एसटीएल सेट की अंतर्निहित डेटा संरचना क्या है?

उत्तर

संबंधित मुद्दे