“随机访问O（1）”是一个非常严格的要求，基本上要求一个基础哈希表-我希望您只表示随机READS，因为我认为它可以通过数学证明，而在一般情况下不可能拥有O
（1）编写以及O（N）有序的迭代。
我认为您不会找到适合您需求的预包装容器，因为它们是如此极端-O（log N）访问当然会改变世界。为了获得您要进行读取和迭代的big-
O行为，您需要粘合两个数据结构，本质上是一个dict和一个堆（或排序列表或树），并使它们保持同步。尽管您没有指定，但我认为您只会得到想要的 摊销 行为-
除非您真正愿意为插入和删除付出任何性能上的损失，这实际上是您表达的规范的涵义，但确实似乎不太可能是现实生活中的要求。
对于O（1）读取并 分摊 O（N）有序迭代，只需将所有键的列表保留在字典一边。例如：
class Crazy(object): def __init__(self): self.d = {} self.L = [] self.sorted = True def __getitem__(self, k): return self.d[k] def __setitem__(self, k, v): if k not in self.d: self.L.append(k) self.sorted = False self.d[k] = v def __delitem__(self, k): del self.d[k] self.L.remove(k) def __iter__(self): if not self.sorted: self.L.sort() self.sorted = True return iter(self.L)如果你不喜欢“摊余O（N）令”您可以删除self.sorted，只是重复
self.L.sort()的
__setitem__本身。当然，这使写操作为O（N
log
N）（尽管我仍然在O（1）上进行写操作）。每种方法都是可行的，并且很难认为一种方法本质上优于另一种方法。如果您倾向于写一堆，然后进行一堆迭代，那么上面代码中的方法是最好的。如果通常是一次写入，一次迭代，另一次写入，另一次迭代，那么就差不多了。
顺便说一句，这利用了Python排序（又称“
timsort”）的异常（和出色；-）性能特征的无耻优势：在其中，排序一个列表，该列表大部分已排序，但最后附加了一些其他项目，基本上是O
（N）（如果与排序的前缀部分相比，粘贴的项目足够少）。我听说Java很快就会获得这种收益，因为Josh
Block对Python的技术演讲印象深刻，以至于他开始在随处的笔记本电脑上为JVM进行编码。大多数系统（包括我相信今天的Jython和IronPython在内）基本上都以O（N
log N）操作进行排序，而没有利用“大多数有序”输入；在这方面，蒂姆·彼得斯（Tim
Peters）塑造成如今的Python风格的“自然合并排序”是一个奇迹。
