सी ++ मल्टीमैप इटरेटर अमान्यता

Question

मैं यह पता लगाने की कोशिश कर रहा हूं कि std::multimap इटरेटर कैसे काम करते हैं, इसलिए मैंने एक साधारण उदाहरण बनाया है जो मेरी समस्या का पदार्थ दिखाता है। अगर असंगत मामला 1 है, तो मैं उम्मीद करता हूं कि इटेटरेटर कुंजी 1 के साथ पहले तत्व को इंगित करे, लेकिन हकीकत में यह कुंजी 0 से जुड़े सभी मानों को प्रिंट करता है (जैसे कुछ भी मिटा नहीं गया था) और कभी-कभी यह क्रैश हो जाता है, संभवतः क्योंकि इटरेटर अमान्य है। हालांकि अगर असम्भवता मामला 2 है, तो कुंजी 1 के साथ सभी मान ठीक से हटा दिए जाते हैं।

क्या यह जानने का कोई तरीका है कि multimap के बाद एरर के बाद अगला मान्य इटरेटर क्या है? (उदाहरण के लिए std::vector.erase(...) रिटर्न एक)

std::multimap<int, int> m; 

for(int j=0; j<3; ++j) { 
    for(int i=0; i<5; ++i) { 
     m.insert(std::make_pair(j, i)); 
    } 
} 

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

Answer 1

समस्या

के कारण जब आप कुंजी 0 साथ एक तत्व पर आप उदाहरण में m.erase(0) फोन, it अंक - तो it अवैध है। m.erase(1) काम करता है, क्योंकि जब इसे पहली बार कहा जाता है, it कुंजी 1 के साथ किसी तत्व को इंगित नहीं कर रहा है, इसलिए यह प्रभावित नहीं होता है। बाद में पुनरावृत्तियों में, 1 कुंजी वाले कोई तत्व नहीं रहते हैं, इसलिए कुछ भी नहीं हटाया जाता है, और कोई इटरेटर प्रभावित नहीं होता है।

समाधान

multimap एक erase -method कि अगले वैध इटरेटर रिटर्न भी नहीं है। एक विकल्प हटाने के बाद it = m.upper_bound(deleted_key); पर कॉल करना है। यह लॉगरिदमिक है, हालांकि, जो आपके परिदृश्य के लिए बहुत धीमा हो सकता है (erase(x) और upper_bound दो लॉगरिदमिक ऑपरेशंस होंगे)।

मान लिया जाये कि क्या आप कुछ इस तरह कर सकता है कुंजी अपने इटरेटर वर्तमान की ओर इशारा करते है को मिटाना चाहते हैं, (अन्यथा, erase ठीक, निश्चित रूप से है, का परीक्षण नहीं):

std::multimap<int, int>::iterator interval_start = m.begin(); 
for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end(); ++it) { 
    if(interval_start->first < it->first) // new interval starts here 
     interval_start == it; 
    if((*it).second == 3) { 
     std::multimap<int, int>::iterator interval_end = it; 
     while((interval_end != m.end()) && (interval_end->first == it->first)) { 
      ++interval_end; // search for end of interval - O(n) 
     } 
     m.erase(interval_start, interval_end); // erase interval - amortized O(1) 
     it = interval_end; // set it to first iterator that was not erased 
     interval_start = interval_end; // remember start of new interval 
    } 
} 

यह एक रैखिक आपरेशन का उपयोग करता है , बाकी सभी स्थिर समय हैं। यदि आपका नक्शा बहुत बड़ा है, और आपके पास केवल समान कुंजी वाले कुछ आइटम हैं, तो यह संभवतः तेज़ होगा। हालांकि, यदि आपके पास समान कुंजी के साथ कई आइटम हैं, तो अंतराल के अंत की खोज करते समय upper_bound (O(log n)O(n) के बजाय O(log n) का उपयोग करके संभवतः बेहतर किया जाता है)।

Answer 2

पहले जवाब

std::multimap<int, int> m; 
// ^^^^^^^^ 
std::map<int, int>::iterator it=m.begin(); 
// ^^^ 

हम ....

दूसरा जवाब है, पुन: संपादित प्रश्न

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    .... stuff .... 
     m.erase(1); // container mutation 
    .... stuff .... 
} 

अत्यंत सावधान रहें जब आप एक कंटेनर (किसी भी कंटेनर) को म्यूट कर रहे होते हैं, जब आप इसे चालू करते हैं, तो आप आप जिस इटरेटर पर निर्भर करते हैं उसे अमान्य कर सकते हैं।

तथाकथित "नोड आधारित कंटेनर" (list, set, map ...) सबसे मजबूत कंटेनर WRT इटरेटर अमान्यकरण हैं: वे केवल (नष्ट तत्वों को iterators को अमान्य कर वहाँ के लिए इन iterators नहीं हो कोई रास्ता नहीं है अवैध)।

इस मामले में आपको यह जांचना चाहिए कि जिस तत्व को आप हटाने वाले हैं, वह वास्तव में *it नहीं है।

मुझे पूरा यकीन नहीं है कि आप वास्तव में अपने लूप के साथ क्या करने की कोशिश कर रहे हैं।

Answer 3

जब आप इटेटरेटर मिटाते हैं तो अमान्य हो जाता है। इसके बजाय अगला तत्व याद रखें, फिर मिटाएं:

std::map<int,int>::iterator next = m + 1; 
m.erase 
m = next; 

Answer 4

अपना कोड देखने से, मुझे लगता है कि आपकी ++ समस्या उत्पन्न कर रही है। आप इसे उस स्थान पर असाइन कर रहे हैं जो हटा दिया गया हो सकता है। यदि स्टेटमेंट और टेस्ट के बाद इसे अंत में ले जाएं। जैसे इतना:

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
    ++it; 
} 

Answer 5

(संपादित)

for(std::multimap<int, int>::iterator it=m.begin(); it!=m.end();) { 
    printf("%d %d\n", (*it).first, (*it).second); 
    ++it; 
    if((*it).second == 3) { 
     //m.erase(0);  //case 1 
     m.erase(1);  //case 2 
    } 
} 

m.erase कि multimap की सामग्रियों (पहले से ही एक और जवाब में कवर) पर निर्भर करता है हो सकता है की वजह से it इटरेटर के अमान्यकरण के अलावा वहाँ हमेशा समस्या यह है कि आप भिन्नता है m.end() आपके for लूप के अंतिम पुनरावृत्ति पर इटरेटर जब आप if((*it).second == 3) करते हैं तो प्रत्येक बार जब आप अपना प्रोग्राम चलाते हैं।

मैं डीबग बिल्ड के साथ चलाने और डीबग करने का सुझाव देता हूं। मुझे पूरा यकीन है कि प्रत्येक सीन मानक लाइब्रेरी कार्यान्वयन में end() डिफ्रेंसिंग का पता लगाने के लिए जोर दिया जाना चाहिए।

Answer 6

ऊपर से ऊपर कुछ लोगों ने जवाब दिया है कि आप आग से खेल रहे हैं।

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