c++ - STL::Map - 遍历列表还是使用查找？

Question

假设我有一个方法需要从包含 100 个元素的 map 中提取 8 个值。您认为哪个更好:

从头到尾走一次 for 循环，通过打开键拉出元素？

或者使用查找 8 次来获取这些值？

Answer 1

遍历列表将花费 O(n) 的时间来找到一个随机元素。

Map 是一个平衡的二叉树，所以查找是 O(log n)。

因此，执行 8 会在 8*log2(n) 中找到结果，并且遍历列表是 (n)。列表越大， yield 越大，但在所有随机情况下，查找比迭代更快。

在非随机情况下，如果有理由认为您想要的项目在树中彼此靠近，或者靠近“开始”(左侧)，那么行走/迭代会更快。但这似乎不太可能。