检查地图在C ++中包含了另一个地图的所有按键(Check if map in C++ contai

2019-08-01 05:21发布

我计划在C ++中使用两张地图,类型: std::map<char, Node> ,其中Node是一个自定义类。 假设我有两张地图, m1m2上述类型的,我想找出是否m1包含了目前所有的键m2 。 换句话说,我想验证该组密钥的交点m1m2是相同的该组密钥的m2

我可以遍历所有的键m2和做一个find()count()m1 ,但这似乎是一个浪费,很可能是缓慢的。 我这样说是因为密钥被存储在一个在有序二叉搜索树std::map ,因此每个查找/计数需要O(LOGN),并在接下来的关键m2 ,在相同的路径的键m1将不得不从一开始就走过。

我是新来的STL,所以请原谅我什么,似乎喜欢的事,应该是可行容易无知。 此外,一些简单的例子代码段或链接代码片段将非常有助于更好地理解。 我不能使用非标准库,包括提升。

提前致谢!

Answer 1:

由于的按键map进行排序,你可以在同一时间通过二者的迭代和按键进行相互比较。 如果key(m1) < key(m2)用于递增M1迭代器; 如果key(m2) < key(m1)然后平方米含有不在M1的密钥。

这是O(n)。



文章来源: Check if map in C++ contains all the keys from another map