Làm việc của std :: map <t1, t2> :: xóa (vị trí lặp)?

Question

Tôi đọc trên cplusplus.com rằng thao tác xóa một phần tử trong một std::map bằng cách chuyển qua trình vòng lặp làm đối số là thời gian không đổi.

Nếu tôi không sai (và vui lòng sửa tôi nếu tôi) các trình vòng lặp về cơ bản là con trỏ đến các phần tử trong bản đồ với toán tử ++ chỉ trả về người kế thừa theo thứ tự của phần tử hiện tại tôi đoán đó là cách kết quả được sắp xếp đạt được trên quá trình truyền tải của std::map. Bây giờ nếu bản đồ là một cây đen đỏ, không nên xóa một yếu tố (sử dụng địa chỉ của nó) là hoạt động thời gian logarit, tôi tự hỏi làm thế nào họ làm điều đó trong thời gian liên tục (trừ khi có một sự thay thế lãng phí bộ nhớ rất cao?). Để làm việc đó).

Answer 1

Để bắt đầu, tôi sẽ cảnh giác với bất kỳ thông tin nào bạn nhận được từ cplusplus.com; trang web được biết là có một số lỗi trên đó.

Thăm cppreference.com, chúng tôi nhận được rằng độ phức tạp là khấu hao thời gian không đổi. Điều này có nghĩa là bất kỳ trình tự nào của các hoạt động n erase sẽ mất thời gian O (n), ngay cả khi thao tác xóa riêng lẻ mất thời gian lớn hơn O (1).

Nó chỉ ra rằng thời gian cần thiết để chèn hoặc xóa từ một cây đỏ/đen kết thúc được tính như sau: mỗi lần chèn hoặc xóa mất thời gian O (log n) để tìm vị trí cho nút, nhưng sau đó chỉ amortized O (1) làm việc để chèn hoặc loại bỏ các phần tử. Điều này có nghĩa rằng công việc thực hiện chèn hoặc xóa một nút từ một cây đỏ/đen bị chi phối bởi công việc cần thiết để tìm ra nơi mà nút đi, chứ không phải là công việc cần thiết để cân bằng lại cây sau đó. Kết quả là, nếu bạn đã có một con trỏ vào một cây đỏ/đen và muốn xóa phần tử đó, bạn chỉ phải làm phân bổ công việc O (1) để xóa phần tử. Mỗi lần xóa cá nhân có thể mất một chút thời gian (tối đa là O (log n)), nhưng trên một luồng các phép toán n, tổng công việc được thực hiện tối đa là O (n).

Lưu ý rằng tiêu chuẩn không yêu cầu rằng std::map sử dụng cây đỏ/đen. Nó có thể sử dụng một loại cấu trúc dữ liệu khác (ví dụ: splay tree, scapegoat tree hoặc xác định skiplist) cũng đảm bảo độ phức tạp về thời gian này. Thật thú vị, mặc dù, không phải tất cả các cấu trúc cây tìm kiếm nhị phân cân bằng đều có thể hỗ trợ khấu hao O (1) bị phân bổ. Ví dụ: AVL tree không có bảo đảm này.

Hy vọng điều này sẽ hữu ích!

Answer 2

Nếu bạn vượt qua một trình vòng lặp để ánh xạ để loại bỏ phần tử, đó là thời gian cố định được phân bổ theo http://www.cplusplus.com/reference/map/map/erase/.

Thời gian cố định được phân bổ có nghĩa là "thời gian trung bình được thực hiện cho mỗi hoạt động, nếu bạn thực hiện nhiều thao tác". Do đó, có thể có một số hoạt động mất nhiều thời gian hơn thời gian không đổi, nhưng nếu bạn thực hiện thao tác tương tự nhiều lần, thì đó là hằng số khấu hao.