地图越长越慢

Question

地图会越长越慢吗？我不是在谈论迭代它,而是像.find() .insert()和的操作.at().

例如,如果我们有map<int, Object> mapA100'000'000个元素,map<int, Object> mapB并且只包含100个元素.

会不会有什么区别表现明智的执行mapA.find(x)和mapB.find(x)？

Answer 1

查找和插入操作的复杂性std::map是映射中元素数量的对数.因此,随着地图变大,它变得越来越慢,但只是它变得非常缓慢(比元素数中的任何多项式慢).要实现具有此类属性的容器,操作通常采用二进制搜索的形式.

想象它的速度有多慢,每次加倍元素数时,基本上需要进一步操作.因此,如果您需要在具有4000个元素的地图上执行k操作,则需要在具有8000个元素的地图上执行k + 1个操作,对于16000个元素执行k + 2操作,依此类推.

相比之下,std::unordered_map并没有为您提供元素的排序,作为回报,它为您提供了平均不变的复杂性.此容器通常实现为哈希表."平均"意味着查找一个特定元素可能需要很长时间,但查找许多随机选择的元素所需的时间除以查找元素的数量,并不依赖于容器大小.无序地图为您提供的功能更少,因此可以为您提供更好的性能.

但是,在选择使用哪个地图时要小心(提供顺序无关紧要),因为渐近成本并不能告诉您任何有关实际挂钟成本的信息.无序地图操作中涉及的散列成本可能会产生一个重要的常数因素,只会使无序地图比大尺寸的有序地图更快.此外,无序地图缺乏可预测性(以及使用所选键的潜在复杂性攻击)可能使得有序地图在需要控制最坏情况而不是平均值的情况下更可取.