sự khác nhau giữa set và unordered_set trong C++ là gì?

Question

Came qua câu hỏi này tốt, mà là tương tự nhưng không phải ở tất cả cùng vì nó nói về Java, trong đó có thực hiện khác nhau của hash-bàn, nhờ có đồng bộ accessor/mutators Differences between HashMap and Hashtable?

Vì vậy, sự khác biệt là gì trong C++ thực hiện thiết lập và unordered_set? Câu hỏi này có thể là ofcourse mở rộng đến bản đồ vs unordered_map và như vậy cho các thùng chứa C++ khác.

Dưới đây là đánh giá ban đầu của tôi

thiết: Trong khi doesnt tiêu chuẩn yêu cầu một cách rõ ràng nó được thực hiện như cây, hạn chế thời gian phức tạp yêu cầu hoạt động của nó đối với find/chèn, có nghĩa là nó sẽ luôn luôn được thực hiện như cây. Thông thường như cây RB (như đã thấy trong GCC 4.8), được cân bằng chiều cao. Vì họ là chiều cao cân, họ có thể dự đoán được thời gian phức tạp cho find()

Ưu điểm: Nhỏ gọn (so với DS khác so)

Côn: Truy cập thời gian phức tạp là O (lg n)

unordered_set: Trong khi chuẩn không rõ ràng yêu cầu nó được thực hiện như cây, ràng buộc phức tạp về thời gian được yêu cầu cho hoạt động tìm/chèn, nghĩa là nó sẽ luôn được triển khai dưới dạng bảng băm.

Ưu điểm:

1. nhanh hơn (lời hứa trả dần O (1) cho tìm kiếm)
2. dễ dàng để chuyển đổi nguyên thủy cơ bản để thread-safe, so với cây DS

Nhược điểm:

1. Tra cứu không được đảm bảo là O (1) Trường hợp xấu nhất có tính chất Therotical là O (n)
2. Không nhỏ gọn như cây. (cho các yếu tố tải trọng mục đích thực tế là không bao giờ 1)

Lưu ý: O (1), cho hashtable đến từ giả định rằng không có va chạm. Ngay cả với hệ số tải là 0,5, mọi biến chèn thứ hai đều dẫn đến va chạm. Có thể quan sát thấy rằng hệ số tải của bảng băm tỷ lệ nghịch với số lượng hoạt động cần thiết để truy cập vào một phần tử trong đó. Chúng tôi càng giảm # hoạt động, bảng băm nhỏ hơn. Khi phần tử được lưu trữ có kích thước tương đương với con trỏ, thì chi phí trên là khá đáng kể.

Chỉnh sửa: Vì phần lớn câu hỏi có chứa câu trả lời đầy đủ, tôi thay đổi câu hỏi thành "Tôi có bỏ sót bất kỳ sự khác biệt nào giữa bản đồ/tập hợp để phân tích hiệu suất mà một người nên biết không?"

Answer 1

Tôi nghĩ rằng nói chung bạn đã trả lời câu hỏi của riêng bạn, tuy nhiên, điều này:

Không như nhỏ gọn như cây. (cho các yếu tố tải mục đích thực tế là không bao giờ 1)

không nhất thiết phải đúng.Mỗi nút của một cây (chúng tôi sẽ giả định đó là một cây màu đỏ-đen) cho một loại T sử dụng không gian bằng ít nhất 2 * pointer_size + sizeof(T) + sizeof(bool). Đây có thể là 3 * pointer size tùy thuộc vào việc cây có chứa con trỏ parent cho mỗi nút cây hay không.

So sánh điều này với bản đồ băm: sẽ có không gian mảng bị lãng phí cho mỗi bản đồ băm do thực tế là load factor < 1 như bạn đã nói. Tuy nhiên, giả sử bản đồ băm sử dụng các danh sách được liên kết đơn lẻ cho chuỗi (và thực sự, không có lý do thực sự nào không), mỗi phần tử được chèn chỉ mất sizeof(T) + pointer size.

Lưu ý rằng phân tích này bỏ qua bất kỳ chi phí nào có thể đến từ không gian thừa được sử dụng bằng cách căn chỉnh.

Đối với mọi thành phần T có kích thước nhỏ (vì vậy, bất kỳ loại cơ bản nào), kích thước của con trỏ và chi phí khác chiếm ưu thế. Với hệ số tải là > 0.5 (ví dụ), std::unordered_set thực sự có thể sử dụng ít bộ nhớ hơn số std::set tương đương.

Điểm thiếu lớn khác là thực tế việc lặp qua std::set được đảm bảo tạo ra thứ tự từ nhỏ nhất đến lớn nhất, dựa trên hàm so sánh đã cho, trong khi lặp qua một std::unordered_set sẽ trả về giá trị theo thứ tự "ngẫu nhiên" .

Answer 2

Sự khác biệt (mặc dù không liên quan đến hiệu suất) là việc chèn set không làm mất hiệu lực trình lặp, trong khi chèn unordered_set có thể nếu nó kích hoạt phục hồi. Trong thực tế nó là một mối quan tâm khá nhỏ, vì tham chiếu đến các yếu tố thực tế vẫn còn hiệu lực.

Answer 3

Yuushi xử lý hiệu quả không gian và các điểm khác tốt; chỉ một vài phần khác của câu hỏi tôi sẽ nhận xét về ...

O (1), cho hashtable xuất phát từ giả định rằng không có va chạm.

Điều đó không đúng. Những gì O (1) có nghĩa là không phải là nỗ lực tra cứu đầu tiên sẽ luôn thành công, đó là - trung bình - một số cố gắng liên tục cần thiết, thay vì cái gì đó phát triển khi số lượng giá trị tăng lên. Ví dụ: với unordered_set hoặc ... _map, max_load_factor mặc định là 1.0 khi xây dựng và nếu hệ số tải tiếp cận với hàm băm tốt, số thành phần trung bình băm vào bất kỳ một nhóm nào sẽ ở khoảng 2 bất kể có bao nhiêu giá trị trong bảng.

Ngay cả với hệ số tải là 0,5, mọi biến chèn thứ hai đều dẫn đến va chạm.

Đúng, nhưng nó không trở nên nghiêm trọng như bạn có thể mong đợi một cách trực quan: chiều dài chuỗi trung bình là 2 ở 1,0 yếu tố tải không tồi.

Nó có thể được quan sát thấy rằng tải trọng-yếu tố của bảng băm là nghịch tỉ lệ với số hoạt động cần thiết để truy cập vào một yếu tố trong đó. Chúng tôi càng giảm # hoạt động, bảng băm nhỏ hơn.

Chắc chắn có sự tương quan (không phải là nghịch đảo).