Is there a description of how cmp works for dict objects in Python 2?

Question

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.

Answer 1

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__.

Answer 2

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.

Answer 3

If you are asking how comparing dictionaries works, it is this:

To compare dicts A and B, first compare their lengths. If they are unequal, then return cmp(len(A), len(B). Next, find the key adiff in A that is the smallest key for which A[adiff] != B[adiff]. Also find the smallest key bdiff in B for which A[bdiff] != B[bdiff]. If adiff != bdiff, then return cmp(adiff, bdiff). Else return cmp(A[adiff], B[bdiff]).

In pseudo-code:

def smallest_diff_key(A, B):
    """return the smallest key adiff in A such that A[adiff] != B[bdiff]"""
    diff_keys = [k for k in A if A.get(k) != B.get(k)]
    return min(diff_keys)

def dict_cmp(A, B):
    if len(A) != len(B):
        return cmp(len(A), len(B))
    adiff = smallest_diff_key(A, B)
    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.