Pre-RFC-ish: add Vec::sorted and friends

libs
1

Hi! What do folks think about adding

impl Vec<T> {
    fn sorted(self) -> Vec<T> where T: Ord { 
        let mut this = self;
        this.sort();
        this
    }
   // and seven other `sort` flavors? 
}

to the stdlib?

This method would allow to replace

let mut deps_metadata = cx.dep_targets(unit)
    .iter()
    .map(|dep| metadata_of(dep, cx, metas))
    .collect::<Vec<_>>();
deps_metadata.sort();

with a more fluent version:

let deps_metadata = cx.dep_targets(unit)
    .iter()
    .map(|dep| metadata_of(dep, cx, metas))
    .collect::<Vec<_>>()
    .sorted();

While seemingly a trivial change, I think it is a nice readability improvement over “collect to a mut vec, then sort”. The problem with the latter approach is that you have to declare the variable as mut, and so all future readers would wonder “is this mut only for sorting, or do we genuinely push and pop something down the line?”. Also in some cases it should be possible to get rid of the variable altogether.

At least in my experience, in the majority of case sorted is a more natural API then sort. To test this hypothesis, I’ve tired to change Cargo to use sorted. There were 20 call altogether, and in 15 cases it was possible to take advantage of sorted: https://github.com/matklad/cargo/commit/3ff7ccc82dc9b555c25e7df97e1afde648810399

The proposal is not without drawbacks, naturally! We already have a large variety of sorting methods, and this proposal further doubles their quantity! What’s more, while sort is implemented for &mut [T], sorted necessary has to be implemented for Vec<T>.

5 Likes
2

A design question: I think I’d like sorted to contain a collect() followed by a sort. This means you use it like this:

let deps_metadata = 
     cx
     .dep_targets(unit)
     .iter()
     .map(|dep| metadata_of(dep, cx, metas))
     .sorted();

A disadvantage of this is that if you already have a vec, you can’t sort it without duplicating it first.

In D language sorted doesn’t return the sorted slice, it returns something that could release a slice. This is for reasons similar to Python sort() returning None.

3

Interesting!

I think having it on Vec is indeed more general (in the Cargo commit, several uses are not preceded with .collect(), and at least one goes via collect::<Result<Vec<_>>>()?). .sorted on iterators also can have different semantics: it could return a lazily-sorted iterator, so that .sorted().take(10).collect::<Vec<_>>() works in O(N).

1 Like
4

I think sorted() working on Vec<> is OK if we also have something like a short to_vec() that turns an iterator into a Vec... :slight_smile:

5

In particular, one would expect there to be a .stable_sorted() and such?

6

Yes, all versions of sort should be available:

sorted
sorted_by
sorted_by_key
sorted_unstable
sorted_unstable_by
sorted_unstable_by_key
sorted_by_cached_key

See also: https://docs.rs/itertools/0.7.8/itertools/trait.Itertools.html#method.sorted

7

.sorted() on iterators would be useful. It might even be marginally faster than .collect + sort, since it could collect straight into two partitions.

It would have to be .sorted::<Vec<_>>() to keep generality of .collect(), e.g. also support .sorted<Result<Vec<_>>>().

1 Like
8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.