将采取最小数据的示例std::map。
我有2个映射如下：找到超过1个（多个）'std :: map's'或'std :: set'键的最佳方法？
map<string, Object*> map_ShortKey; // keys are single English words
map<string, Object*> map_LongKey; // keys are concatenated English words
的map_ShortKey在周围50个元素的节目的开始被填充并在整个保持恒定。但整个计划中的map_LongKey不断增加，它可能会上升到1000-10000个元素。
当我想在这些地图内搜索一个单词时，最好的方法是什么？
（1）先搜索map_ShortKey，如果找不到，则搜索m_LongKey。
（2）添加到map_ShortKey和m_LongKey然后搜索
你的意思是搜索词，或搜索的关键？
如果map_LongKey包含级联的话，那么寻找一个串联的第一个字是不成功的。
如果您正在寻找的东西，实际上是在地图的一个关键然而，那么答案（2）取决于许多因素 - 需要更多的信息。
如果速度是你的关心，然后搜索首先在哪个地图是最有可能包含的关键。
如果速度是不是你的关注，然后组织你的代码清晰 - 这是否涉及合并的地图一起或以其他方式将取决于您的情况。
我应该在我的答案中提到“清晰的结构”！ –
这取决于在map_Shortkey中成功查找的可能性 - 如果很有可能，那么您只在此搜索[log2（n）]中花费6个“步骤”，其中在map_LongKey列表中搜索的平均值为10-13 “脚步”。
另一方面，如果您不太可能在map_shortKey中找到您正在寻找的东西，那么在大集合中的另外50个元素之间搜索的额外负载不会有太大的区别。
由于我们不知道成功的统计数字，所以很难说哪种方法更好。
如果您青睐的最坏情况的复杂性和不知道什么你的搜索（例如，关键是更可能在一个地图上可以找到比其他），那么我会去的方法1）。
查找在std::map具有对数最坏情况的复杂性，所以在第一种情况下，你将最终的log(n) + log(m)查找（假设你的地图分别有n和m元素）最坏情况的复杂性。因此，k查找将花费你k * (log(n) + log(m))。
地图中的插入也具有对数复杂性，所以在第二种情况下，您将强制m从一个地图插入另一个地图，然后在地图中使用m + n元素进行查找。因此，对于k查找（假设您只是第一次进行插入操作），会导致最坏情况的复杂性。
因此，如果你关心的最坏情况复杂，方法1）是优选的，只要：
k * (log(n) + log(m)) < m * log(n) + k * log(n + m)
您可以根据您的工作负载，n和m根据输入的大小估计k ，并做数学计算出什么是最好的（然后通过测量再次检查）。
在上述帖子的评论中看到澄清。 OP在每次查找时都不会添加到地图中。 – Yakk
@Yakk：我做了一个错误的假设，然后从文本中就不清楚了。我编辑了我的答案。 –
第一：措施。第二：措施。第三：措施。 –
也许最好的是（3）管理第三张地图：总是包含两者的'map_ShortAndLongKey'。取决于搜索频率与添加到map_LongKey中的频率。 –
@DidierTrosset，这是关于解析一个随机文件，我不确定测量/分析数据在这种情况下总是可靠的。我想知道以上两种方法的平均表现，如果有人从过去的经验中获得了方便的知识，那么这太棒了！ – iammilind