c++ - 高效地在容器中查找多个项目

Question

我需要从一个大容器中找到一些对象。

我能想到的唯一方法似乎是在循环中一次只搜索容器中的一个项目，然而，即使是平均情况下说“log n”的有效搜索(其中n 是容器的大小)，这为我提供了整个操作的“m log n”(其中 m 是我要查找的项目数)。

这对我来说似乎不是最理想的，因为这是我可能需要经常做的事情，如果可能的话我绝对想改进。

这两个部分都还没有实现，所以我愿意就主容器的格式、我正在寻找的项目“列表”等以及实际的搜索算法提出建议。

项目是复杂的对象，但是搜索键只是一个简单的整数。

Answer 1

哈希表基本上是 O(1) 查找。这给了你 O(m) 来查找 m 个项目；显然，您查找 m 项的速度不能超过 O(m)，因为您需要得到结果。