मानचित्र और unordered_map के बीच कैसे चयन करें?

Question

मान लीजिए कि मैं कुंजी के रूप में एक स्ट्रिंग के साथ डेटा मैप करना चाहता था। मुझे किस कंटेनर को चुना जाना चाहिए, map या unordered_map? unordered_map अधिक मेमोरी लेता है तो मान लीजिए कि स्मृति कोई मुद्दा नहीं है, और चिंता तेज है।

unordered_map आम तौर पर हे (एन) के सबसे ज्यादा मामले के साथ हे (1) की औसत जटिलता देना चाहिए। ओ (एन) में कौन से मामले आएंगे? mapunordered_map से अधिक समय प्रभावी लगता है? क्या ऐसा होता है जब एन छोटा होता है?

मान लिया जाये कि मैं डिफ़ॉल्ट haser बनाम साथ एसटीएल unordered_map का प्रयोग करेंगे नक्शा। स्ट्रिंग कुंजी है।

मैं बजाय तत्वों से अधिक पुनरावृति एक व्यक्ति तत्व हर बार उपयोग करने के लिए जा रहा हूँ, मैं map को प्राथमिकता देनी चाहिए?

Answer 1

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

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

यदि आप किसी क्रमबद्ध फैशन में मानचित्र (इटरेटर्स का उपयोग करके) को पार करना चाहते हैं, तो आप unordered_map का उपयोग नहीं कर सकते हैं।इसके विपरीत, map न केवल उस की अनुमति देता है, बल्कि कुंजी के अनुमान के आधार पर आपको मानचित्र में अगला तत्व भी प्रदान कर सकता है (lower_bound और upper_bound विधियों को देखें)।

Answer 2

क्या मामलों में यह हे (एन) के लिए मिलता है?

अगर आप इस तरह के एक बुरा हैश फंक्शन जो (यानी टकराव का उत्पादन) सभी इनपुट stirngs के लिए एक ही हैश मान पैदा करता है ...

क्या कंटेनर मैं चुना जाना चाहिए था, मानचित्र या unordered_map ?

यह हमेशा आपके पास आवश्यक आवश्यकताओं और प्रकार/डेटा के प्रश्नों का प्रश्न है।

मानचित्र को unordered_map से अधिक समय प्रभावी कब मिलता है?

यह सिर्फ अलग संरचनाओं है। आप अपने सामान्य उपयोग मामलों के आधार पर उनमें से किसी एक का उपयोग करने के लिए बेहतर होगा (खाते में आपके पास किस प्रकार का डेटा है और इसकी राशि)

क्या यह छोटा है जब n छोटा होता है?

छोटे डेटा राशि सब कुछ के मामले में विशेष रूप से एसटीएल कार्यान्वयन पर निर्भर करता ... तो कभी कभी भी एक सादे वेक्टर/सरणी साहचर्य कंटेनरों की तुलना में तेजी से हो सकता है ...

Answer 3

मुझे किस कंटेनर को चुना जाना चाहिए, मानचित्र या unordered_map? unordered_map अधिक मेमोरी लेता है तो मान लीजिए कि स्मृति कोई मुद्दा नहीं है, और चिंता तेज है।

प्रोफ़ाइल और फिर निर्णय लें। unordered_map आमतौर पर तेज़ है, लेकिन यह प्रति मामले भिन्न होता है।

यह किस मामले में ओ (एन) प्राप्त होगा?

जब हैशिंग अच्छी नहीं है और तत्वों का एक गुच्छा उसी डिब्बे को सौंपा जा रहा है।

मानचित्र को unordered_map से अधिक समय प्रभावी कब मिलता है? क्या यह छोटा होता है जब एन छोटा होता है?

शायद नहीं, लेकिन अगर आप वास्तव में परवाह करते हैं तो इसे प्रोफाइल करें। एक छोटे आकार के साथ एक कंटेनर होने के नाते आपके कार्यक्रम की बाधा बेहद असंभव प्रतीत होती है। वैसे भी, ऐसे मामलों के लिए रैखिक खोज के साथ एक साधारण vector तेज हो सकता है।

---

निर्णय लेने पर सबसे महत्वपूर्ण बात यह है कि ऑर्डरर अमान्यता की व्यवस्था और कमी की आवश्यकता है। यदि आपको या तो चाहिए, तो आपको map का उपयोग करना होगा। अन्यथा, unordered_map।

Answer 4

     | map    | unordered_map 
--------------------------------------------------------- 
element ordering  | strict weak  | n/a 
         |     | 
common implementation | balanced tree | hash table 
         | or red-black tree| 
         |     | 
search time   | log(n)   | O(1) if there are no hash collisions 
         |     | Up to O(n) if there are hash collisions 
         |     | O(n) when hash is the same for any key 
         |     |  
Insertion time   | log(n)+rebalance | Same as search 
         |     | 
Deletion time   | log(n)+rebalance | Same as search 
         |     | 
needs comparators  | only operator < | only operator == 
         |     | 
needs hash function | no    | yes 
         |     | 
common use case  | when good hash is| In most other cases. 
         | not possible or | 
         | too slow. Or when| 
         | order is required|