Is_sorted() method in impl Iterator for Range

The trait std::iter::Iterator provides many methods, but they are all implemented as "default implementations," so that those who implements Iterator on their own structs / enums can re-implement some of these methods (such as size_hint() or nth()).

I found that impl<A> Iterator for std::pos::Range<A> requires A: std::iter::Step, which guarantees the values generated by Range<A> are sorted in ascending order. I thought this meant is_sorted() methods can be written as one which always returns true, but the actual implementation wasn't so.

Are there any reasons of this (like, because one can implement Step that generates numbers not in ascending order)?

I'm guessing that optimisation just hasn't been implemented yet.

In theory it could be implemented by adding either an is_positive() method to the Step trait or giving it a ZERO: Self associated constant which you can use to check that you've got an ascending range (i.e. fn is_sorted(self) -> bool { self.step >= Self::ZERO }).

This premise is based on the assumption that Step will only ever be implemented for numeric types, which certainly not the case.


The implementations of Iterator::min and Iterator::max for Range already assume that it always yields items in ascending order, so it should be fine for is_sorted to do the same: - source

1 Like

Ohhh then, I've been worrying if the assumption was invalid, but there was no need to worry. Thank you very much.

Or maybe there's no need to implement is_sorted? Perhaps the compiler can
optimize this trivial case

It looks like the compiler is currently able to optimize this to true when the range bounds are constant, but not when they are runtime variables: Compiler Explorer

Oh, my experiment was not enough. Thank you.

I submitted a pull request to override is_sorted for Range: Optimize is_sorted for Range and RangeInclusive by mbrubeck · Pull Request #89335 · rust-lang/rust · GitHub

1 Like

Thank you! I'm glad to hear that the commit has
been approved.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.