我计划在 C++ 中使用两个类型的映射:std::map<char, Node>
, where Node
是一个自定义类。假设我有两张地图,m1
and m2
对于上述类型,我想知道是否m1
包含all键存在于m2
。换句话说,我想验证一组键的交集m1
and m2
与以下的键组相同m2
.
我可以迭代所有键m2
并做一个find()
or count()
on m1
,但这似乎是一种浪费,而且可能会很慢。我这样说是因为键以二叉搜索树的形式按排序顺序存储在std::map
,因此每个 find/count 都将花费 O(logn),并且对于中的下一个键m2
,键中的相同路径m1
必须从头开始遍历。
我是 STL 的新手,所以请原谅我对看似应该很容易完成的事情的无知。此外,一些简单的示例代码片段或代码片段的链接将非常有助于更好地理解。我不能使用非标准库,包括 boost。
提前致谢!
由于 a 的键map
已排序,您可以同时迭代它们并将键相互比较。如果key(m1) < key(m2)
,增加 m1 的迭代器;如果key(m2) < key(m1)
那么 m2 包含 m1 中没有的密钥。
这是 O(n)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)