I've been trying to make a dict subclass inheriting from UserDict.DictMixin that supports non-hashable keys. Performance isn't a concern. Unfortunately, Python implements some of the functions in DictMixin by trying to create a dict object from the subclass. I can implement these myself, but I am stuck on __cmp__.
I cannot find a succinct description of the logic used by the built-in __cmp__ for the dict class.
If you are asking how comparing dictionaries works, it is this:
adiff not in B or A[adiff] != B[adiff]. (If there is no such key, the dicts are equal.)bdiff not in A or A[bdiff] != B[bdiff].In pseudo-code:
def smallest_diff_key(A, B):
"""return the smallest key adiff in A such that adiff not in B or A[adiff] != B[bdiff]"""
diff_keys = [k for k in A if k not in B or A[k] != B[k]]
return min(diff_keys)
def dict_cmp(A, B):
if len(A) != len(B):
return cmp(len(A), len(B))
try:
adiff = smallest_diff_key(A, B)
except ValueError:
# No difference.
return 0
bdiff = smallest_diff_key(B, A)
if adiff != bdiff:
return cmp(adiff, bdiff)
return cmp(A[adiff], b[bdiff])
This is translated from the 2.6.3 implementation in dictobject.c.
An alternative is to use the Mapping ABC from the collections package. It is available in 2.6 and up. You just inherit from collections.Mapping and implement the __getitem__, __contains__, and __iter__ methods. You get everything else for free.
There is a description of __cmp__ here, but I think the important thing to note is that __cmp__ is only used if the “rich comparison” methods, such as __lt__ and __eq__ are not defined. Moreover, in Python3, __cmp__ is removed from the language. So perhaps eschew __cmp__ altogether and just define __lt__ and __eq__.
