Add a "Vec.sorted()" function

Many functional languages have a List.sorted() function to enable something like:

return list
    .do_something()
    .sorted()
    .do_something_else()

which looks much nicer than

let mut l = list.do_something();
sort(&mut l);
return l.do_something_else();

and this would be nice for Rust, too.

This could even be easily implemented by oneself, but it would be nicer if it was there by standard:

trait SortedImpl {
    fn sorted(self) -> Self;
}

impl<E> SortedImpl for Vec<E>
    where E: std::cmp::Ord 
{
    fn sorted(mut self) -> Self {
        self.sort();
        self
    }
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=655714df16aa6c9321bbbb36c1c7bafc

8 Likes

I've wanted this many, many times. :+1:

3 Likes

You can get this with Itertools::sorted, relying on the fact that collecting vec::IntoIter to Vec is specialized into a no-op.

vec.into_iter().sorted().collect()

Depending on what your do_something() and do_something_else() are doing, this sorted() might even be preferable.

13 Likes

For me vec.sorted() sounds like to clone the original vector, sort, and return it. Kotlin has such convention.

3 Likes

Swift has the same convention: sort would sort in place and sorted would return a sorted clone of the item. The convention is quite useful, though it's late enough in the life of Rust's standard library that I'm not sure it could be adopted widely the way it is in Swift.

1 Like

I assumed the same and was quite surprised about the move. And I never used Kotlin or Swift.

Yes, I still think this is a good idea:

4 Likes

I'd say that it sounds like it returns a sorted version of the vector. In other languages, this means that the original vector has to be cloned to avoid side effects. This has the disadvantage that functional style often has worse performance.

But in Rust we have the possibility to do this without cloning it (by moving) so that we can have functional style without the performance overhead.

If you do want to clone it (because you still need the original vector), you can still do .clone().sorted(). And the best thing is: If you forget the .clone(), the compiler will throw an error ("use of moved value", I think).

22 Likes

Exactly. I would expect this method to consume self and produce a new vector.

4 Likes

For better visibility, here's how would Cargo look if we had sorted: https://github.com/matklad/cargo/commit/3ff7ccc82dc9b555c25e7df97e1afde648810399. In majority of cases, sorted leads to nicer code than sort.

10 Likes

That diff looks great. Anyone up for making the PR?

1 Like

I ran this same change with itertools. I agree this looks nicer, I'm not 100% convinced it should be in std.

2 Likes

I think this is common and simple enough that it should be in std

6 Likes

The other thing I notice about the itertools approach is the transformation to vec is a little magical. Embedding a .sorted() in an iterator chain with itertools is nice, the proposed change looks like

x.iter().filter(...).collect::<Vec<_>>().sorted().into_iter().map(...)

in those cases.

3 Likes

I assume this would imply also adding Vec::sorted_by and Vec::sorted_by_key?

It being on Vec is a nice way to avoid the "does it collect, does it return a Vec or an iterator, is it lazy" etc questions that happen with any iterator version.

6 Likes

It also is a nice way out of Iterator being in libcore. You need liballoc for sorted iterator adaptor.

2 Likes

Oh yeah, we also need to ask whether there should also be Vec::sorted_unstable{_by{_key}}...

1 Like

However, if you're sorting in Vec, you don't add very much by chaining .sorted(), since you can avoid it altogether by doing something like .collect<BTreeSet<_>>() instead. It's only useful if you intend to actually end on a Vec.

That's a pattern I suspect people wouldn't automatically think of. Might be a good argument for a .collect_sorted() on iterators.

1 Like

That is semantically different, because it gets rid of duplicates.

4 Likes