Làm cách nào để ngăn chặn việc khôi phục std :: unordered_map trong khi xóa các phần tử?

Question

Tôi có một tiêu chuẩn :: unordered_map mà tôi sẽ loại bỏ các yếu tố từ thông qua lặp lại.

auto itr = myMap.begin(); 
while (itr != myMap.end()) { 
    if (/* removal condition */) { 
     itr = myMap.erase(itr); 
    } else { 
     ++itr; 
    } 
} 

Tôi muốn ngăn bản đồ thực hiện bất kỳ hoạt động đắt tiền nào cho đến khi tôi xóa xong tất cả các yếu tố cần xóa. Tôi có một mối quan tâm hợp lệ? Tôi có hiểu lầm về cách hoạt động của bộ nhớ trong không?

Answer 1

Các vật chứa không có thứ tự bị cấm phục hồi trong một số erase:

[unord.req]/P14:

Các erase thành viên có trách nhiệm làm mất hiệu lực chỉ lặp và tài liệu tham khảo để các yếu tố xoá hoàn toàn, và giữ gìn trật tự tương đối của các yếu tố không được xoá hoàn toàn.

[unord.req]/p9:

rehashing làm mất hiệu lực lặp, thay đổi đặt hàng giữa các yếu tố, và ...

Mã của bạn là tốt như vậy.

Answer 2

Theo như tôi có thể nói, std::unordered_map được phép rehash trên erase(itr):

C++ 11 Bảng 103 - Yêu cầu chứa kết Unordered

a.erase(q)

Xóa phần tử chỉ đến bởi q. Giá trị trả lại là bộ chuyển đổi ngay sau q trước khi xóa.

trường hợp trung bình O(1), tồi tệ nhất trường hợp O(a.size())

Nó sẽ do đó dường như rằng bạn có một mối quan tâm hợp lệ. Để giải quyết vấn đề này, tôi có thể đề xuất một số con đường:

1. Đảm bảo đây là vấn đề thực tế chứ không phải giả thuyết. Hồ sơ ứng dụng, xem mã nguồn cho thư viện C++ của bạn, v.v.
2. Nếu đó là vấn đề thực tế, hãy xem xét sử dụng vùng chứa khác hoặc thuật toán khác.
3. Hãy xem xét chỉ đơn giản là đánh dấu các yếu tố để xóa thông qua cờ boolean liên kết với từng phần tử và quét các phần tử đã xóa theo thời gian, do đó phân bổ chi phí.
4. Cân nhắc thử nghiệm với hệ số tải, như được đề xuất bởi @amit trong các nhận xét. Mặc dù vùng chứa vẫn được phép lấy thời gian để xóa các phần tử O(a.size()), một yếu tố tải khác có thể ảnh hưởng đến hiệu suất thực tế của ứng dụng của bạn.

Answer 3

Tôi không chắc chắn nó sẽ làm việc, tôi không tìm thấy một xác nhận cho nó trong tài liệu - nhưng nếu unordered_map được xào xáo lại theo băm cổ điển cấu trúc bảng dữ liệu, bạn có thể set the max_load_factor đến một rất cao giá trị và thiết lập lại nó trở lại bình thường khi bạn đang thực hiện (mà sẽ kích hoạt một rehash) (hoặc để dự đoán giá trị nếu bạn có thể dự đoán có bao nhiêu yếu tố sẽ được gỡ bỏ).

Trong điều khoản của bảng băm cổ điển, nó sẽ hoạt động kể từ khi khởi động lại khi giảm bảng xảy ra khi kích thước thấp hơn 1/max_load_factor.

(không chắc chắn đó là trường hợp trong C++, nhưng tôi cho rằng nó đáng để thử, vì nó thực sự dễ thực hiện).