I came across this function here.
I am baffled as to how this would be implemented -- how does the key function generated by cmp_to_key know what "position" a given element should be without checking how the given element compares with every other element of interest?
The cmp_to_key method returns a special object that acts as a surrogate key:
class K(object):
__slots__ = ['obj']
def __init__(self, obj, *args):
self.obj = obj
def __lt__(self, other):
return mycmp(self.obj, other.obj) < 0
def __gt__(self, other):
return mycmp(self.obj, other.obj) > 0
def __eq__(self, other):
return mycmp(self.obj, other.obj) == 0
def __le__(self, other):
return mycmp(self.obj, other.obj) <= 0
def __ge__(self, other):
return mycmp(self.obj, other.obj) >= 0
def __ne__(self, other):
return mycmp(self.obj, other.obj) != 0
def __hash__(self):
raise TypeError('hash not implemented')
When sorting, each key will get compared to most other keys in the sequence. Is this element at position 0 lower than or greater than that other object?
Whenever that happens, the special method hooks are invoked, so __lt__ or __gt__ is called, which the surrogate key turns into a call to the cmp method instead.
So the list [1, 2, 3] is sorted as [K(1), K(2), K(3)], and if, say, K(1) is compared with K(2) to see if K(1) is lower, then K(1).__lt__(K(2)) is called, which is translated to mycmp(1, 2) < 0.
This is how the old cmp method was working anyway; return -1, 0 or 1 depending on wether the first argument is lower than, equal to or greater than the second argument. The surrogate key translates those numbers back to boolean values for the comparison operators.
At no point does the surrogate key need to know anything about absolute positions. It only needs to know about one other object it is being compared with, and the special method hooks provide that other object.
cmp_to_key function only exists to support legacy Python 2 sorting codebases. The simpler pythonic method is to use a key function for sorted() instead, and if the sorting algorithm call for a cmp()-like approach, implement custom rich comparison hooks directly.
key but easy to come up with a compare function... e.g., I want to sort a list of numbers so that all odd numbers come first, in ascending order, and then all even numbers come next, in descending order.(n % 2 == 0, (n % 2 and 1 or -1) * n) for the key then.K class used by cmp_to_key() does.