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.

Embayment

Answer 1

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 adiff not in B or A[adiff] != B[adiff]. (If there is no such key, the dicts are equal.)
• Also find the smallest key bdiff in B for which bdiff not in A or 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 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.

Annelieseannelise

Did you know that by reading the source for dict_compare (svn.python.org/projects/python/trunk/Objects/dictobject.c) or is it documented somewhere? – Lefebvre

Thanks for the info. (PS. I guess this means the behavior of dict.__cmp__ may vary across implementations. :-/ ) – Lefebvre

@NedBatchelder Can we format text like this in algo form, I believe it would be easy to grasp. Presently it is very inconvenient in reading. Btw thanks this is very good answer. – Imbibe

Some of the deviations from the original routine were bugging me, so I edited the answer to match dict_compare a bit more closely. (I didn't bother with the edge case handling for when a comparison mutates the dict, and the except ValueError will do the wrong thing if a comparison throws a ValueError. Unlike the original C, I can't return NULL as a sentinel, and None is already a valid return value.) If I got something wrong, feel free to revert or edit again. – Delois

If you want some example, you may look at https://www.quora.com/How-does-the-cmp-function-of-a-dictionary-work BTW, python3 is no longer support cmp – Deliladelilah

This slower but simpler (?) function gives the same answer: cmp = lambda A, B: (A > B) - (A < B) if not hasattr(A, '__keys__') else cmp(len(A), len(B)) if len(A) != len (B) else ([cmp(adiff, bdiff) if adiff != bdiff else cmp(A[adiff], B[bdiff]) for adiff, bdiff in zip(sorted(A.keys()), sorted(B.keys())) if adiff != bdiff or A[adiff] != B[bdiff]] + [0])[0] – Satisfy

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.

Ankeny

Answer 3

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

Lefebvre

Yeah, I'm just trying to make the interface match 2.4 dict's (work requirement). I'll probably do a full on 3.x port of this code later. – Embayment