yếu tố Erase trong vector trong khi lặp lại cùng một vector

Question

thể trùng lặp:
Erasing from a std::vector while doing a for each?

Tôi đang cố gắng để thực hiện vertice màu theo thuật toán này;

/* 
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 
*/ 

Tôi không hiểu "thêm v vào currentColor". dòng nhưng tôi nghĩ, nó có nghĩa là assing currentColor để v.Vì vậy, các "bộ" là gì? Dù sao vấn đề là xóa phần tử trong vector trong khi lặp lại nó. Đây là mã.

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; 
    } 

Tôi nghĩ rằng dòng it2 = uc.erase(it2); đã được sử dụng chung nhưng nó cho lỗi thời gian chạy.

Answer 1

Trong dòng:

it2 = uc.erase(it2); 

một yếu tố được trỏ bởi iterator it2 được lấy ra từ các vector, yếu tố này được chuyển trong bộ nhớ để lấp đầy khoảng trống đó mà làm mất hiệu lực it2. it2 nhận một giá trị mới và bây giờ trỏ đến phần tử đầu tiên sau phần tử đã xóa hoặc phần cuối của vectơ (nếu phần tử đã xóa là phần tử cuối cùng). Điều này có nghĩa là sau khi xóa một phần tử, bạn không nên tạm ứng it2. Một thay thế cho đề xuất remove-erase idiom là một thủ thuật đơn giản:

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

Bạn có thể đọc thêm về here này.

Edit: Về nhận xét của bạn, bạn có thể sử dụng một lá cờ để vượt qua các thông tin cho dù một yếu tố đã bị xóa hoặc không, và bạn có thể kiểm tra xem nó khi bạn thoát ra khỏi vòng lặp bên trong:

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; 
} 

Sau khi bạn đã xóa một phần tử từ uc, bạn cần phải ngắt khỏi vòng lặp bên trong. Trong lần lặp tiếp theo của vòng lặp bên ngoài, bạn sẽ có thể truy cập phần tử tiếp theo trong uc thông qua một trình lặp hợp lệ.

Answer 2

vector::erase() có thể invalidate iterators trỏ tới vectơ.

Điều này làm mất hiệu lực tất cả các trình vòng lặp và tham chiếu đến vị trí (hoặc thứ nhất) và các phần tử tiếp theo của nó.

Bạn cần thêm kết quả của erase vào trình vòng lặp (nó sẽ trỏ đến phần tử ngay sau lần xóa) và sử dụng kết quả đó. Lưu ý rằng trong

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

Các iterator it không hợp lệ sau uc.erase, ++ và sử dụng để sau này có thể gây ra lỗi runtime.

Tương tự, mặc dù bạn chỉ định kết quả xóa là it2, cuộc gọi có thể làm mất hiệu lực it, không thay đổi. Đặt cược tốt nhất của bạn là khởi động lại thuật toán ngay từ đầu sau mỗi erase() hoặc nếu bạn có thể thay đổi nó để nó có thể tiếp tục từ trình lặp được trả về erase, hãy làm điều đó để đạt được hiệu quả.

Answer 3

Thay vì làm việc với các loại iterator, hãy lưu chỉ mục vào vector. Khi bạn cần một trình lặp - có lẽ để chuyển vào erase - bạn có thể nói begin() + myIndex để tạo trình lặp.

Điều này cũng làm cho vòng lặp trông quen thuộc hơn, ví dụ:

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

Answer 4

Bạn đã có những lỗi runtime vì it2 = uc.erase(it2); trả về iterator sau các yếu tố loại bỏ cuối cùng, vì vậy it2++ trong for(it2=uc.begin();it2<uc.end();it2++) vượt xa những yếu tố cuối cùng.

Hãy thử thay đổi của bạn nếu trong:

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