std :: vector iterator invalidation

Question

Đã có một vài câu hỏi liên quan đến vấn đề này trước đây; sự hiểu biết của tôi là việc gọi std::vector::erase sẽ chỉ làm mất hiệu lực vòng lặp ở vị trí sau phần tử đã xóa. Tuy nhiên, sau khi xóa một phần tử, là iterator tại vị trí đó vẫn còn hợp lệ (cung cấp, tất nhiên, rằng nó không trỏ đến end() sau khi xóa)?

Sự hiểu biết của tôi về cách một vectơ được triển khai dường như cho thấy rằng trình vòng lặp có thể sử dụng được, nhưng tôi không hoàn toàn chắc chắn nếu nó có thể dẫn đến hành vi không xác định.

Ví dụ về những gì tôi đang nói đến, đoạn mã sau xóa tất cả các số nguyên lẻ khỏi một vectơ. Mã này có gây ra hành vi không xác định không?

typedef std::vector<int> vectype; 
vectype vec; 

for (int i = 0; i < 100; ++i) vec.push_back(i); 

vectype::iterator it = vec.begin(); 
while (it != vec.end()) { 
    if (*it % 2 == 1) vec.erase(it); 
    else ++it; 
} 

Mã chạy tốt trên máy tính của tôi, nhưng điều đó không thuyết phục tôi rằng nó hợp lệ.

Answer 1

sau khi xóa một phần tử, là iterator tại vị trí đó vẫn có giá trị

Không; tất cả các trình vòng lặp tại hoặc sau (các) trình vòng lặp được chuyển đến erase đều bị vô hiệu.

Tuy nhiên, erase trả về trình lặp mới trỏ đến phần tử ngay sau phần tử đã bị xóa (hoặc đến cuối nếu không có phần tử như vậy). Bạn có thể sử dụng trình lặp này để tiếp tục lặp lại.

---

Lưu ý rằng phương pháp đặc biệt này loại bỏ các yếu tố lẻ là khá hiệu quả: mỗi khi bạn loại bỏ một phần tử, tất cả các yếu tố sau nó phải được di chuyển một vị trí để bên trái trong vector (điều này là O (n)). Bạn có thể hoàn thành nhiệm vụ này hiệu quả hơn bằng cách sử dụng erase-remove idiom (O (n)). Bạn có thể tạo một is_odd ngữ:

bool is_odd(int x) { return (x % 2) == 1; } 

Sau đó, điều này có thể được chuyển tới remove_if:

vec.erase(std::remove_if(vec.begin(), vec.end(), is_odd), vec.end()); 

Answer 2

Hoặc:

class CIsOdd 
{ 
public: 
    bool operator()(const int& x) { return (x % 2) == 1; } 
}; 

vec.erase(std::remove_if(vec.begin(), vec.end(), CIsOdd()), vec.end());