Phần thứ hai của bản đồ là <..,..> có ổn định không?

Question

Nếu chúng tôi có một map <int, vector<int> > được di chuyển khi cây màu đỏ đen của bản đồ thay đổi hoặc nó lưu trữ con trỏ đến vector s hoặc một cái gì đó tương tự và không di chuyển chúng (khác làm việc với bản đồ sẽ không là O (lg n) nữa ví dụ như nếu chúng ta push_back yếu tố để một số vector s)

Answer 1

Xem cái này: std::map, pointer to map key value, is this possible?

các thứ hai câu trả lời đầu:

Mục 23.1.2 # 8 (kết hợp con yêu cầu tainer):

"Thành viên chèn sẽ không ảnh hưởng đến tính hợp lệ của trình lặp và tham chiếu đến vùng chứa và thành viên xóa sẽ chỉ vô hiệu hóa vòng lặp và tham chiếu đến phần tử đã xóa."

Vì vậy, có lưu trữ con trỏ tới thành viên dữ liệu của phần tử bản đồ được đảm bảo hợp lệ, trừ khi bạn xóa yếu tố.

Vì vậy, nếu tham chiếu được giữ nguyên, dữ liệu không thể được sao chép vào một phần khác của bộ nhớ. Và nếu đúng như vậy, tôi không thấy điểm nào trong việc thực hiện bất kỳ bản sao nào cả ...

Answer 2

Không, các vectơ sẽ không được di chuyển xung quanh. Các thao tác của cây chỉ sắp xếp lại con trỏ giữa các nút. Chúng không di chuyển các nút hoặc nội dung của chúng trong bộ nhớ.

Answer 3

Tôi tin rằng C++ 03 không đảm bảo tính ổn định của dữ liệu trong bộ nhớ và đây sẽ là chi tiết triển khai (và thực sự không phải thứ bạn có thể giả định một cách an toàn mà không kiểm tra).

Lưu ý rằng việc bảo tồn lặp vào bản đồ và vị trí của vector thực tế trong bộ nhớ là điều hoàn toàn khác nhau. Tính hợp lệ của các trình vòng lặp được xác định rõ ràng (cả khi chúng hợp lệ và khi chúng không) trong đặc tả C++, nhưng hành vi bên trong thực tế của cây không phải là.

Điều đó nói rằng, bất kỳ trình biên dịch tốt nào (cho bản phát hành/bật tối ưu hóa) sẽ tối ưu hóa việc triển khai để không thực sự sao chép vectơ khi nó được di chuyển xung quanh cây và triển khai C++ 11 của std::map sẽ sử dụng ngữ nghĩa di chuyển để đảm bảo hành vi đó.

Điều bạn không thể giả định là các con trỏ chỉ nội bộ được di chuyển.