python - 在 python 中替代 c++ STD::map(需要快速的 lower_bound 方法)

Question

我需要从 cpp 中替代 std::map。我知道字典，但它使用 HashMap ，它不支持始终排序的功能。理想情况下，我需要标准库中的一些东西。

更正式地说，我需要能够始终排序并以对数时间添加元素的数据结构。像 map 这样的东西是用红黑树完成的。

编辑:我需要完全排序，而不仅仅是堆。编辑 2:OrderedDict 记住插入顺序，但我需要排序......如果我插入中位数，它应该插入中间而不是末尾。

Answer 1

根据文档，这个模块应该提供你需要的东西:

https://pypi.python.org/pypi/sortedcontainers

特别是:

http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html

性能:

http://www.grantjenks.com/docs/sortedcontainers/performance-scale.html

Alternative tree-based implementations have a runtime complexity proportional to log_2{n} for adding elements. The logarithm grows much more slowly than the cube root for large values of “n”. However, in practice we never reach those large values and the constant factors involved have a significant impact. Consider a billion elements:

\log_2{1,000,000,000} \approx 33

(1,000,000,000)^\frac{1}{3} \approx 1,000

The constant factor between those is 1,000 / 33 \approx 33. So if the operations for tree-based implementations are more than 33 times slower, then SortedContainers may be faster.