Q: sort's key and cmp parameters

[Duncan Booth]

Paul Rubin <http://phr.cx@NOSPAM.invalid> wrote:

> Duncan Booth <duncan.booth at invalid.invalid> writes:
>> > Is there a real-life sorting task that requires (or is far more
>> > efficient with) cmp and can't be easily achieved with key and reverse?
>> > 
>> There is no sorting task that *requires* cmp. If all else fails you can 
>> define a key class to wrap the original wrapper such that comparing the 
>> keys simply calls the comparison function that you *would* have used.
> 
> I would count that as key being far less efficient, though still
> giving the same result.

You'll notice I carefully didn't comment on the efficiency. However, 
without testing it I'm not convinced that it would be 'far less' efficient.

Using cmp2key you have an overhead of one class per sort plus one instance 
for each element being sorted, and an additional one function call for each 
comparison. The only example given so far that would justify needing this 
(sorting trees which require recursive comparison) by its very nature would 
make both of these additional overheads insignificant as each element 
already contains multiple instances and each comparison contains multiple 
function calls.