何时在std :: map上选择std :: vector作为键值数据？

Question

考虑缓存和数据局部性的积极作用主存储器中搜索时,我倾向于使用std::vector<>同std::pair<>样的键值项,进行线性搜索两种,如果我知道,键值项的总金额绝不会"太大"严重影响业绩.

最近我遇到过很多情况,事先我知道我将拥有大量的键值项目,因此std::map<>从一开始就选择了.

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

你呢

• 总是使用std::vector<>(或类似)？
• 总是使用std::map<>(或类似)？
• 对于项目计数范围中的哪一个优于另一个,有一种直觉？
• 完全不同的东西？

谢谢!

Answer 1

我很少使用std::vector线性搜索(除了如下所述的二进制搜索).我认为对于足够少的数据来说它会更好,但是如果用这么少的数据,任何东西都不可能提供巨大的优势.

根据使用模式,对二进制搜索std::vector可能有意义.std::map当您需要在使用期间定期更新数据时,A 运行良好.但是,在很多情况下,您加载一些数据然后使用数据 - 但是在加载数据之后,它大部分都是静态的(即,它变化很小,如果有的话).

在这种情况下,将数据加载到向量中,必要时对其进行排序,然后对数据进行二进制搜索(例如std::lower_bound,std::equal_range)会很有意义.这提供了两个世界中最好的 - 低复杂度二进制搜索和从高位置引用的良好缓存使用(即,向量是连续的,而不是a的链接结构std::map).当然,缺点是插入和删除速度很慢 - 但这是我用过你原来的想法的一次 - 分别存储新插入的数据,直到达到某个极限,然后才将其与其余部分一起排序.因此,单个搜索包括对数据主体的二进制搜索,然后线性搜索(少量)新插入的数据.

Answer 2

我永远不会仅仅基于（可能是虚假的）“效率”理由做出选择，而总是基于我实际上要对容器做什么。我想存储重复项吗？插入顺序重要吗？我有时会想搜索值而不是键吗？诸如此类的事情。