Add a "Vec.sorted()" function

1

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

10 Likes
2

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

4 Likes
3

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.

16 Likes
4

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

3 Likes
5

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
6

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

7

Yes, I still think this is a good idea:

4 Likes
8

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).

23 Likes
9

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

4 Likes
10

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.

11 Likes
11

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

1 Like
12

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

2 Likes
13

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

6 Likes
14

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
15

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
16

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

2 Likes
17

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

1 Like
18

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.

19

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
20

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

4 Likes