无需迭代即可在两个地图中找到共同的价值

Question

我有这两张地图，每张地图都存储着10000多个条目：

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

我只想从两个地图中都存在键的地图中检索这些值。

例如，如果在mapA和mapB中都找到了键“ 10001”，那么我要从两个地图中找到相应的对象。类似于对SQL表进行联接。最简单的方法是迭代较小的映射，然后在每次迭代中执行std :: find（iter-> first）来查找合格的键。那也将是非常昂贵的。

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

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

1）每次插入其中一张地图时，我都会检查它是否存在于另一张地图中。如果是这样，我将密钥添加到上面的通用集中。

2）每次我从一个映射中删除一个条目时，都会从公用集中删除该密钥（如果存在）。

公用集始终维护两个映射中的键。当我想要加入时，我已经有了资格密钥。有更快/更好的方法吗？

Answer 1

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

• 如果任何剩余序列为空，则操作完成。
• 如果序列前面的键相同，则说明已找到一个匹配项。
• 如果键不同，则丢弃两者中的较低者（根据地图的排序顺序）。

您将遍历两个映射，这意味着O（n + m）的复杂性，这比其O（n log m）或O（m log n）复杂性的朴素方法要好得多。