Check if map in C++ contains all the keys from another map

Question

I am planning to use two maps in C++, of type: std::map<char, Node>, where Node is a custom class. Suppose I have two maps, m1 and m2 of the type above, I want to find out whether m1 contains all keys present in m2. In other words, I want to verify that the intersection of the set of keys of m1 and m2 is the same as the set of keys of m2.

I could iterate over all keys in m2 and do a 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 an std::map, and so each of find/count will take O(logn), and for the next key in m2, the same path in the keys of m1 will have to be traversed from the beginning.

I am new to STL, so please forgive my ignorance on what seems like something that should be doable easily. Also, some simple example code snippets or links to code snippets will be very helpful to understand better. I cannot use non-standard libraries, including boost.

Thanks in advance!

Answer 1

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

This is O(n).