C++ multimap iterator invalidation

Question

Tôi đang cố gắng tìm ra cách hoạt động của các trình vòng lặp std::multimap, do đó tôi đã tạo ra một ví dụ đơn giản cho thấy vấn đề của vấn đề của tôi. Nếu trường hợp uncomment 1, tôi mong đợi iterator trỏ đến phần tử đầu tiên với khóa 1, nhưng trên thực tế nó in tất cả các giá trị liên quan đến khóa 0 (như không có gì bị xóa) và đôi khi nó bị treo, có thể do trình vòng lặp không hợp lệ. Tuy nhiên, nếu trường hợp bỏ ghi chú 2, tất cả các giá trị bằng khóa 1 sẽ được xóa đúng cách.

Có cách nào để biết trình lặp hợp lệ tiếp theo cho số multimap sau khi xóa không? (ví dụ std::vector.erase(...) lợi nhuận một)

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

Nguyên nhân của vấn đề

Khi bạn gọi m.erase(0) trong bạn Ví dụ, it điểm tại một phần tử với chìa khóa 0 - vì vậy it không còn giá trị. m.erase(1) hoạt động, bởi vì khi nó được gọi là lần đầu tiên, it không trỏ đến một phần tử có khóa 1, vì vậy nó không bị ảnh hưởng. Trong các lần lặp lại sau, không có phần tử nào có khóa 1 vẫn giữ nguyên, vì vậy không có gì bị xóa và không có trình lặp nào bị ảnh hưởng.

Giải pháp

multimap không có một -method erase mà trả về iterator hợp lệ tiếp theo. Một cách khác là gọi it = m.upper_bound(deleted_key); sau khi xóa. Tuy nhiên, đây là lôgarit, có thể quá chậm đối với kịch bản của bạn (erase(x) và upper_bound sẽ là hai hoạt động lôgarit).

Giả sử bạn muốn xóa phím iterator của bạn hiện đang trỏ đến, bạn có thể làm một cái gì đó như thế này (nếu không, erase là tốt, tất nhiên, không kiểm tra):

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

này sử dụng hoạt động một tuyến tính , tất cả phần còn lại là thời gian không đổi. Nếu bản đồ của bạn rất lớn và bạn chỉ có vài mục có khóa bằng nhau, điều này có thể sẽ nhanh hơn. Tuy nhiên, nếu bạn có nhiều mục có khóa bằng nhau, việc tìm kiếm kết thúc khoảng thời gian có thể được thực hiện tốt hơn bằng cách sử dụng upper_bound (O(log n) thay vì O(n) khi tìm kiếm vào cuối khoảng thời gian).

Answer 2

Trước câu trả lời

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

Hum ....

câu trả lời Thứ hai, tái: thay đổi nội dung câu hỏi

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

Be cực kỳ cẩn thận khi bạn đang biến đổi một vùng chứa (bất kỳ vùng chứa nào) khi bạn đang lặp lại nó, như bạn có thể làm mất hiệu lực một trình lặp mà bạn phụ thuộc vào.

Cái gọi là "container nút dựa trên" (list, set, map ...) là mạnh mẽ nhất WRT chứa iterator huỷ bỏ hiệu lực: họ chỉ làm mất hiệu lực lặp đến các yếu tố xóa (không có cách nào cho các vòng lặp không không hợp lệ).

Trong trường hợp này, bạn nên kiểm tra xem yếu tố bạn sắp xóa không thực sự là *it.

Tôi không hoàn toàn chắc chắn những gì bạn đang cố gắng thực sự làm với vòng lặp của bạn.

Answer 3

khi bạn xóa trình vòng lặp không hợp lệ. thay vào đó hãy nhớ yếu tố tiếp theo sau đó xóa:

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

Answer 4

Từ khi nhìn vào mã của bạn, tôi nghĩ rằng bạn đang gây ra sự cố. Bạn đang gán nó cho một địa điểm có thể đã bị xóa. di chuyển nó đến cuối, sau câu lệnh if và test. như vậy:

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

(Edited)

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

Ngoài chấm dứt hiệu lực it iterator do m.erase có thể xảy ra tùy thuộc vào nội dung của multimap (đã được đề cập trong câu trả lời khác) luôn là vấn đề mà bạn dereference m.end() trình lặp trên vòng lặp cuối cùng của vòng lặp for khi bạn thực hiện if((*it).second == 3) mỗi khi bạn chạy chương trình của mình.

Tôi đề xuất chạy và gỡ lỗi với các bản dựng gỡ lỗi. Tôi gần như chắc chắn rằng tất cả các thư viện chuẩn thực thi sane nên chứa khẳng định để phát hiện end() dereferencing.

Answer 6

Một số người ở trên đã trả lời rằng bạn đang chơi với lửa.

Ngoài ra, tôi nghĩ rằng bạn đang quên rằng multimap được đặt hàng bản đồ, vì vậy bạn đang lặp lại từ các phím nhỏ nhất đến các phím lớn nhất. Vì vậy, trong trường hợp đầu tiên bạn gỡ bỏ các phím sau khi in một số trong số chúng, nhưng trong trường hợp thứ hai, bạn sẽ loại bỏ ngay trước khi đi đến chúng.