在不使用迭代的情况下查找两个映射中的共同值

Question

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

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

我希望从两个映射中仅检索出键都存在的值。例如，如果键“10001”在mapA和mapB中都找到，则我需要来自两个映射的相应对象。类似于在SQL表上执行联接。最简单的方法是迭代较小的映射，然后在每次迭代中进行std::find（iter->first）以找到符合条件的键。但那也会非常昂贵。

相反，我考虑维护这样一个集合：

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

1) 每次我往其中一个映射中插入数据时，都会检查它是否存在于另一个映射中。如果存在，则将该键添加到上述公共集合中。

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

公共集合始终维护两个映射中都存在的键。当我想要进行连接操作时，已经有了符合条件的键。是否有更快/更好的方法？

- Sharath

---

1万条目并不算很多 - 我会选择最简单的解决方案，几乎肯定足够快。 - user2100815

我最可能会使用https://en.cppreference.com/w/cpp/algorithm/set_intersection或类似这些答案：https://dev59.com/lG865IYBdhLWcg3whe9f。这真的取决于您需要多频繁地执行此操作以及地图更改的频率。尝试缓存数据可能对某些用途很有价值，但对于其他用途而言，过于复杂且更加昂贵。 - Retired Ninja

通常情况下，你是对的。但是由于这个函数被频繁调用，所以我需要尽可能地提高性能。 - Sharath

Answer 1

这个算法非常简单。首先，你将两个地图视为序列（使用迭代器）。

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

你将遍历两个地图，这意味着复杂度为O（n+m），这比朴素的方法O（n log m）或O（m log n）的复杂度要好得多。

- Ulrich Eckhardt