std :: मानचित्र <t1, t2> :: मिटाएं (इटरेटर स्थिति)?

Question

मैंने cplusplus.com पर पढ़ा है कि ऑपरेटर को गुजरने के द्वारा std::map में तत्व को हटाने के लिए ऑपरेशन निरंतर समय है।

यदि मैं गलत नहीं हूं (और अगर मैं हूं तो कृपया मुझे सही करें) इटरेटर मूल रूप से ++ ऑपरेटर के साथ मानचित्र में तत्वों के पॉइंटर्स हैं, वर्तमान तत्व के इन-ऑर्डर उत्तराधिकारी को वापस लौटते हुए मुझे लगता है कि एक क्रमबद्ध परिणाम std::map के ट्रैवर्सल पर हासिल किया जाता है।

अब नक्शा एक लाल काला पेड़ है, तो किसी तत्व को हटाने (अपने पते का उपयोग करके) को लॉगरिदमिक टाइम ऑपरेशन नहीं होना चाहिए, मुझे आश्चर्य है कि वे इसे निरंतर समय में कैसे करते हैं (जब तक कि अत्यधिक स्मृति अपर्याप्त विकल्प न हो ऐसा करने के लिए)।

Answer 1

शुरुआत के लिए, मैं cplusplus.com से प्राप्त किसी भी जानकारी से सावधान रहूंगा; साइट पर कुछ त्रुटियों के लिए जाना जाता है।

cppreference.com पर जाकर, हम पाते हैं कि जटिलता निरंतर निरंतर समय है। इसका मतलब यह है कि एन erase संचालन के किसी भी अनुक्रम में समय ओ (एन) लेना चाहिए, भले ही एक व्यक्ति मिटाने के ऑपरेशन में समय (1) से अधिक समय लगे।

यह पता चला है कि लाल/काले पेड़ से डालने या हटाने के लिए आवश्यक समय निम्नानुसार गणना की जाती है: प्रत्येक प्रविष्टि या हटाने में नोड के लिए स्थिति खोजने के लिए समय O (लॉग n) लगता है, लेकिन फिर करता है तत्व को सम्मिलित करने या हटाने के लिए केवल amortized ओ (1) काम करते हैं। इसका मतलब यह है कि लाल/काले पेड़ से नोड डालने या हटाने से किए गए काम पर पेड़ को पुनर्व्यवस्थित करने के लिए आवश्यक काम के बजाय, जहां नोड जाता है, यह पता लगाने के लिए आवश्यक काम से प्रभुत्व होता है। नतीजतन, यदि आपके पास पहले से ही लाल/काले पेड़ में एक सूचक है और उस तत्व को हटाना चाहते हैं, तो आपको तत्व को हटाने के लिए केवल एम (1) काम करना होगा। प्रत्येक व्यक्ति को हटाने में थोड़ा समय लग सकता है (अधिकतर ओ (लॉग एन) पर), लेकिन एन परिचालनों की एक धारा में कुल काम किया जाता है ओ (एन)।

ध्यान दें कि मानक को std::map लाल/काले पेड़ का उपयोग करने की आवश्यकता नहीं है। यह किसी अन्य प्रकार की डेटा संरचना का उपयोग कर सकता है (कहें, splay tree, scapegoat tree, या निर्धारक skiplist) जो इस समय जटिलता की भी गारंटी देता है। दिलचस्प बात यह है कि, सभी संतुलित द्विआधारी खोज वृक्ष संरचनाएं अमूर्त ओ (1) हटाने का समर्थन नहीं कर सकती हैं। AVL tree, उदाहरण के लिए, इस गारंटी नहीं है।

आशा है कि इससे मदद मिलती है!

Answer 2

यदि आप तत्व को हटाने के लिए मानचित्र पर एक पुनरावर्तक पास करते हैं, तो यह http://www.cplusplus.com/reference/map/map/erase/ के अनुसार निरंतर समय को निरस्त कर देता है।

अमोरिज्ड निरंतर समय का अर्थ है कि "यदि आप कई संचालन करते हैं तो प्रति ऑपरेशन औसत समय लिया जाता है"। इसलिए, कुछ ऑपरेशन हो सकते हैं जो निरंतर समय से अधिक समय लेते हैं, लेकिन यदि आप एक ही ऑपरेशन करते हैं तो कई बार, यह निरंतर निरंतर होता है।