Tôi tự hỏi cái nào hiệu quả hơn.multimap vs bản đồ với tập hợp
std::map< String, std::set<int> >
hoặc
std::multimap< String, int >
EDIT: Tôi không có kế hoạch làm bất cứ điều gì khác thường với những tấm bản đồ. Chèn, xóa, sửa đổi, tìm kiếm chuẩn. Kích thước của mỗi bộ hoặc chuỗi đa khóa không được lớn hơn 100.
này tôi tin là thực hiện phụ thuộc, nhưng một (un) đoán:
Trên thực tế nó phụ thuộc vào số lượng các số nguyên mà bạn sẽ được giữ trong multimap hoặc std::set. A multimap rất có thể sẽ sử dụng tìm kiếm tuyến tính các giá trị sau khi tìm kiếm (n) của khóa. Nếu bạn có một số lượng lớn các giá trị số nguyên, thì tìm kiếm nhật ký (n) của các khóa theo sau là một tìm kiếm nhật ký (n) của các giá trị có thể nhanh hơn một chút.
Tuy nhiên, xét về hiệu quả, hãy lưu trữ bất kỳ thứ gì trong một số map hoặc multimap với khóa string gần như chắc chắn sẽ lớn hơn sự khác biệt trong cả hai trường hợp.
Như đã nói bên dưới, một số multimap có thể dễ sử dụng hơn và rõ ràng hơn để duy trì cho nó một lợi thế riêng biệt.
Tôi không thể nói chắc chắn nhưng được cho rằng multimap được thiết kế để làm những gì khác là một biểu thức, nên tốt hơn là cụ thể và sử dụng multimap, nó có ý nghĩa hơn nhiều, nó cũng có các hàm thành viên để làm việc với một multimap như một khái niệm, các hàm đó sẽ là một chút sôi nổi khi sử dụng cách tiếp cận khác.
std :: multimap < Chuỗi, int> có nhiều khả năng tiết kiệm bộ nhớ hơn.
Bạn có lý do? –
Số lượng các số được lưu trữ giống nhau ở cả hai nhưng vì bạn đang sử dụng hai cây màu đỏ đen, bạn đang sử dụng gấp hai lần số lần "lưu giữ sách" hơn là cần thiết. Hơn nữa, cho rằng hầu hết std :: string STL triển khai sử dụng tính toán tham khảo và sao chép về ngữ nghĩa viết, dữ liệu được sử dụng bởi các chuỗi có thể không được tăng gấp đôi. Hy vọng điều này có ý nghĩa khi tôi gõ vào điện thoại của tôi. –
Trên thực tế, bạn chưa chứng minh rằng một bản đồ và các bộ chiếm nhiều không gian hơn so với một multimap (những gì về sổ sách _additional_ của multimap?), Nhưng trên thực tế bạn sẽ lưu trữ nhiều hơn hai cây. Và điều này được thực hiện vì cây không được chỉ định. Và không có không gian tên 'std' trong STL. Và, thực sự, bình luận của tôi đã được dự định để kích động bạn thêm một lý do để _answer_ của bạn;) –
Nếu bạn không hài lòng với những câu trả lời cho đến nay (không nói rằng bạn không phải) và tôi hoàn toàn buộc phải trả lời, tôi sẽ cung cấp cho tôi được giáo dục "đoán" quá:
Để chèn, các multimap có vẻ hiệu quả hơn. Với cách tiếp cận bản đồ, trước tiên bạn phải truy xuất, sau đó thực hiện thao tác trên tập hợp. Để xóa/truy xuất, bản đồ có vẻ "hiệu quả" hơn.
Tùy chọn "đặt" sẽ loại bỏ các cặp khóa + giá trị trùng lặp, cho dù đa phương thức sẽ không.
Chúng thực sự không tương đương. A multimap<X,Y> cho phép lưu trữ cặp khóa-giá trị trùng lặp, trong khi map<T, set<X>> thì không.
multimap<int, int> m;
m.insert(make_pair(2, 3));
m.insert(make_pair(2, 3)); // This changes the size of m!
Trong khi
map<int, set<int>> m;
m[2].insert(3);
m[2].insert(3); // This does nothing.
Vì vậy, tôi sẽ sử dụng phương pháp thiết lập trừ khi bạn cần lặp lại cặp khóa-giá trị. Cú pháp cũng đẹp hơn. Tôi hy vọng sự khác biệt về hiệu suất và sử dụng bộ nhớ không phải là tuyệt vời.
Xác định "hiệu quả". –
Các hoạt động mà bạn muốn thực hiện là gì?Điều đó sẽ xác định các chi phí khác nhau, vì cách tiếp cận đầu tiên sẽ cho phép bạn thực hiện tra cứu nhanh bằng cả chuỗi và số nguyên và thứ hai sẽ yêu cầu bạn lặp lại và kiểm tra phần int so với mỗi giá trị mà chuỗi đó giống nhau ... Nhưng nếu bạn không cần thao tác đó, có thể trường hợp tùy chọn thứ hai tốt hơn trong một số trường hợp sử dụng ... –
hãy xem bản chỉnh sửa của tôi –