c++ - 在不迭代的情况下在两个映射中找到公共(public)值

Question

我有这两张 map ，每张都存储了 10000 多个条目:

std::map<std::string,ObjectA> mapA;
std::map<std::string,ObjectB> mapB;

我只想从两个映射中都存在其键的映射中检索那些值。

例如，如果在 mapA 和 mapB 中都找到键“10001”，那么我需要两个 map 中的相应对象。类似于对 SQL 表进行连接。最简单的方法是迭代较小的 map ，然后在每次迭代中执行 std::find(iter->first) 以找到符合条件的键。那也将是非常昂贵的。

相反，我正在考虑维护这样一个集合:

std::set<std::string> common;

1) 每次插入其中一个 map 时，我都会检查它是否存在于另一个 map 中。如果是，我将 key 添加到上面的公共(public)集。

2) 每次我从其中一个映射中删除一个条目时，我将从公共(public)集中删除该键(如果存在)。

公共(public)集始终维护两个映射中的键。当我想进行连接时，我已经有了限定键。有没有更快/更好的方法？

Answer 1

算法非常简单。首先，您将这两个映射视为序列(使用迭代器)。

• 如果剩余序列中的任何一个为空，您就完成了。
• 如果序列前面的键相同，则您找到了匹配项。
• 如果键不同，则丢弃两者中较低的(根据 map 的排序顺序)。

您将迭代两个映射，这意味着 O(n+m) 的复杂度，这明显优于具有 O(n log m) 或 O(m log n) 复杂度的原始方法。