unordered_map: cái nào tìm nhanh hơn() hoặc đếm()?

Question

Cách nhanh nhất để tìm hiểu xem vùng chứa unordered_map có một mục có khóa được chỉ định không?

Answer 1

Chúng sẽ có hiệu suất tương đương. Bạn nên sử dụng thuật toán thể hiện rõ nhất những gì bạn đang cố gắng làm.

Để xây dựng trên đó, thông thường, count() sẽ được triển khai bằng cách sử dụng find(). Ví dụ, trong libcxx, count() được thực hiện như return (find(__k) != end());

Answer 2

Tôi nghĩ rằng Tìm là tùy chọn tốt nhất ở đây, không cần phải tiến xa hơn nữa.

http://www.cplusplus.com/reference/unordered_map/unordered_map/find/

Answer 3

find() và count() được áp dụng cho nhiều container trong C++.

Đối với bản đồ, bộ vv tìm sẽ luôn có thời gian thực hiện liên tục, vì nó chỉ tính giá trị băm và trả về trình lặp cho phần tử đầu tiên được tìm thấy (end() nếu không tìm thấy).

count() mặt khác, có thời gian thực hiện không đổi O (e), trong đó e là số lần khóa được cung cấp được tìm thấy. Trường hợp xấu nhất là một bộ sưu tập mà tất cả các thành viên đều giống nhau, vì vậy count có thể có độ phức tạp O (n)

map hoặc unordered_map không cho phép trùng lặp, do đó thời gian chạy tiệm cận của chúng sẽ giống nhau.

Lựa chọn phụ thuộc vào ngữ nghĩa trong mã của bạn. Nếu bạn chỉ muốn kiểm tra xem khóa có tồn tại hay không, bạn chỉ có thể sử dụng count. Nếu bạn muốn kiểm tra xem khóa có tồn tại hay không và sử dụng giá trị của khóa đó, hãy truy cập find vì bạn sẽ có một trình vòng lặp trỏ đến phần tử đó.