130

What methods need to be overridden/implemented when making user-defined classes sortable and/or hashable in python?

What are the gotchas to watch out for?

I type dir({}) into my interpreter to get a list of methods on built-in dicts. Of those, I assume I need to some implement some subset of

['__cmp__', '__eq__', '__ge__', '__gt__', '__hash__', '__le__', '__lt__', '__ne__']

Is there a difference in which methods must be implemented for Python3 as opposed to Python2?

Community
  • 1
  • 1
Matt Fenwick
  • 48,199
  • 22
  • 128
  • 192
  • 3
    Good discussion here: http://stackoverflow.com/q/1061283/641766. Difference between Python 2.x and 3.x is that `__cmp__` was removed. – Zach Kelling Aug 22 '11 at 19:56

4 Answers4

143

I almost posted this as a comment to the other answers but it's really an answer in and of itself.

To make your items sortable, they only need to implement __lt__. That's the only method used by the built in sort.

The other comparisons or functools.total_ordering are only needed if you actually want to use the comparison operators with your class.

To make your items hashable, you implement __hash__ as others noted. You should also implement __eq__ in a compatible way -- items that are equivalent should hash the same.

agf
  • 171,228
  • 44
  • 289
  • 238
  • so a poor implementation of `__lt__` could cause python to sort unpredictably? (for instance, if x.__lt__(y) and y.__lt__(x)) – Matt Fenwick Aug 24 '11 at 01:04
  • 6
    I don't know about "unpredictably", it'll be consistent if fed the exact same input, but a different input order could cause different items to be in a different order. Yes, if you improperly implement the comparison used to sort, Python will sort improperly. I'd recommend a `__key__` function that turns the instance into a tuple, then just have both `__lt__` (`self.__key__() < other.__key__()`) and `__hash__` (`hash(self.__key__())`) use that. – agf Aug 24 '11 at 01:10
  • What about making the classes themselves sortable, instead of just instances of classes? For example, if you want to say FooClass < BarClass = False but BarClass < FooClass = True, so you can sort a list of classes. – odigity Dec 17 '22 at 15:10
  • 1
    @odigity You'd need to define the methods on the metaclass / type. – agf Dec 18 '22 at 20:42
  • @agf - That's what I was afraid of. Very well, I shall fetch the forbidden tomes... – odigity Dec 19 '22 at 15:29
35

There isn't any difference between Python 2 and 3.

For sortability:

You should define comparision methods. This makes your items sortable. Generally, you shouldn't prefer __cmp__().

I usually use functools.total_ordering decorator.

functools.total_ordering(cls) Given a class defining one or more rich comparison ordering methods, this class decorator supplies the rest. This simplifies the effort involved in specifying all of the possible rich comparison operations:

The class must define one of __lt__(), __le__(), __gt__(), or __ge__(). In addition, the class should supply an __eq__() method.

You should be careful that your comparison methods do not have any side effects. (change any of the values of the object)

For hashing:

You should implement __hash__() method. I think the best way is returning hash(repr(self)), so your hash would be unique.

Chris Huang-Leaver
  • 6,059
  • 6
  • 41
  • 67
utdemir
  • 26,532
  • 10
  • 62
  • 81
  • 1
    For an example of `functools.total_ordering` from the documentation, see [here](https://docs.python.org/2/library/functools.html#functools.total_ordering). – Evgeni Sergeev Jun 05 '16 at 08:15
  • Depending on your use consider hash returning `id(self)` since that's going to be the local memory location. It's a quick and basically solid has that implements the hashing such that if the object is the other object it hashes the same otherwise it doesn't. – Tatarize Aug 20 '22 at 05:28
6

There are a few ways of marking your object sortable. First - rich comparison, defined by a set of functions:

object.__lt__(self, other)
object.__le__(self, other)
object.__eq__(self, other)
object.__ne__(self, other)
object.__gt__(self, other)
object.__ge__(self, other)

Also it is possible to define only one function:

object.__cmp__(self, other)

And the last should be defined if you want to define custom __hash__ function. See the doc.

Garrett Hyde
  • 5,409
  • 8
  • 49
  • 55
Roman Bodnarchuk
  • 29,461
  • 12
  • 59
  • 75
  • 9
    In Python 3, "[...]the `__cmp__()` special method is no longer supported," see the [relevant section here](https://docs.python.org/release/3.0.1/whatsnew/3.0.html#ordering-comparisons). – Evgeni Sergeev Jun 05 '16 at 08:13
-6

Implement __lt__(self,other) method is the answer to make your class sortable.
It can be used for not only the built-in method sorted(iterable), but also priority queue via heapq module.

In addition, I don't like python's design, so many '__ge__', '__gt__', '__le__', '__lt__', '__ne__' methods are not intuitive at all !
As a contrast, Java's Interface Comparable<T> (see java doc) returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object, which is direct and friendly!

yichudu
  • 165
  • 2
  • 12
  • 12
    Most of your answer covers your opinion (which should not be part of the answer). – skyking Apr 25 '18 at 09:59
  • 3
    @skyking... while I don't agree with the opinions in this particular answer, I do believe that opinion (with researched and useful data relevant to the question) is very valuable. The error in this opinion answer is not supporting the opinion with relevant data. But understanding preferences helps people make decisions and is therefore very useful. Here, the answer is ill formed because there is no useful and actionable python code to illustrate a pythonic way to code based on author's preferences. – Andrew Jun 29 '20 at 22:17
  • 2
    @Andrew Except that this opinion is completely irrelevant cause the question is about python. There is no point to tell java is better when the question is about python, not "which language is better to do this ?". Its almost trolling about the never ending pointless argument of "what is the beast programming language ?" and so useless for this question. – Welgriv Aug 11 '21 at 11:06