何时选择STD::STD::关键值数据的映射?

我很少用 std::vector 使用线性搜索(以下所述的二进制搜索除外)。我认为,对于足够少的数据量来说,情况会更好,但是有了这些小数据,任何事情都不可能提供巨大的优势。

根据使用模式,二进制搜索 STD::载体 不过也有道理。一 std::map 当您需要在使用过程中定期更新数据时,可以很好地工作。然而,在相当多的情况下,您先加载一些数据,然后再使用这些数据——但是在加载了数据之后,它大部分仍然是静态的(也就是说,它变化很小,如果有的话)。

在这种情况下,将数据加载到向量中,必要时对其进行排序,然后对数据进行二进制搜索(例如 std::lower_bound , std::equal_range )这提供了几乎两个世界中最好的——低复杂性二进制搜索 和 从引用的高位置(即向量是连续的,而不是 STD::地图 )当然,缺点是插入和删除很慢——但这是我第一次使用您的原始想法——将新插入的数据单独存储,直到达到某个限制,然后才将其与其余数据进行排序,因此单个搜索由数据主体,然后对新插入的(少量)数据进行线性搜索。

我决不会仅仅基于(可能是伪造的)“效率”的理由做出选择,而是总是基于我对容器的实际操作。我要存储副本吗?插入顺序重要吗?我有时会想搜索值而不是键吗?那些东西。

我几乎总是喜欢使用map(或者无序的map,当散列容器更有意义时)和vector。

尽管如此,我认为你的推理是倒退的。我倾向于用向量 只有 当有大量的数据时,因为向量的内存占用会更小。

使用正确的数据集类型,您可以加载一个向量,然后对其进行排序和二进制搜索,使其具有更小的占地面积和与地图相似的性能特征,尤其是在加载后数据集是稳定的情况下。

您是否考虑过使用已排序的数据结构?他们倾向于提供对数搜索和插入-一个合理的权衡。就我个人而言,除了喜欢地图之外,我没有任何硬性和快速的规则,因为它能够输入人类可读/可理解的价值。

当然,还有很多关于映射与列表/向量(排序和未排序)的效率的讨论——如果您的键是一个10000个字符的字符串,那么进行字符串比较要比搜索一个只有几个项目的列表花费更长的时间,因此您希望确保能够也会冷冰冰地比较钥匙。

你为什么不吃 unordered_map 计入账户?