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 Rust Playground for an example.
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.
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.
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.
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: Rust Playground . 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!
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: