Kiểm tra xem bản đồ trong C++ có chứa tất cả các phím từ một bản đồ khác

Question

Tôi đang lập kế hoạch sử dụng hai bản đồ trong C++, loại: std::map<char, Node>, trong đó Node là một lớp tùy chỉnh. Giả sử tôi có hai bản đồ, m1 và m2 của loại ở trên, tôi muốn tìm hiểu xem m1 chứa tất cả các phím có trong m2 hay không. Nói cách khác, tôi muốn xác minh rằng giao điểm của tập hợp các khóa của m1 và m2 giống với bộ khóa của m2.

tôi có thể lặp qua tất cả các phím trong m2 và làm một find() hoặc count() trên m1, nhưng điều đó có vẻ như một sự lãng phí và có lẽ sẽ chậm. Tôi nói điều này bởi vì các khóa được lưu trữ dưới dạng cây tìm kiếm nhị phân theo thứ tự sắp xếp trong một std::map và do đó mỗi tìm/số sẽ lấy O (logn) và cho khóa tiếp theo trong m2, cùng một đường dẫn trong các phím của m1 sẽ phải đi ngang từ đầu.

Tôi mới tham gia STL, vì vậy, hãy tha thứ cho sự thiếu hiểu biết của tôi về những thứ có vẻ dễ dàng thực hiện được. Ngoài ra, một số đoạn mã ví dụ đơn giản hoặc liên kết đến đoạn mã sẽ rất hữu ích để hiểu rõ hơn. Tôi không thể sử dụng các thư viện không chuẩn, bao gồm cả tăng cường.

Cảm ơn trước!

Answer 1

Vì các phím của số map được sắp xếp, bạn có thể lặp qua cả hai khóa cùng một lúc và so sánh các khóa với nhau. Nếu key(m1) < key(m2), hãy tăng trình lặp cho m1; nếu key(m2) < key(m1) thì m2 chứa khóa không phải trong m1.

Đây là O (n).