सी ++ unordered_map

में प्री-आवंटित बाल्टी मैं बड़ी मात्रा में डेटा स्टोर करने के लिए gnu ++ 0x से unordered_map का उपयोग कर रहा हूं। मैं बड़ी संख्या में तत्वों के लिए स्थान आवंटित करना चाहता हूं, क्योंकि मैं उपयोग की गई कुल स्थान को बाध्य कर सकता हूं।सी ++ unordered_map

std::unordered_map m; 
m.resize(pow(2,x));

जहां एक्स में जाना जाता है:

मैं ऐसा करने में सक्षम होने के लिए क्या चाहते हैं कॉल है।

unordered_map इसका समर्थन नहीं करता है। यदि संभव हो तो मैं unordered_map का उपयोग करूंगा, क्योंकि यह अंततः मानक का हिस्सा होगा।

कुछ अन्य बाधाओं:

विश्वसनीय हे (1) का उपयोग और नक्शे के उत्परिवर्तन की आवश्यकता है। वांछित हैश और तुलना कार्यों पहले से ही गैर मानक और कुछ हद तक महंगा हैं। ओ (लॉग एन) उत्परिवर्तन (जैसा कि std :: map के साथ) बहुत महंगा है।

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

स्रोत

2011-05-05 JAD

m.rehash(pow(2,x));

यदि pow(2, x) बाल्टी की संख्या है जिसे आप प्रीलाइटेड करना चाहते हैं। आप यह भी कर सकते हैं:

m.reserve(pow(2,x));

लेकिन अब pow(2, x) तत्वों आप डालने की योजना बना रहे की संख्या है। दोनों कार्य कुछ भी नहीं करते हैं लेकिन बाल्टी प्रीलाकेट करते हैं। वे कोई तत्व नहीं डालते हैं। और वे दोनों आपके उपयोग के मामले के लिए बिल्कुल इस्तेमाल किया जाना है।

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

a.rehash(n): Postconditions:a.bucket_count() >= a.size()/a.max_load_factor() and a.bucket_count() >= n

यहाँ सटीक शब्दों कि नवीनतम (N4660) rehash को तर्क निर्दिष्ट करने के लिए उपयोग करता है।

यह पोस्टकंडिशन सुनिश्चित करता है कि bucket()_count() >= n, और load_factor()max_load_factor() से कम या उसके बराबर रहता है।

इसके बाद reserve(n)rehash(n) के संदर्भ में परिभाषित किया गया है:

a.reserve(n): a.rehash(ceil(n/a.max_load_factor())) के रूप में एक ही।

स्रोत

2011-05-05 23:56:25

आप संकेत का उपयोग कर रहे हैं, जैसे कि यह है: इटरेटर std :: set :: insert (iterator hint, const value_type और value); http://en.cppreference.com/w/cpp/container/set/insert, अनुचित शब्द दिखता है। –

मैं std::unordered_map के लिए अपना स्वयं का आवंटन लिखने का सुझाव दूंगा जो आपको इच्छित तरीके से स्मृति आवंटित करता है।

स्रोत

2011-05-05 23:38:40 orlp

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

स्रोत

2011-05-05 23:49:25

एसटीएल ओ (एन) अमूर्त सम्मिलन समय की गारंटी देता है, लेकिन इसे कार्यान्वित करने का एक आम तरीका निरंतर कारक द्वारा बाल्टी की संख्या में वृद्धि करना है, और फिर प्रत्येक मौजूदा तत्व को दोहराएं। यदि आप मानचित्र में n तत्व संग्रहीत कर रहे हैं तो यह ओ (लॉग n) बार होता है। जब n 2^बड़ा होता है, तो यह निष्पादित प्रविष्टियों की संख्या के लिए बड़ा का अतिरिक्त कारक जोड़ता है। मैं इस कारक को दाढ़ी देने की कोशिश कर रहा हूं। – JAD

"यह बड़े का एक अतिरिक्त कारक जोड़ता है" नहीं, यह 2 का अतिरिक्त कारक जोड़ता है। क्या आप समझते हैं कि अमूर्त परिचालन कैसे काम करते हैं? एकमात्र वास्तविक कारण यह जवाब गलत है क्योंकि यह ओ (एन) अमूर्त सम्मिलन समय "गारंटी" नहीं करता है, यह केवल यादृच्छिक रूप से सम्मिलित तत्वों पर अत्यधिक उच्च संभावना के साथ अपेक्षित ओ (एन) अमूर्त प्रविष्टि समय प्रदान करता है। यदि आप सटीक आकारों को जानते हैं कि बाल्टी समायोजित होंगी और हैश फ़ंक्शन का उपयोग किया जाएगा, तो हैश तालिका को ट्रिक करना और प्रत्येक सम्मिलन के लिए एन टकराव को मजबूर करना अभी भी संभव है। – codetaku

-2

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

स्रोत

2016-01-14 21:12:24 hrrl

आपके द्वारा किए गए कुछ बिंदु समझ में नहीं आते हैं, या आपने स्वयं को समझ में नहीं लिया है। उदाहरण के लिए "यदि मैप किए गए मान गतिशील रूप से बदलते हैं आकार (उदा। वेक्टर)"। इससे कोई फर्क नहीं पड़ता कि आपके पास वेक्टर (या उस मामले के लिए कोई कंटेनर या कक्षा) में कितने तत्व हैं, 'आकार (std :: vector )' वही रहता है (स्पष्ट रूप से उसी टी 'के लिए)। 'नक्शा' 1 तत्व के 'std :: vector' या 1 मिल तत्वों के' std :: vector' के लिए सटीक मात्रा को सुरक्षित रखेगा। "आप सबसे बड़ा कंटेनर आरक्षित कर सकते हैं जो कभी अस्तित्व में हो सकता है" एक और मुद्दा है कि मैं इस प्रश्न के संदर्भ में एक अच्छी सलाह के रूप में नहीं देखता हूं। – bolov

निर्माता http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map

तो सबसे आसान तरीका के अनुसार एक पैरामीटर "size_type bucket_count" लेता है क्या आपके उदाहरण कोड का कहना है क्या करना है:

std::unordered_map m{ pow(2,x) };

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

स्रोत

2016-10-07 18:21:10 Ben

सी ++ unordered_map

उत्तर

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