c++ - 检查 C++ 中的映射是否包含另一个映射中的所有键

Question

我计划在 C++ 中使用两个映射，类型为: std::map<char, Node> ，其中 Node 是自定义类。假设我有两个映射， m1 和 m2 以上类型，我想查明 m1 是否包含 m2 中存在的 所有 键。换句话说，我想验证 m1 和 m2 的键集的交集与 m2 的键集相同。

我可以遍历 m2 中的所有键并在 find() 上执行 count() 或 m1 ，但这看起来很浪费，而且可能很慢。我这样说是因为键在 std::map 中按排序顺序存储为二叉搜索树，因此每个查找/计数都将采用 O(logn)，对于 m2 中的下一个键，m1 键中的相同路径必须从头开始遍历。

我是 STL 的新手，所以请原谅我对似乎应该很容易完成的事情的无知。此外，一些简单的示例代码片段或代码片段的链接将非常有助于更好地理解。我不能使用非标准库，包括 boost。

提前致谢!

Answer 1

因为一个 map 的键已排序，您可以同时遍历它们并将键相互比较。如果key(m1) < key(m2) , 递增 m1 的迭代器；如果key(m2) < key(m1)然后 m2 包含一个不在 m1 中的 key 。

这是 O(n)。