C++: là std :: unordered_map được bảo đảm là dựa trên nút?

Question

Bố cục điển hình của std::unordered_map<K, V> là gì? Có phải các đối tượng K và V được lưu trữ trong chính các nhóm hay làm các con trỏ lưu trữ các nhóm đến các nút chứa các khóa và giá trị?

Tôi đang cố gắng tìm hiểu ý nghĩa hiệu suất của việc sử dụng std::unordered_map<K, V> so với std::unordered_map<K, V*>. Giả sử tôi chỉ bao giờ emplace và tìm kiếm các giá trị, là có bất kỳ lý do để thích thứ hai, ngay cả khi các giá trị khá lớn? Lý do duy nhất tôi có thể tưởng tượng là nếu các giá trị được lưu trữ trong dòng trong các thùng và cần phải được phân bổ lại mỗi khi vùng chứa được khôi phục.

Có điều gì trong tiêu chuẩn đảm bảo điều này sẽ không xảy ra không?

Answer 1

[unord.req]/8:

rehashing làm mất hiệu lực lặp, thay đổi đặt hàng giữa các yếu tố, và những thay đổi mà Xô yếu tố xuất hiện trong, nhưng không làm mất hiệu lực con trỏ hoặc tham chiếu đến các yếu tố.

Thực tế con trỏ và tham chiếu đến phần tử không bị vô hiệu hóa bằng cách khôi phục (hoặc chèn/xóa, xem/13) có nghĩa là chúng phải dựa trên nút.

C++ 17 thậm chí hiển thị các nút điều khiển nút để bạn có thể chuyển các nút giữa hai số unordered_map s.