python - 使用迭代器协议(protocol)访问已排序的字典

Question

我有一个字典“vcomments”，其中的键是非连续整数。当循环遍历键时，我需要按排序或反向排序的顺序执行此操作。目前我在用

for key_pt in sorted(self.view.vcomments.iterkeys()):

但我还需要找到超出或早于某个数字的那些键(或下一个键):

    if direction == 'down':
        sorted_pts = (key_pt for key_pt in sorted(self.view.vcomments.iterkeys()) if key_pt > curr_pt)
    else:
        sorted_pts = (key_pt for key_pt in reversed(sorted(self.view.vcomments.iterkeys())) if key_pt < curr_pt)
    try:
        next_pt = sorted_pts.next()
    except StopIteration:

1. 我是否可以创建一个迭代器类(使用迭代器协议(protocol))来存储字典并使我能够以正向或反向顺序循环遍历它们？我假设/猜测我可能需要首先分配一个属性值，该值将指示下一个循环是否应该是正向/反向。

2. 我能否在我的迭代器类中包含一个生成器函数(嵌套)，使我能够检索下一个键？也就是说，超出或之前提供的整数？

3. 同样，是否有一种方法可以让我提供开始点和结束点并检索位于这些值之间的所有键(按排序顺序)？

我很抱歉问了三个(虽然相关)问题 - 第一个问题的答案会让我开始。我并没有粗鲁到期待一个完整的解决方案，只是表明这些对我来说是否是可行的目标。

添加:我仍然需要能够通过其键检索单个特定的字典项目。

Answer 1

我认为最能满足您需求的数据结构是 skip list .我从来没有实现过一个——一直想——但在我看来它拥有你需要的所有东西。

1. 跳过列表按排序顺序存储其项目。使基本列表成为双向链表将允许在 O(n) 中进行正向和反向迭代。

2. 跳表允许 O(log n) 次插入、修改、删除和搜索。这不像字典那么快，但在我看来，如果您需要按排序顺序存储项目，字典会给您带来麻烦——即使是 OrderedDict，除非您 < em>很少添加键。

3. 通过上面维基百科文章中描述的一些修改，甚至可以在 O(log n) 中实现索引访问。

Python 中有一种实现 here - 可能还有其他人。

但是，您的一些评论表明您可能满足于简单地迭代字典的排序副本，而您只是想清理上面的代码。所以这是一种解决方法。这很天真，但这是一个起点。这假设您对 O(n) 搜索时间和 O(n log n) 迭代时间完全没问题，这都是次优的...

>>> 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'