python 中 c++ STD::map 的替代方案（需要快速的 lower_bound 方法）

Question

我需要 cpp 中 std::map 的替代方案。我了解字典，但它使用哈希映射，它不支持始终排序的功能。理想情况下，我需要标准库中的东西。

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

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

Answer 1

根据文档，该模块应该提供您需要的内容：

\n\n

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

\n\n

尤其：

\n\n

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

\n\n

表现：

\n\n

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

\n\n

\n

替代的基于树的实现的运行时复杂性\n 与添加元素的 log_2{n} 成正比。对于较大的 \xe2\x80\x9cn\xe2\x80\x9d 值，对数的增长速度比立方根慢得多。然而，在实践中，我们永远不会达到那么大的值，并且所涉及的常数因素会产生重大影响。考虑十亿个元素：

\n\n

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

\n\n

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

\n\n

它们之间的常数因子是 1,000 / 33 \\大约 33。因此，如果基于树的实现的\n 操作速度慢 33 倍以上，则 SortedContainer 可能会更快。

\n

\n