कैसे एसटीएल ने कंटेनरों को अपना अंत पता किया?

मुझे पता है कि मानक एसटीएल कंटेनरों को लागू करने के तरीके को निर्देशित नहीं करता है, बल्कि यह उनमें से प्रत्येक के लिए आवश्यकताओं का एक सेट जरूरी है।कैसे एसटीएल ने कंटेनरों को अपना अंत पता किया?

हालांकि, यह व्यापक रूप से ज्ञात है कि एसटीएल आदेश दिया गया है कि आमतौर पर red–black trees के रूप में लागू किया जाता है।

आप उनके संबंधित iterators का उपयोग कर एक std::set या एक std::map के तत्वों के माध्यम से पुनरावृति कर सकते हैं या के बाद से सी ++ 11 छोरों का उपयोग थी।

हालांकि मुझे क्या पहेली है, एसटीएल में एक आदेशित कंटेनर "अंत" है। या इसे एक और तरीका दें, क्योंकि उन्हें पेड़ों के रूप में लागू किया गया है, कंटेनर का अंत कैसे कार्यान्वित किया गया है या यह लागू किया जा सकता है?

मुझे पता है कि मानक तय §23.2.1/सी जनरल कंटेनर आवश्यकताओं (जोर मेरा):

शुरू() पुनरावर्तक कंटेनर में पहला तत्व की चर्चा करते हुए देता है। अंत() एक पुनरावर्तक देता है जो कंटेनर के लिए पिछले-अंत-अंत मूल्य है। यदि कंटेनर खाली है, तो शुरू करें() == अंत();

ठीक है, संगत कंटेनरों के लिए यह आसान है, लेकिन पेड़ों के लिए यह "अतीत-अंत" कैसे बनाया जा सकता है?

स्रोत

2015-11-11 101010

यह समझें कि "अतीत-अंत" एक तार्किक अवधारणा है, भौतिक नहीं। इसका शाब्दिक अर्थ यह है कि जब आप अंतिम वैध प्रविष्टि से आगे बढ़ते हैं तो आपको वह इटेटरेटर मिलता है, लेकिन उस इटरेटर की आंतरिक सामग्री कुछ भी हो सकती है। –

पेड़ ट्रैवर्सल जैसे चौड़ाई-पहले और गहराई को समाप्त करने से पहले() और अंत() की प्राकृतिक धारणा है, इस प्रकार संबंधित पुनरावृत्तियों के बारे में अवधारणात्मक रूप से कुछ भी नहीं है। –

@MarkRansom मेला पर्याप्त, यह एक तार्किक अवधारणा है। लेकिन आप इस तरह की तार्किक अवधारणा को कैसे कार्यान्वित करते हैं? मेरा मतलब कोड में है। – 101010

इस जरूरत की तरह "सूची की तरह" कंटेनरों के सभी, अंत के लिए प्रहरी नोड के कुछ प्रकार है, क्योंकि उपयोगकर्ता, end() प्राप्त कर सकते हैं कंटेनर में कुछ डालने, इटरेटर घटती है, और कम कर end() इंगित करना चाहिए उस सम्मिलित तत्व के लिए। मेरी समझ यह है कि कुछ कार्यान्वयन गतिशील रूप से इसके लिए आवंटित किए जाएंगे, और कुछ गतिशील सेंटीनेल नोड को कंटेनर के अंदर ही रखेंगे।

स्रोत

2015-11-11 16:28:05

मैं मानक में कोई स्थान नहीं ढूंढ पा रहा हूं जिसका अर्थ है कि 'std :: map :: end() 'या' std :: set :: end() 'को एक कम करने योग्य इटरेटर वापस करना होगा। आप जो कह रहे हैं वह 'basic_string',' array', 'deque',' list' और 'vector' के लिए सच है, लेकिन ओपी ने 'सेट' और 'मानचित्र' के बारे में पूछा। –

@ АндрейБеньковский: N4527 23.2.1 [container.requirements.general]/12: अन्यथा निर्दिष्ट नहीं किया गया [...] एक कंटेनर सदस्य फ़ंक्शन का आह्वान [...] इटेटर्स को ऑब्जेक्टर्स को अमान्य नहीं करेगा, या ऑब्जेक्ट्स के मानों को बदल नहीं देगा उस कंटेनर के भीतर। - और मानचित्र :: सम्मिलन स्पष्ट रूप से अन्यथा नहीं बताता है। 23.2.4 [सहयोगी.रेक्मेट्स]/9: सम्मिलित और प्रतिस्थापन सदस्य कंटेनर की पहचानकर्ताओं और संदर्भों की वैधता को प्रभावित नहीं करेंगे, और मिटाए गए सदस्यों को केवल तत्वों और मिटाए गए तत्वों के संदर्भों को अमान्य कर दिया जाएगा। –

@ АндрейБеньковский: विशेष रूप से, यह 'basic_string',' deque', या 'vector' के लिए * सत्य नहीं है - उन मामलों में यदि डालने वाले इटरेटर द्वारा पुन: आवंटन किया जाता है और संदर्भ अमान्य होते हैं। और आप 'सरणी' में सम्मिलित नहीं कर सकते हैं, जो वास्तव में यहां प्रासंगिक नहीं है। –

मैं सिर्फ विजुअल स्टूडियो 2013 एसटीएल में map कंटेनर के कार्यान्वयन का निरीक्षण किया है, और यहाँ कैसे end कार्यान्वित किया जाता है है। जब map बनाया गया है, आरबी पेड़ का एक प्रमुख तत्व आवंटित किया गया है और यह तत्व कंटेनर का अंत घोषित किया गया है।

जब आप एक वैध इटरेटर के माध्यम से कंटेनर को पार करते हैं, operator++ और operator-- बस मुख्य तत्व को छोड़ दें। और जब आप पेड़ के अंतिम तत्व तक पहुंचते हैं और एक पुनरावर्तक को बढ़ाते हैं, तो यह ऊपर चढ़ता है (एक सही उप-खोज की तलाश करता है) और अंत में पेड़ के सिर तक पहुंच जाता है, जो end है।

स्रोत

2015-11-11 16:47:38 AlexStepanov

कैसे एसटीएल ने कंटेनरों को अपना अंत पता किया?

उत्तर

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