paper cut: is a slice / Iterator sorted?

[gnzlbg]

I just used binary_search inside a loop and realized that it would be nice to check before the loop if my immutable slice was sorted. So I spent 10 minutes going through the standard library just to find out that there aren't any is_sorted, is_sorted_by, is_sorted_by_key, etc. algorithms implemented for neither slices nor iterators.

We should add:

• Iterator::is_sorted
• Iterator::is_sorted_by
• Iterator::is_sorted_by_key

and since Iterator is implemented for slices, we can add those methods to slices as well by just forwarding to the Iterator implementation.

[arielb1]

We also shouldn't change it to be O(n) on debug-assertions builds - debug-assertions should be for the last 2x of performance, not for potential order-of-magnitude slowdowns.

[gnzlbg]

@arielb1 sorry this issue turned out to be two issues, I've split that part to #44371.

[leonardo-m]

In the D language standard library there is also a wrapper for sorted iterables (that performs statistical tests inside its constructor), with it you can create functions that document in the code that return/accept sorted iterables.

[bluss]

and since Iterator is implemented for slices those methods should work on slices as well.

Just to help clarify here: slices are iterable (IntoIterator for &[T], &mut [T]), but not themselves iterators.

[gnzlbg]

@bluss what I meant is that we should probably implement those methods on slices as well, but that implementation should just be forwarded to the Iterator version. I've reworded the issue.

[Thiez]

How would it make sense for this operation to be defined on an iterator? It would have to consume the entire iterator to get the result, leaving you only with the information that the iterator that you now can't use anymore would indeed have been sorted. .is_sorted_by_key(select_the_key) seems particularly redundant, given that it would just be .map(select_the_key).is_sorted().

[gnzlbg]

It would have to consume the entire iterator to get the result,

Of course.

leaving you only with the information that the iterator that you now can't use anymore would indeed have been sorted.

There are many useful algorithms that consume an iterator. Iterators don't necessarily own the items; some iterators do, some don't. If you don't want the items to get lost then don't consume an iterator that owns them. You can either copy/clone the iterator before you consume it, or you can create it again. For example, given:

let v: Vec<u32> = vec![0, 1, 2, 3, 4, 5];

then this works

if v.iter().is_sorted() {
  for i in v.iter().map(|i| i* 2) {
    println!("{}", i);
  }
} 

but this won't compile

if v.into_iter().is_sorted() { // vec is consumed here
  for i in v.iter().map(|i| i * 2) {
    println!("{}", i);
  }
} 

Given that iterating over an Iterator consumes the iterator:

let v: Vec<u32> = vec![0, 1, 2, 3, 4, 5];
let it = v.iter().map(|i| i* 2);
for i in it { println!("{}", i); }  // it is moved here
for i in it { println!("{}", i); }  // ERROR: it was already moved

and that is_sorted must, by necessity, look at each element on the sequence, maybe you could elaborate on why you think that consuming an iterator in this algorithm is bad, and suggest what could be done about it instead?

.is_sorted_by_key(select_the_key) seems particularly redundant, given that it would just be .map(select_the_key).is_sorted().

I've added them for both convenience and consistency. The stable and unstable sort, sort_by, and sort_by_key functions are redundant as well, yet they are very convenient. To be consistent with the sort algorithms, I think is_sorted should provide these alternatives as well. However, I also think that having them is convenient.

[the8472]

How about a non-terminal .while_sorted() operation? All it would have to do is compare adjacent elements and stop iterating when they are not monotonic. .require_sorted() could panic instead. Maybe this could be generalized into .while_pair(|a,b| ...) and put into itertools?

[gnzlbg]

@the8472 itertools already has .tuple_window which combined with take_while is more generic than .while_pair.

Anyhow, I am neither in favour nor opposed to doing that, but I think that discussion should belong in a different issue.

This issue is about std neither checking the precondition of binary_search nor providing users the algorithm to check it themselves.

There is some prior art for is_sorted in other standard libraries, e.g., in C++, although there it is implemented on top of is_sorted_until.

[the8472]

is_sorted_until seems like a good model. In the rust case that could be sorted_prefix() -> (impl Iterator, impl Iterator). Then a consumer could do a binary search with the prefix and either panic if the tail is non-empty or do something else with it.

[Thiez]

That seems like a lot of complexity to avoid a single call to sort() (or collect::<Vec<_>>() followed by sort()). Especially since your proposed sorted_prefix would have to perform hidden allocations to do its work anyway.

[the8472]

Ok, how about num_sorted() -> usize for iterators? That could get you the sorted prefix of a slice for example. It's more powerful than is_sorted() without additional cost.