सी ++ एसटीएल unordered_map कार्यान्वयन, संदर्भ वैधता

Question

std::map और std::tr1::unordered_map दोनों के लिए, मैं मानक से देखते हैं कि:

unordered_map कंटेनर में तत्वों के संदर्भ, सभी मामलों में वैध रहेगा एक मिलावत के बाद भी।

वे यह कैसे कर रहे हैं (कार्यान्वयन-वार)? क्या वे सभी प्रविष्टियों को एक प्रकार की लिंक्ड सूची के रूप में बनाए रखते हैं और फिर हैश-टेबल तत्वों को पॉइंटर्स स्टोर करता है?

Answer 1

हां, लिंक्ड सूचियां शामिल हैं, हालांकि आपके सुझाव के अनुसार काफी कुछ नहीं है।

2011 मानक कहता है (23.2.5 पैरा 8), "एक असाधारण सहयोगी कंटेनर के तत्व बाल्टी में व्यवस्थित होते हैं। उसी हैश कोड के साथ एक ही बाल्टी में कुंजी दिखाई देती है।"

प्रत्येक बाल्टी के भीतर, तत्व एक लिंक्ड सूची में हैं (प्रत्येक बाल्टी के लिए एक अलग सूची, पूरे कंटेनर के लिए एक बड़ी सूची नहीं)। जब कंटेनर को फिर से हटाया जाता है, तो तत्वों को नई बाल्टी को सौंपा जाएगा, लेकिन प्रत्येक तत्व के पॉइंटर्स वैध रहते हैं। प्रत्येक नई बाल्टी में लिंक्ड सूची पॉइंटर्स से मौजूदा तत्वों तक इकट्ठी होती है जो उस बाल्टी में समाप्त होती हैं।

इटरेटर को रीहाश द्वारा अमान्य कर दिया जाता है, क्योंकि एक इटरेटर को तत्व और उसकी बाल्टी दोनों को पॉइंटर्स रखने की आवश्यकता होती है (इसलिए इसे एक बाल्टी के अंतिम तत्व से अगले के पहले तत्व में ले जाया जा सकता है)। तत्व पॉइंटर मान्य रहता है, इसलिए किसी तत्व के मौजूदा पॉइंटर्स और संदर्भ अभी भी मान्य हैं, लेकिन बाल्टी पॉइंटर को रीहाश द्वारा अमान्य किया जाता है, इसलिए इटेटरेटर उपयोग योग्य नहीं है।

(यही कारण है कि अनियंत्रित कंटेनर केवल ऑर्डर करने वाले सहयोगी कंटेनरों द्वारा समर्थित बिडरेक्शनल इटरेटर्स की बजाय इटरेटर्स का समर्थन करते हैं। प्रत्येक बाल्टी के तत्व एक सिंगल लिंक्ड सूची में हैं, इसलिए आप उनके माध्यम से पीछे नहीं जा सकते हैं।)