Why does `slice::sort_by_key` uses `B` and not `&B` as the key?


#1

slice::sort_by_key is a thin wrapper around “real” sort function, it requires key extraction function to return B and not &B, so if key is not Copy you have to use slice::sort_by instead. See https://play.rust-lang.org/?gist=eea7cb6f6d574403392d630ce4f2a495&version=stable for an example.

What is the reason behind this design? Thank you!


#2

Using &B would mean it could only work with types that contain that B somehow.

For instance, suppose you had a Vec<&str> that you wanted to sort by the number of words. B would be a usize, but there’s no way for you to return a &usize for this.

For sorting by keys that would preferably just be borrowed, where a &B key is possible, I’d suggest just using sort_by instead to compare them directly.


#3

I think this would work much better if region inference worked better when returning references from a closure. You’d then be able to return a &SomeType and so long as &SomeType: Ord it would work.

Going a step further, maybe a T: AsRef<B> could be returned, and then you can also abstract over owned vs borrowed keys.


#4

Thinking about this a bit more, one might imagine the following signature instead:

fn sort_by_key<'a, ..., F: FnMut(&'a T) -> B>(&'a mut self, ...) {...}

This would use the “proper” lifetime in the closure and should allow returning a reference back. The trouble now, of course, is the borrow resulting from calling the closure does not allow mutating the slice.

The readonly methods, such as binary_search_by_key, do use a signature like above, probably for this very reason (to allow returning references tied to the closure arg).

So in fact, I don’t think region inference has anything to do with this; there’s just no way to express the lifetime relationships here accordingly.


#5

That makes sense, thank you! Rust doesn’t have function overload, it seems, but I was able to create my vision of slice::sort_unstable_by_key_ref: https://play.rust-lang.org/?gist=609cbfec09a1e32b19d9aa4d0713d8b6&version=stable . One point I don’t grasp at the moment is that I had to change F: FnMut(&T) -> B to F: Fn(&T) -> &B – the relations between FnOnce, FnMut and Fn are not 100% clear to me.

Is this function worth reworking into a full-blown pull request? What do you think? Thank you!


#6

That shouldn’t be necessary - what error did you get? Make sure the FnMut param is declared as mut itself (ie mut f: F).


#7

It can remain FnMut if you also bind the parameter mutably, like mut f: F. That mut makes no difference in the API to the caller, as they just provide f by value, but you need it mutable to call FnMut. You didn’t need that for the plain by_key version because there you’re just passing that by value as a parameter again.

There are already 6 sorting methods – 3 variants of sort and 3 sort_unstable – so I fear that adding ref versions of each might be too much. But I found a related issue for this, so maybe you could propose it there first:


#8

Yes, passing f as mut f: F solves the issue.

This is exactly the part I didn’t realize :slight_smile: Thanks for explanation!

C++ has overloads to workaround this issue… I get your point. Will chime in the issue discussion.