जांच करें कि सी ++ में अन्य नक्शा

Question

से सभी कुंजियां मौजूद मैं प्रकार के, सी ++ में दो नक्शे इस्तेमाल की योजना बना रहा हूँ: std::map<char, Node>, जहां Node एक कस्टम वर्ग है। मान लीजिए कि मेरे पास दो प्रकार हैं, m1 और m2 उपरोक्त प्रकार के, मैं यह जानना चाहता हूं कि m1 में कुंजी m2 में मौजूद हैं। दूसरे शब्दों में, मैं सत्यापित करना चाहता हूं कि m1 और m2 की चाबियों के सेट का चौराहे m2 की कुंजी के सेट जैसा ही है।

मैं m2 में सभी चाबियाँ पर पुनरावृति सकता है और एक find() या count()m1 पर करते हैं, लेकिन यह एक बेकार की तरह प्रतीत होता है और शायद धीमी गति से होगा। मैं यह इसलिए कहता हूं क्योंकि std::map में क्रमबद्ध क्रम में कुंजी को बाइनरी सर्च पेड़ के रूप में संग्रहीत किया जाता है, और इसलिए प्रत्येक खोज/गिनती ओ (लॉगन) लेती है, और m2 में अगली कुंजी के लिए, m1 की चाबियों में एक ही पथ शुरुआत से गुजरना होगा।

मैं एसटीएल के लिए नया हूं, इसलिए कृपया मेरी अज्ञानता को क्षमा करें जो कुछ ऐसा लगता है जो आसानी से किया जा सकता है। साथ ही, कुछ सरल उदाहरण कोड स्निपेट या कोड स्निपेट के लिंक बेहतर समझने में बहुत उपयोगी होंगे। मैं बढ़ावा सहित गैर-मानक पुस्तकालयों का उपयोग नहीं कर सकता।

अग्रिम धन्यवाद!

Answer 1

के बाद से एक map की चाबी हल कर रहे हैं, तो आप एक ही समय में उन दोनों के माध्यम से पुनरावृति और एक दूसरे के लिए कुंजी तुलना कर सकते हैं। यदि key(m1) < key(m2), एम 1 के लिए इटरेटर को बढ़ाएं; अगर key(m2) < key(m1) तो एम 2 में एक कुंजी नहीं है जो एम 1 में नहीं है।

यह ओ (एन) है।