检查C ++中的映射是否包含来自另一个映射的所有键 [英] Check if map in C++ contains all the keys from another map

问题描述

我计划在C ++中使用两种类型的映射： std :: map< char，Node> ，其中 Node 是一个自定义类。假设我有两个映射， m1 和 m2 上面的类型，我想知道 m1 包含 m2 中的所有键。换句话说，我想验证 m1 和 m2 的键集合的交集是否相同 m2 。

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.

我可以迭代 m2 并在 m1上执行 find（）或 count（） ，但这似乎是一种浪费，可能会很慢。我说这是因为键作为二叉搜索树以排序顺序存储在 std :: map 中，因此每个find / count将采用O（logn）对于 m2 中的下一个键， m1 的键中的相同路径必须从头开始遍历。

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.

我是STL的新人，所以请原谅我对于看起来很容易做到的东西的无知。另外，一些简单的示例代码片段或代码片段的链接将有助于更好地了解。我不能使用非标准库，包括boost。

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.

提前感谢！

推荐答案

由于映射的键被排序，您可以同时迭代它们，并将键相互比较。如果 key（m1） key（m2），递增迭代器为m1;如果 key（m2）键（m1），则m2包含不在m1中的键。

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.

这是O（n）。

这篇关于检查C ++中的映射是否包含来自另一个映射的所有键的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！