何时选择关键值数据的std :: map over std :: map？

Question

考虑到在主内存中搜索时缓存和数据局部性的积极影响，我倾向于使用std::vector<>和std::pair<>类似的键值项目，并对两者执行线性搜索，如果我知道键值项目的总数将会永远不要“太大”来严重影响性能。

最近我一直在很多情况下我事先知道，我将有键值项的数额巨大，因此都选择了std::map<>从此开始。

我想知道如何在上述情况下为适当的容器做出决定。

你

• 始终使用std::vector<>（或类似）？
• 始终使用std::map<>（或类似）？
• 对于产品数量范围内的哪一个比另一个更可取？
• 东西完全不同吗？

谢谢！

Answer 1

我很少使用std::vector与线性搜索（除了与二进制搜索相结合，如下所述）。我认为对于数据量足够小的数据来说会更好，但对于那些小数据来说，任何事情都不可能提供巨大的优势。

根据使用模式，std::vector上的二进制搜索可能有意义。当您需要在使用过程中定期更新数据时，A std::map可以很好地工作。然而，在很多情况下，您会加载一些数据然后使用这些数据 - 但是在您加载数据之后，它大部分保持静态（即，如果有变化，它几乎不会变化）。

在这种情况下，将数据加载到矢量中，必要时对其进行排序，然后对数据执行二分搜索（例如std::lower_bound,std::equal_range）可能具有很大意义。这几乎是两全其美的 - 低复杂度的二进制搜索和从高参考位置（即，该矢量是连续的，与std::map的链接结构相反），良好的高速缓存使用。当然，缺点是插入和删除速度很慢 - 但这是我用过原始想法的一次 - 分别存储新插入的数据，直到达到某个限制，然后才将其与其余的数据，所以单个搜索包括对数据主体的二进制搜索，然后是对（少量）新插入的数据进行线性搜索。

Answer 2

我永远不会仅仅在“效率”的基础上作出选择（但可能是假的），但总是以我实际上对容器做的事情为准。我想存储重复吗？广告订单是否重要？我有时会想要搜索的价值不是关键？那些东西。

Answer 3

我几乎总是更喜欢使用map（或unordered_map，当散列容器变得更有意义）与矢量。

这就是说，我认为你的推理是倒退的。当存在大量数据时，我会倾向于使用向量，因为向量将占用更小的内存空间，所以只有。

使用正确的数据集类型，您可以加载矢量，然后对其进行排序并进行二进制搜索，以较小的覆盖区和与地图类似的性能特征，尤其是在数据集加载后稳定的情况下。

Answer 4

你有没有考虑过使用排序后的数据结构？他们倾向于提供对数搜索和插入 - 一个合理的折衷。就我个人而言，除了喜欢地图之外，我没有任何硬性规则和快速规则来输入可读/可​​理解的值。

当然，还有很多关于地图与列表/矢量（已排序和未排序）效率的讨论 - 如果您的密钥是一个字符数为10,000个字符的字符串，则比搜索要花费更长的时间通过一个只有几个项目的列表，所以你要确保你可以有效地比较密钥。

Answer 5

为什么不考虑unordered_map？