<p>我认为最适合您需要的数据结构是<a href="http://en.wikipedia.org/wiki/Skip_list" rel="nofollow">skip list</a>。我从来没有实现过一个——一直想实现——但在我看来,这已经具备了您需要的所有东西。在</p>
<ol>
<li><p>跳过列表按排序顺序存储其项。使基列表成为双链接列表将允许在O(n)中进行正向和反向迭代。</p></li>
<li><p>跳过列表允许O(logn)插入、修改、删除和搜索。这不像字典那么快,但在我看来,如果你需要按排序顺序存储项目,字典会给你带来麻烦——甚至是一个<code>OrderedDict</code>,除非你很少<em>添加键。</p></li>
<li><p>通过上面wikipedia文章中描述的一些修改,甚至可以在O(logn)中实现索引访问。</p></li>
</ol>
<p>Python <a href="http://infohost.nmt.edu/tcc/help/lang/python/examples/pyskip/web/index.html" rel="nofollow">here</a>中有一个实现——可能还有其他实现。在</p>
<p>但是,您的一些注释表明您可能满足于简单地迭代字典的排序副本,而您只是在尝试清理上面的代码。所以这里有一个方法。这很幼稚,但这只是一个起点。这假设您完全可以使用O(n)搜索时间和O(nlogn)迭代时间,它们都是次优的。。。在</p>
<pre><code>>>> class SortIterDict(dict):
... def __iter__(self):
... return iter(sorted(super(SortIterDict, self).__iter__()))
... def __reversed__(self):
... return reversed(tuple(iter(self)))
... def get_next(self, n):
... return next((x for x in iter(self) if x > n), None)
... def get_prev(self, n):
... return next((x for x in reversed(self) if x < n), None)
...
>>> d = SortIterDict({'d':6, 'a':5, 'c':2})
>>> list(d)
['a', 'c', 'd']
>>> list(reversed(d))
['d', 'c', 'a']
>>> d.get_next('b')
'c'
>>> d.get_prev('b')
'a'
</code></pre>