"multiset" & "multimap" - Vấn đề là gì?

Question

Khi câu hỏi nêu rõ ... Tôi không nhận được điểm về số multisets/multimaps.

Vì vậy, mục đích là gì?

Answer 1

Một số trường hợp sử dụng:

Multimap

• Với mã bưu điện như một chìa khóa, tất cả mọi người có mã bưu điện
• Với ID tài khoản như chìa khóa, tất cả các đơn đặt hàng mở của người đó/tài khoản
• Từ điển, với mỗi từ khóa giải thích khác nhau

multiset

thực chất là bản đồ có khóa và số nguyên.

• Việc kiểm kê của một cửa hàng, tất cả các sản phẩm có chìa khóa của họ và số tiền vẫn sẵn là giá trị
• tích lũy dữ liệu bán hàng của một cửa hàng, mỗi khi một sản phẩm được bán sản phẩm id get của bổ sung vào multiset do đó tăng số lượng đã bán

Answer 2

http://www.cplusplus.com/reference/stl/multimap/

Maps là một loại kết hợp container lưu trữ các yếu tố hình thành bởi sự kết hợp của một giá trị quan trọng và một giá trị ánh xạ, giống như bản đồ container, nhưng cho phép khác nhau yếu tố để có cùng giá trị khóa.

Đây là loại đăng ký nơi các thành phần có thể chia sẻ khóa. Bạn có thể nghĩ về các công ty và nhân viên. Địa chỉ đường phố là chìa khóa và nhân viên là các giá trị.

Answer 3

Đây là những gì Wikipedia nói về công dụng:

• Trong một hệ thống tuyển sinh, nơi sinh viên có thể được ghi danh trong nhiều lớp cùng một lúc, có có thể là một hiệp hội cho mỗi tuyển của một học sinh trong một khóa học, trong đó khóa là ID sinh viên và giá trị là ID khóa học. Nếu sinh viên được đăng ký theo ba khóa học, sẽ có ba liên kết có chứa cùng một khóa.
• Chỉ số của một cuốn sách có thể báo cáo bất kỳ số lượng tài liệu tham khảo cho một thuật ngữ chỉ số nhất định, và do đó có thể được mã hóa như một Multimap từ các thuật ngữ chỉ số để bất kỳ số địa điểm tham khảo

Answer 4

Một ví dụ nơi một multimap sẽ hữu ích nếu bạn có một tình huống mà hầu hết thời gian các phím là duy nhất, nhưng đôi khi họ không.

Ví dụ: nếu bạn đang tạo lớp bộ nhớ cache sử dụng băm làm khóa. Hầu hết thời gian hai đối tượng khác nhau sẽ không có cùng một băm, do đó, các phím sẽ là duy nhất. Nhưng có thể bạn sẽ nhận được va chạm băm cho các đối tượng khác nhau, vì vậy bạn sẽ muốn có một multimap để bao quát tình huống đó.

Ví dụ khác sẽ là bất kỳ loại chỉ mục không duy nhất nào (như trong cơ sở dữ liệu).

Đối với nhiều người - tôi nghĩ những thứ đó sẽ ít hữu ích hơn. Điều duy nhất tôi có thể nghĩ là sử dụng nó như một loại danh sách được sắp xếp tự động.

Answer 5

Một multiset hoặc multimap chỉ đơn giản là cho các tình huống có thể có nhiều hơn một mục cụ thể. Ví dụ: giả sử bạn muốn tạo chỉ mục cho một cuốn sách. Bạn sẽ quét qua các văn bản, ném ra tất cả các từ vô nghĩa phổ biến thực sự ("a", "an", "the", vv) và sau đó tạo một danh sách tất cả các phần còn lại và vị trí trong cuốn sách nơi mỗi xảy ra.

Khá một vài từ sẽ xuất hiện trên nhiều trang, trong trường hợp này, bạn sẽ có nhiều mục nhập từ một từ đến các trang khác nhau. Một cách để xử lý đó sẽ là một bội số từ các từ đến số trang.

Answer 6

Sử dụng đa chiều, bất cứ nơi nào bạn muốn sử dụng loại cấu trúc cây.

Answer 7

Lợi ích quan trọng nhất của việc sử dụng một bội số trên một vectơ/danh sách (hoặc bất kỳ vùng chứa nào khác) là độ phức tạp của hoạt động tìm. độ phức tạp trung bình của trường hợp cho multiset là O (logn) và unordered_multiset là O (1). Tương tự cũng đúng đối với multimap và ordered_multimap.