[Pre-RFC] Remove RandomAccessIterator


#1

I think we should remove RandomAccessIterator (“RAI”) from the library.

pub trait RandomAccessIterator: Iterator {
    fn indexable(&self) -> usize;
    fn idx(&mut self, index: usize) -> Option<Item>;
}
  • This trait has been part of libstd for a long time, but it has never found a real use case.

  • We have not found a sound and practical expansion into mutable reference RAI.

  • Reasonable performance of algorithms implemented using RAI have not been demonstrated.

  • Overlaps with the Index trait, which unlike RAI does have an expansion into mutable references.

  • Does not give iterators any O(1) skip multiple steps forward/backward capabilities.

  • The trait can be added again when we figure out the above points.


#2

Yeah a really useful RAI would need to provide unchecked options for efficient algorithm implementation, I think.

O(1) skip should be trivial to add backwards-compatibly with proper specialization support, though.

Also: Really disappointed you didn’t find a way to add an extra I to the accronym to shim in a “remove RAII” joke :wink:


#3

I’m in favor of removing this. Use cases have never been clear.


#4

Sounds good to me. We explicitly chose not to mark it #[stable] for several of the reasons you list.


#5

So maybe I shouldn’t be worried? I’m just worried that it will suddenly slip in for no reason at all.

Some other features are like that. Permutations/ElementSwaps in libstd are worrying.

  • They allocate too much
  • Cute algorithm but the lexical ordering is needed more often, .next_permutation covers that in-place.

#6

Understood. I think this will get more clear over time. Right now we’re stabilizing things we clearly need, deprecating/moving out things we clearly don’t want (for now), and leaving the rest unstable.

In the long run, unstable items should be on a “path to stable” or else be removed. I think after the dust settles for 1.0 we’ll re-evaluate the remaining unstable items under this metric.

Yep – good eye! These were also specifically not stabilized because they seem somewhat niche.

FWIW, these features could probably be moved out of tree before 1.0, it just hasn’t been a core priority. If you wanted to put together an RFC/PR, I’d be glad to review. (It might be worth putting together a more comprehensive list of such APIs that we could reach consensus on beforehand.)


#7

I don’t agree for permutations in general, just that this is not a good way to implement it.