CODEWITHSUNDEEP
pythonpython-2.x
DannoHung
DannoHung

Reputation: 411

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

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.

Upvotes: 22

Views: 8288

Answers (3)

Ned Batchelder
Ned Batchelder

Reputation: 375604

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.

Upvotes: 34

Eric Snow
Eric Snow

Reputation: 1198

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.

Upvotes: 2

unutbu
unutbu

Reputation: 879671

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

Upvotes: 0

Related Questions