字典无法排序,因此您需要创建一个可以保留字典但不在比较中使用它的东西。
元组不是一个好选择,因为其中的每个元素可能被比较。例如,如果第一个元素(您的key
)相等,则会比较第二个元素:
>>> (1, {'a': 1}) < (1, {'a': 2})
TypeError: unorderable types: dict() < dict()
或者使用
heap
:
>>> heap = []
>>> heapq.heappush(heap, (2, {'a': 1}))
>>> heapq.heappush(heap, (2, {'b': 2}))
TypeError: unorderable types: dict() < dict()
如果“key”保证不相等,那么就没有问题,因为第二项不会被比较。
如果您只想为“dict”创建一些存储空间,可以简单地创建一个类来存储“(key,value)”,但仅对“key”进行比较。
from functools import total_ordering
@total_ordering
class KeyDict(object):
def __init__(self, key, dct):
self.key = key
self.dct = dct
def __lt__(self, other):
return self.key < other.key
def __eq__(self, other):
return self.key == other.key
def __repr__(self):
return '{0.__class__.__name__}(key={0.key}, dct={0.dct})'.format(self)
把这些东西插入到你的堆
中,这将保证字典
不会被比较:
>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, KeyDict(2, {'a': 1}))
>>> heapq.heappush(heap, KeyDict(2, {'b': 2}))
>>> heap
[KeyDict(key=2, dct={'a': 1}), KeyDict(key=2, dct={'b': 2})]
一种替代方法是使用由计数器作为第二个元素组成的3个元组,这样可以确保比较不会转到字典中:
>>> from itertools import count
>>> cnt = count()
>>> heap = []
>>> heapq.heappush(heap, (2, next(cnt), {'a': 1}))
>>> heapq.heappush(heap, (2, next(cnt), {'b': 2}))
>>> heap
[(2, 0, {'a': 1}), (2, 1, {'b': 2})]
heap
是空的。 - MSeifert