Check if a card in C ++ contains all the keys from another card

Question

I plan to use two maps in C ++, such as: std::map<char, Node> , where Node is a custom class. Suppose I have two cards, m1 and m2 type above, I want to find out if m1 contains all the keys present in m2 . In other words, I want to check that the intersection of the key set m1 and m2 matches the key set m2 .

I could iterate over all the keys in m2 and do find() or count() on m1 , but that would seem like a waste and would probably be slow. I say this because the keys are stored as a binary search tree in sorted order in std::map , so each of find / count will take O (logn), and for the next key in m2 - the same path to the keys from m1 should be passed from the start.

I am new to STL, so please forgive my ignorance of what seems like something that should be easy to do. In addition, some simple snippets of code or links to snippets of code will be very useful for understanding better. I can not use non-standard libraries, including boost.

Thanks in advance!

Answer 1

Since the keys to map are sorted, you can iterate over both of them at the same time and compare the keys with each other. If key(m1) < key(m2) , increase the iterator for m1; if key(m2) < key(m1) , then m2 does not contain the key in m1.

This is O (n).