std :: नक्शा और पहले से डाले गए डेटा का व्यवहार

Question

क्या std::map नए डेटा डालने पर मान के आसपास पहले से डाला गया है?

Answer 1

नक्शा एक पेड़ के रूप में लागू किया गया है, और जब आप एक नया तत्व डालते हैं, तो पेड़ को पुन: संतुलित करने की आवश्यकता हो सकती है।

यह पेड़ में तत्वों के किसी भी इटरेटर या संदर्भ को अमान्य करता है। यह संतुलन पॉइंटर्स के हेरफेर के माध्यम से किया जाता है, इसलिए आपके पास चिंता करने की कोई बात नहीं है; नोड खुद ही रहते हैं।

संतुलन में नोड्स को बताकर पेड़ की संरचना को बदलना शामिल है, जो उनके बच्चे, माता-पिता और भाई बहन फिर से असाइन करने वाले पॉइंटर्स के माध्यम से होते हैं, लेकिन यह एक कार्यान्वयन विस्तार है। तार्किक रूप से कुछ भी नहीं बदला है।

Answer 2

मानक एसटीएल के विशिष्ट कार्यान्वयन, केवल व्यवहार और रनटाइम विशेषताओं को अनिवार्य नहीं करता है। उस ने कहा, एक स्किप सूची या पेड़ std :: मानचित्र का एक बहुत ही संभावित कार्यान्वयन है, इसलिए लिंक अपडेट हो जाएंगे, और सापेक्ष आदेश बदल जाएगा, लेकिन वास्तविक डेटा चारों ओर घूमने वाला नहीं है।

template <class T> 
struct Node 
{ 
    Node* mPrevious; 
    Node* mNext; 
    T mValue; 
}; 

जब दो मौजूदा बीच एक नए नोड डालने, तुम सब करने की ज़रूरत कुछ rewiring है:

Answer 3

दोगुना लिंक्ड सूची में एक ठेठ नोड पर विचार करें।

void insert(Node* target, Node* newNode) 
{ 
    target->mPrevious->mNext = newNode; 
    target->mPrevious = newNode; 

    newNode->mPrevious = target->mPrevious; 
    newNode->mNext = target; 
} 

व्यवहार के साथ इसी तरह की है एक std::map (या std::set, std::multimap या std::multiset बाद से वे सभी सामान्य रूप में एक ही अंतर्निहित संरचना का उपयोग करके लागू)।

इसका मतलब है कि मौजूदा तत्व को इंगित करने वाला कोई भी इटरेटर भी वैध रहता है। मैं मौजूदा तत्व बिट पर जोर देता हूं। end द्वारा लौटाए गए इटरेटर को सम्मिलन या हटाने के बाद पुनः संयोजित किया जाना चाहिए और बेहतर कैश नहीं किया जाना चाहिए।

Answer 4

सी ++ मानक std::map के कार्यान्वयन को केवल इसके व्यवहार और दक्षता को लागू नहीं करता है। कार्यान्वयन के आसपास वस्तुओं को स्थानांतरित करने की अनुमति है; हालांकि, यह अक्षम हो सकता है।

अधिकांश std::map कंटेनरों को लिंक के साथ एक पेड़ डेटा संरचना का उपयोग करके कार्यान्वित किया जाता है। आइटम डालने या पुन: व्यवस्थित करते समय, लिंक बदल जाते हैं, लेकिन डेटा स्थानांतरित नहीं होता है। चलती वस्तुओं std::map के निष्पादन समय को धीमा कर देगी।