जैसा कि आप I assume the buckets can get big... कह रहे हैं, std::list का उपयोग करना बेहतर है। खोज दोनों मामलों में रैखिक है, लेकिन तत्व जोड़ना std::list में स्थिर है।
I guess they're all the same, since data isn't ordered - नहीं, वे नहीं हैं। यदि वे थे, तो केवल एक कंटेनर होगा। प्रत्येक कंटेनर के अपने फायदे और नुकसान होते हैं, विभिन्न स्थितियों के लिए विभिन्न कंटेनरों का उपयोग किया जाता है।
वेक्टर के बारे में एक छोटी सी जानकारी:
std::vector, क्षमता है कि क्यों यह capacity() और size() तरीकों है है। वे दोनों अलग हैं। तो, मान लीजिए कि क्षमता 4 है और आपके पास 2 तत्व हैं, तो आकार 2 होगा। तो, एक और तत्व जोड़ना आकार बढ़ाएगा (3 होगा) और यह सब बहुत तेज़ है।
लेकिन क्या होता है जब आपको 5+ तत्व जोड़ना होता है और क्षमता 4 होती है? पूरी तरह से नया स्मृति आवंटित किया जाता है, सभी वर्ष तत्वों नई स्मृति में की नकल की है, सभी वर्ष तत्वों (, उनके विनाशकर्ता कहा जाता है, तो उपयोगकर्ता-निर्धारित प्रकार) नष्ट हैं। तब पुरानी मेमोरी मुक्त होनी चाहिए। ये महंगी परिचालन हैं यदि आपको लगता है कि तत्वों को जोड़ना/निकालना अक्सर अधिक होगा।
आप कुछ स्मृति को पहले से आरक्षित करने के लिए std::vector::reserve विधि का उपयोग करके और हर समय नई मेमोरी को पुन: आवंटित नहीं करने और सब कुछ बार-बार कॉपी करने के लिए इसका उपयोग कर सकते हैं। लेकिन यह उपयोगी है जब आप इन वैक्टरों के अनुमानित आकार को जानते हैं। मुझे लगता है कि आप अपनी स्थिति में नहीं हैं (बहुत मेमोरी आरक्षित करना भी एक अच्छा समाधान नहीं है - आपको मेमोरी बर्बाद नहीं करना चाहिए जैसे कि) तो, फिर, मैं std :: सूची पसंद करूंगा।
या डबल हैश।
वैसे भी, नई स्मृति की आवंटन और वस्तुओं की प्रतिलिपि ऐसा नहीं होती है, क्योंकि std::vector "चालाक" है और जब नई जगह आवंटित होती है, तो यह क्षमता केवल 1 तत्व या कुछ के साथ क्षमता में वृद्धि नहीं करती है। मुझे लगता है कि यह इसे दोगुना करता है, लेकिन मैं इसके बारे में निश्चित नहीं हूं। Argh, मुझे नहीं पता कि यह वास्तव में अंग्रेजी में कैसे कहा जाता है .. शायद कुछ "संचित समय/स्मृति" या "संचित जटिलता" की तरह कुछ:?पता नहीं:/
नोट: जो भी आप चुनते हैं, मैं आपको हैश-फ़ंक्शन पर अपना ध्यान देने का सुझाव दूंगा। यह यहां सबसे महत्वपूर्ण है। एक हैश कंटेनर में एक ही हैश के साथ बहुत से तत्व नहीं होने चाहिए। तो, मेरी सलाह है कि एक अच्छा हैश-फ़ंक्शन खोजना और फिर इससे कोई फर्क नहीं पड़ता।
आशा है कि मदद की (:
संपादित करें: मैं आप इस लेख की सलाह देते हैं - comparing std::vector and std::deque - यह एकदम सही है - स्मृति के उपयोग (आवंटन, deallocating, बढ़ रही है), CPU उपयोग, आदि मैं था तुलना इस तरह के आलेखों के लिए पूरे site की अनुशंसा करें - बहुत सारे नहीं हैं, लेकिन वास्तव में अच्छी तरह से लिखे गए हैं।
स्रोत
2010-11-20 23:38:46
वेक्टर ठीक है, जरूरी नहीं है। निकालें-मध्य-मध्य कुशल नहीं है, इसलिए यदि आपकी बाल्टी आपको बड़ी हो सकती है इसकी तुलना 'सूची' और/या 'डेक' के साथ की जा सकती है। यदि आपकी बाल्टी को बड़ा होने की अनुमति नहीं है, तो 'वेक्टर' अधिक आवंटित हो सकता है। इन तीनों में रैखिक खोज है। obvio हमें संरचना जो रैखिक लुकअप समय को हरा सकती है वह एक और हैशटेबल (या फिर एक ही टेबल) है, जैसा कि डबल हैशिंग में है। आदेश के बिना मानक पुस्तकालयों में कुछ भी नहीं है: वे सब कुछ आदेश, और शुद्ध अनुक्रमों के साथ चीजें हैं। –
'डेक' 'वेक्टर 'से बेहतर हो सकता है, क्योंकि इसे कभी भी पुन: आवंटित नहीं करना और सबकुछ ले जाना है। एक्सेस थोड़ी धीमी है, पुश_बैक संभावित रूप से बहुत तेज है, इस पर निर्भर करता है कि तत्वों की प्रतिलिपि कितनी महंगी है। 'सूची' आमतौर पर या तो अधिक स्मृति आवंटन करता है, और उस कारण से धीमा हो सकता है। –