सी ++ एसटीएल में सेट और हैशसेट के बीच क्या अंतर है?

Question

मुझे एक दूसरे को कब चुनना चाहिए? क्या कोई पॉइंटर्स हैं जो आप सही एसटीएल कंटेनरों का उपयोग करने के लिए सिफारिश करेंगे?

Answer 1

hash_set एक ऐसा एक्सटेंशन है जो सी ++ मानक का हिस्सा नहीं है। set के लिए लुकअप ओ (लॉग एन) के बजाय ओ (1) होना चाहिए, इसलिए यह ज्यादातर परिस्थितियों में तेज़ होगा।

जब आप कंटेनर के माध्यम से पुन: प्रयास करते हैं तो एक और अंतर दिखाई देगा। set सॉर्ट किए गए क्रम में सामग्री वितरित करेगा, जबकि hash_set अनिवार्य रूप से यादृच्छिक (धन्यवाद Lou Franco) होगा।

संपादित करें: C++ मानक को C++ 11 अपडेट unordered_set पेश किया गया है जिसे hash_set के बजाय प्राथमिकता दी जानी चाहिए। प्रदर्शन समान होगा और मानक द्वारा गारंटीकृत है। नाम में "unordered" जोर देकर कहते हैं कि यह किसी भी विशेष क्रम में परिणाम उत्पन्न करेगा।

Answer 2

एक हैश_सेट एक हैश तालिका द्वारा कार्यान्वित किया जाएगा, जिसमें ज्यादातर ओ (1) संचालन होते हैं, जबकि एक सेट को किसी प्रकार के पेड़ (एवीएल, लाल काला, आदि) द्वारा लागू किया जाता है जिसमें ओ (लॉग एन) होता है। संचालन, लेकिन क्रमबद्ध क्रम में हैं।

संपादित करें: मैंने लिखा था कि पेड़ ओ (एन) हैं। यह पूरी तरह गलत है।

Answer 3

stl::set एक बाइनरी खोज पेड़ के रूप में लागू किया गया है। hashset एक हैश तालिका के रूप में लागू किया गया है।

मुख्य मुद्दा यह है कि बहुत से लोग stl::set का उपयोग करते हैं, यह सोचते हुए कि यह ओ (1) की तलाश में हैश तालिका है, जो यह नहीं है, और नहीं है। यह देखने के लिए वास्तव में ओ (लॉग (एन)) है। अन्यथा जो डेटास्ट्रक्चर का बेहतर विचार पाने के लिए बाइनरी पेड़ बनाम हैश टेबल के बारे में पढ़ते हैं।

Answer 4

ध्यान में रखना एक और बात यह है कि हैश_सेट के साथ आपको हैश फ़ंक्शन प्रदान करना है, जबकि एक सेट को केवल तुलना फ़ंक्शन ('<') की आवश्यकता होती है जो परिभाषित करना आसान है (और देशी प्रकारों के लिए पूर्वनिर्धारित)।

Answer 5

मुझे नहीं लगता कि किसी ने अभी तक प्रश्न के दूसरे भाग का उत्तर दिया है।

हैश_सेट या अनॉर्डर्ड_सेट का उपयोग करने का कारण आमतौर पर ओ (1) लुकअप टाइम होता है। मैं आम तौर पर कहता हूं क्योंकि हर बार, कार्यान्वयन के आधार पर, हैश को एक बड़े हैश सरणी में कॉपी करना पड़ सकता है, या हैश बाल्टी में हजारों प्रविष्टियां हो सकती हैं।

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