मिटाएं तत्व एक ही वेक्टर

Question

संभव डुप्लिकेट पुनरावृत्ति करते हुए:
Erasing from a std::vector while doing a for each?

मैं इस एल्गोरिथ्म के अनुसार रंग vertice लागू करने के लिए कोशिश कर रहा हूँ;

/* 
Given G=(V,E): 
Compute Degree(v) for all v in V. 
Set uncolored = V sorted in decreasing order of Degree(v). 
set currentColor = 0. 
while there are uncolored nodes: 
    set A=first element of uncolored 
    remove A from uncolored 
    set Color(A) = currentColor 
    set coloredWithCurrent = {A} 
    for each v in uncolored: 
     if v is not adjacent to anything in coloredWithCurrent: 
     set Color(v)=currentColor. 
     add v to currentColor. 
     remove v from uncolored. 
     end if 
    end for 
    currentColor = currentColor + 1. 
end while 
*/ 

मुझे समझ में नहीं आता "वर्तमान रंग में v जोड़ें।" लाइन लेकिन मुझे लगता है, इसका मतलब है वर्तमान में vol को voling। इसलिए "सेट" क्या है? वैसे भी समस्या यह है कि वेक्टर में तत्व को मिटा रहा है। यह कोड है।

vector<struct Uncolored> uc; 
    vector<struct Colored> c; 

    int currentColor = 0; 
    struct Colored A; 
    struct Colored B; 

    vector<struct Uncolored>::iterator it; 
    vector<struct Uncolored>::iterator it2; 
    vector<struct Colored>::iterator it3; 

    for(it=uc.begin();it<uc.end();it++){ 

     A.id = (*it).id;   
     uc.erase(uc.begin()); 
     A.color = currentColor; 
     c.push_back(A); 

     for(it2=uc.begin();it2<uc.end();it2++) { 
      it3=c.begin(); 
      while(it3 != c.end()) { 
       if(adjacencyMatris[(*it2).id][(*it3).id] == 0) { 
        B.id = (*it2).id;  
        it2 = uc.erase(it2); 
        B.color = currentColor; 
        c.push_back(B); 
       } 
       it3++; 
      } 
     } 
     currentColor = currentColor + 1; 
    } 

मुझे लगता है कि it2 = uc.erase(it2); लाइन पहले से ही सामान्य उपयोग है लेकिन यह रन टाइम त्रुटि देता है।

Answer 1

लाइन में:

it2 = uc.erase(it2); 

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

for(it2 = uc.begin(); it2 != uc.end();) 
{ 
    ... 
    if(...) 
    { 
     it2 = uc.erase(it2); 
    } 
    else 
    { 
     ++it2; 
    } 
    ... 
} 

आप इस here के बारे में अधिक पढ़ सकते हैं: प्रस्तावित remove-erase idiom के लिए एक वैकल्पिक एक सरल चाल है।

संपादित करें: अपनी टिप्पणी के बारे में, आप जानकारी पारित करने के लिए है कि क्या एक तत्व मिटा दिया गया है या नहीं एक ध्वज का उपयोग कर सकते हैं, और आप यह जांच कर सकते हैं जब आप भीतरी पाश से बाहर निकलना:

for(it2=uc.begin(); it2 != uc.end();) 
{ 
    bool bErased = false; 

    for(it3 = c.begin(); it3 != c.end(); ++it3) 
    { 
     if(adjacencyMatris[(*it2).id][(*it3).id] == 0) 
     { 
     B.id = (*it2).id; 
     it2 = uc.erase(it2); 
     bErased = true; 
     B.color = currentColor; 
     c.push_back(B); 
     break; 
     } 
    } 

    if(!bErased) 
     ++it2; 
} 

uc से तत्व को मिटाने के बाद आपको आंतरिक लूप से तोड़ना होगा। बाहरी लूप के अगले पुनरावृत्ति में आप uc में एक वैध इटरेटर के माध्यम से अगले तत्व तक पहुंच पाएंगे।

Answer 2

vector::erase()invalidate iterators वेक्टर को इंगित कर सकते हैं।

यह सभी इटरेटर और स्थिति (या पहले) और इसके बाद के तत्वों के संदर्भों को अमान्य करता है।

आप (यह सिर्फ मिट एक के बाद तत्व को इंगित करेंगे) और कहा कि इसके परिणामस्वरूप का उपयोग इटरेटर को erase का परिणाम जोड़ने की जरूरत है। ध्यान दें कि

for(it=uc.begin();it<uc.end();++it){ 
    A.id = (*it).id;   
    uc.erase(uc.begin()); 
    ... 
} 

में इटरेटर it के बाद uc.erase, तो बाद में ++ और उपयोग रनटाइम त्रुटि हो सकती है मान्य नहीं है।

इसी प्रकार, भले ही आप it2 पर मिटाने के परिणाम को असाइन करते हैं, तो कॉल it को अमान्य कर सकता है, जो बदला नहीं गया है।

आपकी सर्वश्रेष्ठ शर्त या तो प्रत्येक erase() के बाद शुरुआत से अपने एल्गोरिदम को फिर से शुरू करने के लिए है, या यदि आप इसे बदल सकते हैं ताकि यह erase द्वारा लौटाए गए इटरेटर से जारी रह सके, तो कुछ दक्षता प्राप्त करने के लिए ऐसा करें।

Answer 3

iterator प्रकारों के साथ काम करने के बजाय, vector में एक इंडेक्स स्टोर करें। जब आपको एक इटरेटर की आवश्यकता होती है - शायद erase में गुजरने के लिए - आप एक इटरेटर उत्पन्न करने के लिए begin() + myIndex कह सकते हैं।

यह लूप को और अधिक परिचित बनाता है, उदा।

for(ind=0; ind < uc.size(); ind++) { 

Answer 4

क्योंकि it2 = uc.erase(it2); पिछले हटा तत्व निम्नलिखित iterator देता है, तो for(it2=uc.begin();it2<uc.end();it2++) में it2++ पिछले तत्व से परे चला जाता है आप रनटाइम त्रुटि मिल गया है।

if(adjacencyMatris[(*it2).id][(*it3).id] == 0) { 
    B.id = (*it2).id;  
    uc.erase(it2); 
    B.color = currentColor; 
    c.push_back(B); 
    break; 
}