एसटीएल मानचित्र के माध्यम से लूप को एक वेक्टर बनाम, एक वेक्टर बनाम प्रदर्शन के बीच प्रदर्शन अंतर क्या है? मैं सम्मिलन, हटाना, और कुछ पहुंच के लिए मानचित्र कुंजी का उपयोग करना चाहता हूं, लेकिन मुझे मानचित्र में प्रत्येक तत्व पर नियमित पहुंच करने की भी आवश्यकता है।एसटीएल मानचित्र बनाम वेक्टर के लिए इटरेटर एक्सेस प्रदर्शन?
उत्तर
मानचित्र और वेक्टर दोनों के साथ, पूरे संग्रह के माध्यम से पुनरावृत्त ओ (एन) है। हालांकि (सूची बनाम वेक्टर की तरह) वेक्टर तत्वों को संगत रूप से स्टोर करता है, इसलिए अगले तत्व तक पहुंच बहुत सस्ता है क्योंकि यह कैश का उपयोग बेहतर तरीके से करेगी, जबकि नक्शा नहीं होगा।
लेकिन चूंकि को की आवश्यकता है ताकि कुंजी पर आधारित लुकअप हो, वास्तव में कोई विकल्प नहीं है। आप पहले तत्व पर क्रमबद्ध जोड़े के वेक्टर का उपयोग कर सकते हैं, लेकिन यदि संग्रह को उत्परिवर्तनीय करने की आवश्यकता है तो यह बहुत धीमी होगी। बस एक नक्शा का प्रयोग करें।
यदि आपको कुंजी द्वारा पहुंच का तेज़ तरीका चाहिए तो मानचित्र का उपयोग करें। अन्यथा वेक्टर का हर समय उपयोग करें जब तक कि प्रोफाइलर के साथ कुछ प्रदर्शन मुद्दों की खोज नहीं की जाएगी।
मानचित्र के प्रत्येक तत्व के माध्यम से इटरेटिंग ओ (एन) समय लेता है। wikipedia
मुझे नहीं पता कि क्यों कोई डाउनोट किया गया। यह पूरे पेड़ को स्थानांतरित करने के लिए वास्तव में ओ (एन) है। –
मैं अच्छा होगा अगर यह दिखाएगा कि किसने मतदान किया था। –
एक खूनी बदला लेने के लिए? :) –
पेड़ ब्राउज़ करना महंगा नहीं है (ग्रोसो मोडो एक लिंक्ड सूची का पालन करने जैसा है), आपको कैश से ज्यादा कैश से लाभ नहीं होगा, लेकिन आम तौर पर यह तब होता है जब आप महंगे होते हैं, न कि खुद ही पुनरावृत्ति।
क्या आप पूरे मानचित्र के माध्यम से पुन: प्रयास करते समय हमें क्या करना चाहते हैं, इसके बारे में और बता सकते हैं?
This link में सभी एसटीएल कंटेनर पर विभिन्न संचालन के लिए प्रदर्शन की एक अच्छी तालिका है।
आम तौर पर, यदि आपको किसी कुंजी के आधार पर बहुत सारी डालने, निकालने या खोज करने की आवश्यकता है तो नक्शा जाने का रास्ता है।
यदि आपको केवल एक बार कंटेनर सेट अप करने की आवश्यकता है और फिर इसे सरणी की तरह एक्सेस करें तो वेक्टर का उपयोग करें।
संपादित करें: एसटीएल कंटेनर के संचालन के प्रदर्शन तालिका:
एक मानचित्र के माध्यम सेप्रश्न में एक सूक्ष्मता है। उपयोगकर्ता मानचित्र में एक तत्व, बल्कि _all_ तत्वों तक पहुंच नहीं चाहता है। अमूर्त लागत विश्लेषण पूरे मानचित्र ट्रांसवर्सल के लिए ओ (एन) उत्पन्न करता है (पेड़ में प्रत्येक किनारा केवल एक बार नीचे, एक बार ऊपर की तरफ स्थानांतरित होता है)। –
लिंक टूटा हुआ है। मुझे लगता है कि यह होना चाहिए: http://devmentor.org/references/stl/stl.php –
वेक्टर के लिए सिर क्यों डालें और वेक्टर के लिए सिर हटाएं ओ (1) है? वे दोनों ओ (एन) होना चाहिए। और वेक्टर खोज ओ (लॉग एन) है? वहां कुछ गड़बड़ है। – Slava
पुनरावृत्ति रेखीय हो सकता है लेकिन व्यावहारिक रूप से, यह C++ कार्यान्वयन से इतनी कुशल नहीं है। तो मेरी सलाह है वेक्टर का उपयोग करना और रैखिक समय में वेक्टर में वस्तुओं का पता लगाने के लिए एक और मानचित्र का उपयोग करना।
मानचित्र में प्रत्येक तत्व का उपयोग कुछ और महत्वपूर्ण है, क्योंकि यह अक्सर बंद हो रहा है, लेकिन मुझे अभी भी उचित त्वरित कुंजी-आधारित लुकअप की आवश्यकता है (मैं उस आवश्यकता को निकाल सकता हूं, लेकिन चीजें अनियंत्रित बालों वाली होंगी)। नक्शा ऊपर ग्रेग रोजर्स के उत्तर के अनुसार बेहतर फिट प्रतीत होता है। –