使用迭代器协议访问排序字典

Question

我有一个字典“vcomments”，其中的键是非顺序整数。当循环通过键时，我需要按排序或反向排序的顺序进行。目前我使用

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

但我还需要找到那些在某个数字之外或之前的键（或下一个键）：

^{pr2}$

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

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

3. 类似地，我是否可以提供起始点和结束点，并检索这些值之间的所有键（按排序顺序）？

我很抱歉问了三个问题（虽然相关），第一个问题的答案会给我一个开始。我并不粗鲁地期待一个完整的解决方案，只是一个迹象，这些是否是我可行的目标。在

补充说：我仍然需要能够检索到一个单一的，特定的字典项的键。在

Answer 1

在这种情况下，我倾向于用两种不同的方式存储部分数据。在

如果您保留了dict，但是添加了一个由int索引的列表，该列表将显示键（r值？）你的口述？这将给您可能需要的随机访问（我假设您有dict是有原因的），以及您似乎需要添加的向后和向前行为。在

如果你走这条路，你可以把它全部打包在一个类中，这样你就不会在你的代码中分散了两次更新。在

采用treap或red-black-tree实现，并对其进行修改，使您能够指定一个键，并在下一个或上一个键处取回键、值对。如果您经常插入或删除值，其中一个可能更好。在

Answer 2

首先，您应该注意到您需要一个更好的数据结构。Python dict根本没有顺序，OrderedDict只是保持插入顺序（因此每次键更改都需要重新排序）。像^{}这样的已排序字典，甚至像blist.sortedlist这样的排序列表可能更适合您的需要。在

Is it possible for me to create an iterator class (using the iterator protocol) that will store the dictionary and enable me to loop through them in either forward, or reverse, order? I'm assuming/guessing that I might need to first assign an attribute-value that will indicate whether the next loop should be forward/reverse.

这里不需要单独的迭代器类。您可以通过内置的^{}函数获得免费的正向迭代和向后迭代：

for key in mydict:
  # do something

for key in reversed(mydict.keys()):
  # do something

Can I include a generator-function (nested) within my iterator class that will enable me to retrieve the next key; that is, beyond or before a supplied integer-number?

当然，itertools有很多功能，可以让您做这样的事情：

^{pr2}$

也可以将其打包到函数中：

def first_beyond(pivot, seq):
  next(dropwhile(lambda x: x <= pivot, seq))

first_beyond(4, mydict)
first_beyond(20, reversed(mydict.keys()))

Similarly, will there be a way for me to supply begin-and-end points and retrieve all keys that fall between these values (in sorted order)?

您可以轻松地为此构建一个通用工具：

from itertools import dropwhile, takewhile
def between(begin, end, seq):
  return takewhile(lambda x: x <= end, 
                   dropwhile(lambda x: x < begin, seq))

这样使用：

>>> list(between(4, 30, [1,2,4,8,16,32]))
[4, 8, 16]

编辑：如果您只是偶尔需要检查已排序的键，您可以将它们转换为已排序的列表并使用它们。习语同上：

keys = sorted(mydict)

# forward and backward iteration
for k in keys:
  # ...
for k in reversed(keys):
  # ...

# function that returns a forward or backward iterator based on an argument
def forward_or_backward(seq, forward=True):
  for x in (iter if forward else reversed)(seq):
    yield x

# random access inside a loop
for i, key in enumerate(keys):
  # next element
  key[i+1]

# the between and first_beyond functions above also work for lists

你的其他功能可以从这些部分粘在一起。请注意，创建一个特殊的类是不明智的，因为我们可以用一种足够通用的方式编写函数，使它们能够处理任何iterable，而不仅仅是键列表。在

Answer 3

我认为最适合您需要的数据结构是skip list。我从来没有实现过一个——一直想实现——但在我看来，这已经具备了您需要的所有东西。在

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

2. 跳过列表允许O（logn）插入、修改、删除和搜索。这不像字典那么快，但在我看来，如果你需要按排序顺序存储项目，字典会给你带来麻烦——甚至是一个OrderedDict，除非你很少添加键。

3. 通过上面wikipedia文章中描述的一些修改，甚至可以在O（logn）中实现索引访问。

Python here中有一个实现——可能还有其他实现。在

但是，您的一些注释表明您可能满足于简单地迭代字典的排序副本，而您只是在尝试清理上面的代码。所以这里有一个方法。这很幼稚，但这只是一个起点。这假设您完全可以使用O（n）搜索时间和O（nlogn）迭代时间，它们都是次优的。。。在

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