Par*_*esh 7 c++ stl intersection map set
我打算在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.
提前致谢!
由于a的键map被排序,您可以同时迭代它们并将键相互比较.如果key(m1) < key(m2),增加m1的迭代器; 如果key(m2) < key(m1)那么m2包含一个不在m1中的密钥.
这是O(n).