std :: hash_set vs std :: unordered_set, chúng có giống nhau không?

Question

Tôi biết hash_set không chuẩn và unordered_set là tiêu chuẩn. Tuy nhiên, tôi tự hỏi, hiệu suất khôn ngoan, sự khác biệt giữa hai là gì? Tại sao chúng tồn tại riêng biệt?

Answer 1

Yêu cầu phức tạp cho các đối tượng unordered_ được đặt ra theo tiêu chuẩn C++ về cơ bản không để lại nhiều chỗ cho việc triển khai, mà phải là một số loại bảng băm. Tiêu chuẩn này được viết hoàn toàn nhận thức rằng các cấu trúc dữ liệu đó đã được triển khai bởi hầu hết các nhà cung cấp dưới dạng một phần mở rộng.

Nhà cung cấp trình biên dịch thường sẽ gọi các bộ chứa đó là "bản đồ băm" hoặc "bộ băm", đó là những gì bạn có thể đang đề cập đến (không có tiêu chuẩn là std::hash_set theo tiêu chuẩn). không gian tên, và tương tự cho các trình biên dịch khác).

Khi tiêu chuẩn mới được viết, tác giả muốn tránh nhầm lẫn với thư viện mở rộng hiện có, vì vậy họ đã đặt tên phản ánh tư duy điển hình của C++: nói nó là gì chứ không phải cách nó được triển khai. Các vùng chứa không có thứ tự là, tốt, không có thứ tự. Điều đó có nghĩa là bạn nhận được ít hơn từ họ so với các container theo thứ tự, nhưng tiện ích này giảm bớt cho bạn truy cập hiệu quả hơn.

Thực hiện khôn ngoan, hash_set, Tăng không theo thứ tự, TR1-không có thứ tự và C++ 11-không có thứ tự sẽ rất giống nhau, nếu không giống nhau. Ví dụ:

Answer 2

Chúng khá giống nhau. Tên tiêu chuẩn (C++ 0x) là unordered_set. hash_set là tên cũ hơn từ boost và những cái khác.

Answer 3

Ví dụ Visual Studio 2010 có cả hash_xxx và unordered_xxx và nếu bạn xem qua các tiêu đề, ít nhất việc triển khai thực hiện giống nhau cho tất cả các lớp đó (cùng một lớp -/"chính sách"). Đối với các trình biên dịch khác, tôi không biết, nhưng do thùng chứa băm thường phải được triển khai như thế nào, tôi đoán sẽ không có nhiều khác biệt, nếu có.

Answer 4

Về câu hỏi "là chúng giống nhau" từ dòng chủ đề: dựa trên kinh nghiệm nâng cấp mã của tôi từ __gnu_cxx :: hash_set thành std :: unordered_set, chúng gần như, nhưng không chính xác, giống nhau.

Sự khác biệt mà tôi gặp phải là lặp qua __gnu_cxx :: hash_set trả về các mục trong thứ xuất hiện là thứ tự chèn ban đầu, trong khi std :: unordered_set thì không. Vì vậy, như tên của nó, ta không thể dựa vào một iterator để trả về các mục theo bất kỳ thứ tự cụ thể nào khi lặp đi lặp lại toàn bộ std :: unordered_set.